The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems
Authors:
Thomas Ericsson and Axel Ruhe
Journal:
Math. Comp. 35 (1980), 12511268
MSC:
Primary 65F15; Secondary 15A18, 65N30
MathSciNet review:
583502
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A new algorithm is developed which computes a specified number of eigenvalues in any part of the spectrum of a generalized symmetric matrix eigenvalue problem. It uses a linear system routine (factorization and solution) as a tool for applying the Lanczos algorithm to a shifted and inverted problem. The algorithm determines a sequence of shifts and checks that all eigenvalues get computed in the intervals between them. It is shown that for each shift several eigenvectors will converge after very few steps of the Lanczos algorithm, and the most effective combination of shifts and Lanczos runs is determined for different sizes and sparsity properties of the matrices. For large problems the operation counts are about five times smaller than for traditional subspace iteration methods. Tests on a numerical example, arising from a finite element computation of a nuclear power piping system, are reported, and it is shown how the performance predicted bears out in a practical situation.
 [1]
T. J. A. AGAR &. A. JENNINGS, Hybrid Sturm Sequence and Simultaneous Iteration Methods, Internat. Sympos. Appl. of Computer Methods in Engineering, Univ. of Southern California, Los Angeles, Calif., 1977, pp. 405412.
 [2]
J.
H. Argyris, Th.
L. Johnsen, R.
A. Rosanoff, and J.
R. Roy, On numerical error in the finite element method,
Comput. Methods Appl. Mech. Engrg. 7 (1976), no. 2,
261–282. MR 0657963
(58 #31902)
 [3]
K. J. BATHE & E. L. WILSON, Numerical Methods in Finite Element Analysis, PrenticeHall, Englewood Cliffs, N.J., 1976.
 [4]
James
R. Bunch and Linda
Kaufman, Some stable methods for calculating
inertia and solving symmetric linear systems, Math. Comp. 31 (1977), no. 137, 163–179. MR 0428694
(55 #1714), http://dx.doi.org/10.1090/S00255718197704286940
 [5]
J.
Alan George, Solution of linear systems of equations: direct
methods for finite element problems, Sparse matrix techniques (Adv.
Course, Technical Univ. Denmark, Copenhagen, 1976) Springer, Berlin,
1977, pp. 52–101. Lecture Notes in Math., Vol. 572. MR 0440883
(55 #13751)
 [6]
Paul
S. Jensen, The solution of large symmetric eigenproblems by
sectioning, SIAM J. Numer. Anal. 9 (1972),
534–545. MR 0315880
(47 #4429)
 [7]
C.
C. Paige, Practical use of the symmetric Lanczos process with
reorthogonalization, Nordisk Tidskr. Informationsbehandling (BIT)
10 (1970), 183–195. MR 0264839
(41 #9430)
 [8]
C.
C. Paige, Computational variants of the Lanczos method for the
eigenproblem, J. Inst. Math. Appl. 10 (1972),
373–381. MR 0334480
(48 #12799)
 [9]
Beresford
N. Parlett, The symmetric eigenvalue problem, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1980. PrenticeHall Series in Computational
Mathematics. MR
570116 (81j:65063)
 [10]
B.
N. Parlett and D.
S. Scott, The Lanczos algorithm with selective
orthogonalization, Math. Comp.
33 (1979), no. 145, 217–238. MR 514820
(80c:65090), http://dx.doi.org/10.1090/S00255718197905148203
 [11]
Axel
Ruhe, Computation of eigenvalues and eigenvectors, Sparse
matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976)
Springer, Berlin, 1977, pp. 130–184. Lecture Notes in Math.,
Vol. 572. MR
0440891 (55 #13759)
 [12]
B. T. SMITH ET AL., Matrix Eigensystem Routines EISPACK Guide, Lecture Notes in Comput. Sci., Vol. 6 and Vol. 51, SpringerVerlag, Berlin and New York, 1974, 1977.
 [13]
Gilbert
Strang and George
J. Fix, An analysis of the finite element method,
PrenticeHall, Inc., Englewood Cliffs, N. J., 1973. PrenticeHall Series in
Automatic Computation. MR 0443377
(56 #1747)
 [14]
R. UNDERWOOD, An Iterative Block Lanczos Method for the Solution of Large Sparse Symmetric Eigenproblems, Tech. Report STANCS75496, Stanford University, Stanford, Calif., 1975.
 [15]
Handbook for automatic computation. Vol. II, SpringerVerlag, New
YorkHeidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C.
Reinsch; Die Grundlehren der Mathematischen Wissenschaften, Band 186. MR 0461856
(57 #1840)
 [1]
 T. J. A. AGAR &. A. JENNINGS, Hybrid Sturm Sequence and Simultaneous Iteration Methods, Internat. Sympos. Appl. of Computer Methods in Engineering, Univ. of Southern California, Los Angeles, Calif., 1977, pp. 405412.
 [2]
 J. H. ARGYRIS, T.L. JOHNSEN, R. A. ROSANOFF & J. R. ROY, "On numerical error in the finite element method," Comput. Methods Appl. Mech. Engrg., v. 7, 1976, pp. 261282. MR 0657963 (58:31902)
 [3]
 K. J. BATHE & E. L. WILSON, Numerical Methods in Finite Element Analysis, PrenticeHall, Englewood Cliffs, N.J., 1976.
 [4]
 J. R. BUNCH & L. KAUFMAN, "Some stable methods for calculating inertia and solving symmetric linear systems," Math. Comp., v. 31, 1977, pp. 163179. MR 0428694 (55:1714)
 [5]
 J. A. GEORGE, "Solution of linear systems of equations: Direct methods for finite element problems," Sparse Matrix Techniques (V. A. Barker, Ed.), Lecture Notes in Math., Vol. 572, SpringerVerlag, Berlin and New York, 1977, pp. 52101. MR 0440883 (55:13751)
 [6]
 P. S. JENSEN, "The solution of large symmetric eigenproblems by sectioning," SIAM J. Numer. Anal., v. 9, 1972, pp. 534545. MR 0315880 (47:4429)
 [7]
 C. C. PAIGE, "Practical use of the symmetric Lanczos process with reorthogonalization," BIT, v. 10, 1970, pp. 183195. MR 0264839 (41:9430)
 [8]
 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)
 [9]
 B. N. PARLETT, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, N.J., 1980. MR 570116 (81j:65063)
 [10]
 B. N. PARLETT & D. S. SCOTT, "The Lanczos algorithm with selective orthogonalization," Math. Comp., v. 33, 1979, pp. 217238. MR 514820 (80c:65090)
 [11]
 A. RUHE, "Computation of eigenvalues and eigenvectors," in Sparse Matrix Techniques, (V. A. Barker, Ed.), Lecture Notes in Math., Vol. 572, SpringerVerlag, Berlin and New York, 1977, pp. 130184. MR 0440891 (55:13759)
 [12]
 B. T. SMITH ET AL., Matrix Eigensystem Routines EISPACK Guide, Lecture Notes in Comput. Sci., Vol. 6 and Vol. 51, SpringerVerlag, Berlin and New York, 1974, 1977.
 [13]
 G. STRANG & G. J. FIX, An Analysis of the Finite Element Method, PrenticeHall, Englewood Cliffs, N.J., 1973. MR 0443377 (56:1747)
 [14]
 R. UNDERWOOD, An Iterative Block Lanczos Method for the Solution of Large Sparse Symmetric Eigenproblems, Tech. Report STANCS75496, Stanford University, Stanford, Calif., 1975.
 [15]
 J. H. WILKINSON & C. REINSCH (Eds.), Handbook for Automatic Computation, Vol. II, Linear Algebra, SpringerVerlag, Berlin and New York, 1971. MR 0461856 (57:1840)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F15,
15A18,
65N30
Retrieve articles in all journals
with MSC:
65F15,
15A18,
65N30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005835022
PII:
S 00255718(1980)05835022
Article copyright:
© Copyright 1980
American Mathematical Society
