Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



$ {\rm SOR}$-methods for the eigenvalue problem with large sparse matrices

Author: Axel Ruhe
Journal: Math. Comp. 28 (1974), 695-710
MSC: Primary 65F15
MathSciNet review: 0378378
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The eigenvalue problem $ Ax = \lambda Bx$, where A and B are large and sparse symmetric matrices, is considered. An iterative algorithm for computing the smallest eigenvalue and its corresponding eigenvector, based on the successive overrelaxation splitting of the matrices, is developed, and its global convergence is proved. An expression for the optimal overrelaxation factor is found in the case where A and B are two-cyclic (property A). Further, it is shown that this SOR algorithm is the first order approximation to the coordinate relaxation algorithm, which implies that the same overrelaxation can be applied to this latter algorithm. Several numerical tests are reported. It is found that the SOR method is more effective than coordinate relaxation. If the separation of the eigenvalues is not too bad, the SOR algorithm has a fast rate of convergence, while, for problems with more severe clustering, the c-g or Lanczos algorithms should be preferred.

References [Enhancements On Off] (What's this?)

  • [1] O. Axelsson, "A generalized SSOR method," Nordisk Tidskr. Informationsbehandling (BIT), v. 13, 1972, pp. 443-467. MR 0339467 (49:4226)
  • [2] W. W. Bradbury & R. Fletcher, "New iterative methods for solution of the eigenproblem," Numer. Math., v. 9, 1966, pp. 259-267. MR 36 # 2313. MR 0219230 (36:2313)
  • [3] G. Buffoni, "Evaluation of eigensolutions of discrete space diffusion equation," Calcolo, v. 4, 1967, pp. 169-177. MR 42 # 7077. MR 0272166 (42:7047)
  • [4] A. R. Curtis & J. K. Reid, "The solution of large sparse unsymmetric systems of linear equations," Proc. IFIP Congress (Ljubljana, 1971), C. V. Freeman (Ed.), North-Holland, Amsterdam, 1972. MR 0458821 (56:17021)
  • [5] M. Engeli, Th. Ginsburg, H. Rutishauser & E. Stiefel, "Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems," Mitt. Inst. Angew. Math. Zürich, No. 8, 1959. MR 26 #3218. MR 0145689 (26:3218)
  • [6] D. K. Faddeev & V. N. Faddeeva, Computational Methods in Linear Algebra, Fizmatgiz, Moscow, 1960; English transl., Freeman, San Francisco, Calif., 1963. MR 28 #1742.
  • [7] G. E. Forsythe & W. Wasow, Finite-Difference Methods for Partial Differential Equations, Appl. Math. Ser., Wiley, New York, 1960. MR 23 # B3156. MR 0130124 (23:B3156)
  • [8] Isaac Fried, "Gradient methods for finite element eigenproblems," AIAA J., v. 7, 1969, pp. 739-741.
  • [9] M. Geradin, Analyse Dynamique Duale des Structures par la Méthode des Eléments Finis, Dissertation, Université de Liège, Belgium, 1972.
  • [10] G. H. Golub, "Some uses of the Lanczos algorithm in numerical linear algebra," Topics in Numerical Analysis, J. H. Miller, Editor, Academic Press, London and New York, 1973, pp. 173-184. MR 0359289 (50:11743)
  • [11] F. G. Gustavson, "Some basic techniques for solving sparse systems of linear equations," Sparse Matrices and Their Applications, D. J. Rose & R. A. Willoughby, Editors, Plenum Press, New York, 1972, pp. 41-52.
  • [12] M. R. Hestenes & W. Karush, "A method of gradients for the calculation of the characteristic roots and vectors of a real symmetric matrix," J. Res. Nat. Bur. Standards, v. 47, 1951, pp. 45-61. MR 13, 283. MR 0043552 (13:283d)
  • [13] S. Holm, Coordinate Overrelaxation Methods for the Eigenproblem, Report UMINF-33.73, Department of Information Processing, Umeå, Sweden.
  • [14] W. Kahan, Relaxation Methods for an Eigenproblem, Technical Report CS-44, Computer Science Department, Stanford University, Stanford, California, 1966.
  • [15] C. Lanczos, "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators," J. Res. Nat. Bur. Standards, v. 45, 1950, pp. 255-282. MR 13, 163. MR 0042791 (13:163d)
  • [16] J. M. Ortega & W. C. Rheinboldt, "Local and global convergence of generalized linear iterations," Studies in Numerical Analysis. 2: Numerical Solutions of Nonlinear Problems (Sympos. SIAM, Philadelphia, Pa., 1968), Soc. Indust. Appl. Math., Philadelphia, Pa., 1970, pp. 122-143. MR 43 #4242. MR 0278512 (43:4242)
  • [17] C. C. Paige, "Computational variants of the Lanczos method for the eigenproblem," J. Inst. Math. Appl., v. 10, 1972, pp. 373-381. MR 0334480 (48:12799)
  • [18] A. Ruhe, Iterative Eigenvalue Algorithms for Large Symmetric Matrices, Report UMINF-31.72, Department of Information Processing, Umeå, Sweden.
  • [19] H. R. Schwarz, "The eigenvalue problem $ (A - \lambda B)x = 0$ for symmetric matrices of high order," Comp. Meth. Appl. Mech. Engnrg., v. 3, 1974, pp. 11-28. MR 0381273 (52:2170)
  • [20] G. W. Stewart, "On the sensitivity of the eigenvalue problem $ Ax = \lambda Bx$," SIAM J. Numer. Anal., v. 9, 1972, pp. 669-686. MR 0311682 (47:244)
  • [21] D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971. MR 46 #4698. MR 0305568 (46:4698)
  • [22] A. Bracha-Barak & P. E. Saylor, "A symmetric factorization procedure for the solution of elliptic boundary value problems," SIAM J. Numer. Anal., v. 10, 1973, pp. 190-206. MR 0315876 (47:4425)
  • [23] P. Concus & G. H. Golub, "Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations," SIAM J. Numer. Anal., v. 10, 1973, pp. 1103-1120. MR 0341890 (49:6636)
  • [24] I. Shavitt, C. F. Bender, A. Pipano & R. P. Hosteny, "The iterative calculation of several of the lowest or highest eigenvalues and corresponding eigenvectors of very large symmetric matrices," J. Computational Phys., v. 11, 1973, pp. 90-108. MR 0339471 (49:4230)
  • [25] O. B. Widlund, "On the use of fast methods for separable finite difference equations for the solution of general elliptic problems," Sparse Matrices and Applications, D. J. Rose & W. A. Willoughby, Editors, Plenum Press, New York, 1972, pp. 121-134.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F15

Retrieve articles in all journals with MSC: 65F15

Additional Information

Keywords: Eigenvalues, sparse matrices, overrelaxation
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society