$\textrm {SOR}$-methods for the eigenvalue problem with large sparse matrices
HTML articles powered by AMS MathViewer
- by Axel Ruhe PDF
- Math. Comp. 28 (1974), 695-710 Request permission
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
- O. Axelsson, A generalized $\textrm {SSOR}$ method, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 443–467. MR 339467, DOI 10.1007/bf01932955
- W. W. Bradbury and R. Fletcher, New iterative methods for solution of the eigenproblem, Numer. Math. 9 (1966), 259–267. MR 219230, DOI 10.1007/BF02162089
- G. Buffoni, Evaluation of eigensolutions of discrete space diffusion equation, Calcolo 4 (1967), 169–177. MR 272166, DOI 10.1007/BF02576732
- 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
- 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 8 (1959), 107. MR 145689 D. K. Faddeev & V. N. Faddeeva, Computational Methods in Linear Algebra, Fizmatgiz, Moscow, 1960; English transl., Freeman, San Francisco, Calif., 1963. MR 28 #1742.
- 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 Isaac Fried, "Gradient methods for finite element eigenproblems," AIAA J., v. 7, 1969, pp. 739-741. M. Geradin, Analyse Dynamique Duale des Structures par la Méthode des Eléments Finis, Dissertation, Université de Liège, Belgium, 1972.
- G. H. Golub, Some uses of the Lanczos algorithm in numerical linear algebra, Topics in numerical analysis (Proc. Roy. Irish Acad. Conf., University Coll., Dublin, 1972) Academic Press, London, 1973, pp. 173–184. MR 0359289 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.
- 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, DOI 10.6028/jres.047.008 S. Holm, Coordinate Overrelaxation Methods for the Eigenproblem, Report UMINF-33.73, Department of Information Processing, Umeå, Sweden. W. Kahan, Relaxation Methods for an Eigenproblem, Technical Report CS-44, Computer Science Department, Stanford University, Stanford, California, 1966.
- 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, DOI 10.6028/jres.045.026
- 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
- C. C. Paige, Computational variants of the Lanczos method for the eigenproblem, J. Inst. Math. Appl. 10 (1972), 373–381. MR 334480, DOI 10.1093/imamat/10.3.373 A. Ruhe, Iterative Eigenvalue Algorithms for Large Symmetric Matrices, Report UMINF-31.72, Department of Information Processing, Umeå, Sweden.
- H. R. Schwarz, The eigenvalue problem $(A-\lambda B)x=0$ for symmetric matrices of high order, Comput. Methods Appl. Mech. Engrg. 3 (1974), no. 1, 11–28. MR 381273, DOI 10.1016/0045-7825(74)90039-5
- G. W. Stewart, On the sensitivity of the eigenvalue problem $Ax=\lambda Bx$, SIAM J. Numer. Anal. 9 (1972), 669–686. MR 311682, DOI 10.1137/0709056
- David M. Young, Iterative solution of large linear systems, Academic Press, New York-London, 1971. MR 0305568
- 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 315876, DOI 10.1137/0710020
- 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 341890, DOI 10.1137/0710092
- 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. Comput. Phys. 11 (1973), 90–108. MR 339471, DOI 10.1016/0021-9991(73)90149-6 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.
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 695-710
- MSC: Primary 65F15
- DOI: https://doi.org/10.1090/S0025-5718-1974-0378378-X
- MathSciNet review: 0378378