methods for the eigenvalue problem with large sparse matrices
Author:
Axel Ruhe
Journal:
Math. Comp. 28 (1974), 695710
MSC:
Primary 65F15
MathSciNet review:
0378378
Fulltext PDF Free Access
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 twocyclic (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 cg or Lanczos algorithms should be preferred.
 [1]
O.
Axelsson, A generalized 𝑆𝑆𝑂𝑅
method, Nordisk Tidskr. Informationsbehandling (BIT)
12 (1972), 443–467. MR 0339467
(49 #4226)
 [2]
W.
W. Bradbury and R.
Fletcher, New iterative methods for solution of the
eigenproblem, Numer. Math. 9 (1966), 259–267.
MR
0219230 (36 #2313)
 [3]
G.
Buffoni, Evaluation of eigensolutions of discrete space diffusion
equation, Calcolo 4 (1967), 169–177. MR 0272166
(42 #7047)
 [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) NorthHolland, Amsterdam, 1972, pp. 1240–1245. MR 0458821
(56 #17021)
 [5]
M.
Engeli, Th.
Ginsburg, H.
Rutishauser, and E.
Stiefel, Refined iterative methods for computation of the solution
and the eigenvalues of selfadjoint boundary value problems, Mitt.
Inst. Angew. Math. Zürich. No. 8 (1959), 107. 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]
George
E. Forsythe and Wolfgang
R. Wasow, Finitedifference methods for partial differential
equations, Applied Mathematics Series, John Wiley & Sons, Inc.,
New YorkLondon, 1960. MR 0130124
(23 #B3156)
 [8]
Isaac Fried, "Gradient methods for finite element eigenproblems," AIAA J., v. 7, 1969, pp. 739741.
 [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
(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. 4152.
 [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,283d)
 [13]
S. Holm, Coordinate Overrelaxation Methods for the Eigenproblem, Report UMINF33.73, Department of Information Processing, Umeå, Sweden.
 [14]
W. Kahan, Relaxation Methods for an Eigenproblem, Technical Report CS44, 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
(13,163d)
 [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
(43 #4242)
 [17]
C.
C. Paige, Computational variants of the Lanczos method for the
eigenproblem, J. Inst. Math. Appl. 10 (1972),
373–381. MR 0334480
(48 #12799)
 [18]
A. Ruhe, Iterative Eigenvalue Algorithms for Large Symmetric Matrices, Report UMINF31.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
(52 #2170)
 [20]
G.
W. Stewart, On the sensitivity of the eigenvalue problem
𝐴𝑥=𝜆𝐵𝑥, SIAM J. Numer. Anal.
9 (1972), 669–686. MR 0311682
(47 #244)
 [21]
David
M. Young, Iterative solution of large linear systems, Academic
Press, New YorkLondon, 1971. MR 0305568
(46 #4698)
 [22]
Amnon
BrachaBarak 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
(47 #4425)
 [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
(49 #6636)
 [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 (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. 121134.
 [1]
 O. Axelsson, "A generalized SSOR method," Nordisk Tidskr. Informationsbehandling (BIT), v. 13, 1972, pp. 443467. MR 0339467 (49:4226)
 [2]
 W. W. Bradbury & R. Fletcher, "New iterative methods for solution of the eigenproblem," Numer. Math., v. 9, 1966, pp. 259267. MR 36 # 2313. MR 0219230 (36:2313)
 [3]
 G. Buffoni, "Evaluation of eigensolutions of discrete space diffusion equation," Calcolo, v. 4, 1967, pp. 169177. 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.), NorthHolland, 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 selfadjoint 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, FiniteDifference 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. 739741.
 [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. 173184. 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. 4152.
 [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. 4561. MR 13, 283. MR 0043552 (13:283d)
 [13]
 S. Holm, Coordinate Overrelaxation Methods for the Eigenproblem, Report UMINF33.73, Department of Information Processing, Umeå, Sweden.
 [14]
 W. Kahan, Relaxation Methods for an Eigenproblem, Technical Report CS44, 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. 255282. 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. 122143. 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. 373381. MR 0334480 (48:12799)
 [18]
 A. Ruhe, Iterative Eigenvalue Algorithms for Large Symmetric Matrices, Report UMINF31.72, Department of Information Processing, Umeå, Sweden.
 [19]
 H. R. Schwarz, "The eigenvalue problem for symmetric matrices of high order," Comp. Meth. Appl. Mech. Engnrg., v. 3, 1974, pp. 1128. MR 0381273 (52:2170)
 [20]
 G. W. Stewart, "On the sensitivity of the eigenvalue problem ," SIAM J. Numer. Anal., v. 9, 1972, pp. 669686. 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. BrachaBarak & P. E. Saylor, "A symmetric factorization procedure for the solution of elliptic boundary value problems," SIAM J. Numer. Anal., v. 10, 1973, pp. 190206. 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. 11031120. 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. 90108. 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. 121134.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F15
Retrieve articles in all journals
with MSC:
65F15
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819740378378X
PII:
S 00255718(1974)0378378X
Keywords:
Eigenvalues,
sparse matrices,
overrelaxation
Article copyright:
© Copyright 1974
American Mathematical Society
