-methods for the eigenvalue problem with large sparse matrices

Author:
Axel Ruhe

Journal:
Math. Comp. **28** (1974), 695-710

MSC:
Primary 65F15

DOI:
https://doi.org/10.1090/S0025-5718-1974-0378378-X

MathSciNet review:
0378378

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The eigenvalue problem , 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.

**[1]**O. Axelsson,*A generalized 𝑆𝑆𝑂𝑅 method*, Nordisk Tidskr. Informationsbehandling (BIT)**12**(1972), 443–467. MR**0339467****[2]**W. W. Bradbury and R. Fletcher,*New iterative methods for solution of the eigenproblem*, Numer. Math.**9**(1966), 259–267. MR**0219230**, https://doi.org/10.1007/BF02162089**[3]**G. Buffoni,*Evaluation of eigensolutions of discrete space diffusion equation*, Calcolo**4**(1967), 169–177. MR**0272166**, https://doi.org/10.1007/BF02576732**[4]**A. R. Curtis and J. K. Reid,*The solution of large sparse unsymmetric systems of linear equations*, Information processing 71 (Proc. IFIP Congress, Ljubljana, 1971) North-Holland, Amsterdam, 1972, pp. 1240–1245. MR**0458821****[5]**M. Engeli, Th. Ginsburg, H. Rutishauser, and 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), 107. MR**0145689****[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]**George E. Forsythe and Wolfgang R. Wasow,*Finite-difference methods for partial differential equations*, Applied Mathematics Series, John Wiley & Sons, Inc., New York-London, 1960. MR**0130124****[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 (Proc. Roy. Irish Acad. Conf., Univ. Coll., Dublin, 1972) Academic Press, London, 1973, pp. 173–184. MR**0359289****[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]**Magnus R. Hestenes and William Karush,*A method of gradients for the calculation of the characteristic roots and vectors of a real symmetric matrix*, J. Research Nat. Bur. Standards**47**(1951), 45–61. MR**0043552****[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]**Cornelius Lanczos,*An iteration method for the solution of the eigenvalue problem of linear differential and integral operators*, J. Research Nat. Bur. Standards**45**(1950), 255–282. MR**0042791****[16]**James M. Ortega and Werner C. Rheinboldt,*Local and global convergence of generalized linear iterations*, Studies in Numerical Analysis, 2: Numerical Solutions of Nonlinear Problems (Symposia, SIAM, Philadelphia, Pa., 1968) Soc. Indust. Appl. Math., Philadelphia, Pa., 1970, pp. 122–143. MR**0278512****[17]**C. C. Paige,*Computational variants of the Lanczos method for the eigenproblem*, J. Inst. Math. Appl.**10**(1972), 373–381. MR**0334480****[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 (𝐴-𝜆𝐵)𝑥=0 for symmetric matrices of high order*, Comput. Methods Appl. Mech. Engrg.**3**(1974), no. 1, 11–28. MR**0381273**, https://doi.org/10.1016/0045-7825(74)90039-5**[20]**G. W. Stewart,*On the sensitivity of the eigenvalue problem 𝐴𝑥=𝜆𝐵𝑥*, SIAM J. Numer. Anal.**9**(1972), 669–686. MR**0311682**, https://doi.org/10.1137/0709056**[21]**David M. Young,*Iterative solution of large linear systems*, Academic Press, New York-London, 1971. MR**0305568****[22]**Amnon Bracha-Barak and Paul E. Saylor,*A symmetric factorization procedure for the solution of elliptic boundary value problems*, SIAM J. Numer. Anal.**10**(1973), 190–206. MR**0315876**, https://doi.org/10.1137/0710020**[23]**Paul Concus and Gene H. Golub,*Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations*, SIAM J. Numer. Anal.**10**(1973), 1103–1120. MR**0341890**, https://doi.org/10.1137/0710092**[24]**I. Shavitt, C. F. Bender, A. Pipano, and 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.**11**(1973), 90–108. MR**0339471****[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.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F15

Retrieve articles in all journals with MSC: 65F15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1974-0378378-X

Keywords:
Eigenvalues,
sparse matrices,
overrelaxation

Article copyright:
© Copyright 1974
American Mathematical Society