The Lanczos algorithm with partial reorthogonalization
Author:
Horst D. Simon
Journal:
Math. Comp. 42 (1984), 115142
MSC:
Primary 65F10; Secondary 65F25
MathSciNet review:
725988
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The Lanczos algorithm is becoming accepted as a powerful tool for finding the eigenvalues and for solving linear systems of equations. Any practical implementation of the algorithm suffers however from roundoff errors, which usually cause the Lanczos vectors to lose their mutual orthogonality. In order to maintain some level of orthogonality, full reorthogonalization (FRO) and selective orthogonalization (SO) have been used in the past as a remedy. Here partial reorthogonalization (PRO) is proposed as a new method for maintaining semiorthogonality among the Lanczos vectors. PRO is based on a simple recurrence, which allows us to monitor the loss of orthogonality among the Lanczos vectors directly without computing the inner products. Based on the information from the recurrence, reorthogonalizations occur only when necessary. Thus substantial savings are made as compared to FRO. In some numerical examples we apply the Lanczos algorithm with PRO to the solution of large symmetric systems of linear equations and show that it is a robust and efficient algorithm for maintaining semiorthogonality among the Lanczos vectors. The results obtained compare favorably with the conjugate gradient method.
 [1]
Jane
Cullum and Ralph
A. Willoughby, Lanczos and the computation in specified intervals
of the spectrum of large, sparse real symmetric matrices, Sparse
Matrix Proceedings 1978 (Sympos. Sparse Matrix Comput., Knoxville, Tenn.,
1978) SIAM, Philadelphia, Pa., 1979, pp. 220–255. MR 566378
(81m:15007)
 [2]
Jane
Cullum and Ralph
A. Willoughby, Computing eigenvectors (and eigenvalues) of large,
symmetric matrices using Lanczos tridiagonalization, Numerical
analysis (Proc. 8th Biennial Conf., Univ. Dundee, Dundee, 1979), Lecture
Notes in Math., vol. 773, Springer, Berlin, 1980,
pp. 46–63. MR 569461
(81h:65032)
 [3]
G. Golub, R. Underwood & J. H. Wilkinson, The Lanczos Algorithm for the Symmetric Problem, Tech. Rep. STANCS72720. Comp. Sci. Dept., Stanford University, 1972.
 [4]
J. Grcar, Analyses of the Lanczos Algorithm and of the Approximation Problem in Richardson's Method, Ph.D. thesis, University of Illinois at UrbanaChampaign, 1981.
 [5]
David
S. Kershaw, The incomplete Choleskyconjugate gradient method for
the iterative solution of systems of linear equations, J.
Computational Phys. 26 (1978), no. 1, 43–65. MR 0488669
(58 #8190)
 [6]
Cornelius
Lanczos, Solution of systems of linear equations by
minimizediterations, J. Research Nat. Bur. Standards
49 (1952), 33–53. MR 0051583
(14,501g)
 [7]
N. Munksgaard, "Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients." ACM TOMS, v. 6, 1980, pp. 206219.
 [8]
B. NourOmid, A NewtonLanczos Method for Solution of Nonlinear Finite Element Equations, Report UCB/SESM81/04, Dept. of Civil Engineering, University of California, Berkeley, 1981.
 [9]
B. NourOmid, B. N. Parlett & R. Taylor, "Lanczos versus subspace iteration for the solution of eigenvalue problems," Internat. J. Numer. Methods Engrg., v. 19, 1983, pp. 859871.
 [10]
C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph.D. Thesis, Univ. of London, 1971.
 [11]
C.
C. Paige, Computational variants of the Lanczos method for the
eigenproblem, J. Inst. Math. Appl. 10 (1972),
373–381. MR 0334480
(48 #12799)
 [12]
C.
C. Paige, Error analysis of the Lanczos algorithm for
tridiagonalizing a symmetric matrix, J. Inst. Math. Appl.
18 (1976), no. 3, 341–349. MR 0501834
(58 #19082)
 [13]
C.
C. Paige, Accuracy and effectiveness of the Lanczos algorithm for
the symmetric eigenproblem, Linear Algebra Appl. 34
(1980), 235–258. MR 591433
(82b:65025), http://dx.doi.org/10.1016/00243795(80)901676
 [14]
C.
C. Paige and M.
A. Saunders, Solutions of sparse indefinite systems of linear
equations, SIAM J. Numer. Anal. 12 (1975),
no. 4, 617–629. MR 0383715
(52 #4595)
 [15]
Beresford
N. Parlett, The symmetric eigenvalue problem, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1980. PrenticeHall Series in Computational
Mathematics. MR
570116 (81j:65063)
 [16]
B.
N. Parlett, A new look at the Lanczos algorithm for solving
symmetric systems of linear equations, Linear Algebra Appl.
29 (1980), 323–346. MR 562767
(83e:65064), http://dx.doi.org/10.1016/00243795(80)902487
 [17]
B.
N. Parlett and J.
K. Reid, Tracking the progress of the Lanczos algorithm for large
symmetric eigenproblems, IMA J. Numer. Anal. 1
(1981), no. 2, 135–155. MR 616327
(82e:65039), http://dx.doi.org/10.1093/imanum/1.2.135
 [18]
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
 [19]
D. S. Scott, Analysis of the Symmetric Lanczos Process, Ph.D. thesis, Dept. of Math., University of California, Berkeley, 1978.
 [20]
H. D. Simon, The Lanczos Algorithm for Solving Symmetric Linear Systems, Report PAM74, Center for Pure and Appl. Math., Univ. of California, Berkeley, 1982.
 [21]
Hidetosi
Takahasi and Makoto
Natori, Eigenvalue problem of large sparse matrices, Rep.
Comput. Centre Univ. Tokyo 4 (1971/72), 129–148. MR 0362871
(50 #15309)
 [22]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [23]
E. Wilson, private communication.
 [24]
O. C. Zienkiewicz, The Finite Element Method, 3rd ed., McGrawHill, London, 1977.
 [1]
 J. Cullum & R. Willoughby, "Lanczos and the computation in specified intervals of the spectrum of large sparse real symmetric matrices," in Sparse Matrix Proceedings (I. Duff and G. W. Stewart, eds.), SIAM, Philadelphia, Pa., 1979. MR 566378 (81m:15007)
 [2]
 J. Cullum & R. Willoughby, "Computing eigenvectors and eigenvalues of large sparse symmetric matrices using Lanczos tridiagonalization," in Numerical Analysis Proceedings, Dundee 1979 (G A. Watson, ed.), SpringerVerlag, Berlin, 1980. MR 569461 (81h:65032)
 [3]
 G. Golub, R. Underwood & J. H. Wilkinson, The Lanczos Algorithm for the Symmetric Problem, Tech. Rep. STANCS72720. Comp. Sci. Dept., Stanford University, 1972.
 [4]
 J. Grcar, Analyses of the Lanczos Algorithm and of the Approximation Problem in Richardson's Method, Ph.D. thesis, University of Illinois at UrbanaChampaign, 1981.
 [5]
 D. S. Kershaw, "The incomplete Choleskiconjugate gradient method for the iterative solution of systems of linear equations," J. Comput. Phys., v. 24, 1978, pp. 4365. MR 0488669 (58:8190)
 [6]
 C. Lanczos, "Solution of systems of linear equations by minimized iterations," J. Res. Nat. Bur. Standards, v. 49, 1952, pp. 3353. MR 0051583 (14:501g)
 [7]
 N. Munksgaard, "Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients." ACM TOMS, v. 6, 1980, pp. 206219.
 [8]
 B. NourOmid, A NewtonLanczos Method for Solution of Nonlinear Finite Element Equations, Report UCB/SESM81/04, Dept. of Civil Engineering, University of California, Berkeley, 1981.
 [9]
 B. NourOmid, B. N. Parlett & R. Taylor, "Lanczos versus subspace iteration for the solution of eigenvalue problems," Internat. J. Numer. Methods Engrg., v. 19, 1983, pp. 859871.
 [10]
 C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph.D. Thesis, Univ. of London, 1971.
 [11]
 C. Paige, "Computational variants of the Lanczos method for the eigenproblem," J. Inst. Math. Appl., v. 10, 1972, pp. 373381. MR 0334480 (48:12799)
 [12]
 C. Paige, "Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix," J. Inst. Math. Appl., v. 18, 1976, pp. 341349. MR 0501834 (58:19082)
 [13]
 C. Paige, "Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem," Linear Algebra Appl., v. 34, 1980, pp. 235258. MR 591433 (82b:65025)
 [14]
 C. Paige & M. Saunders, "Solution of sparse indefinite systems of linear equations," SI AM J. Numer. Anal., v. 12, 1975, pp. 617629. MR 0383715 (52:4595)
 [15]
 B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, N. J., 1980. MR 570116 (81j:65063)
 [16]
 B. N. Parlett, "A new look at the Lanczos algorithm for solving symmetric systems of linear equations," Linear Algebra Appl., v. 29, 1980, pp. 323346. MR 562767 (83e:65064)
 [17]
 B. N. Parlett & J. K. Reid, "Tracking the progress of the Lanczos algorithm for large symmetric eigenproblems," IMA J. Numer. Anal., v. 1, 1981, pp. 135155. MR 616327 (82e:65039)
 [18]
 B. N. Parlett & D. Scott, "The Lanczos algorithm with selective orthogonalization," Math. Comp., v. 33, 1979, pp. 217238. MR 514820 (80c:65090)
 [19]
 D. S. Scott, Analysis of the Symmetric Lanczos Process, Ph.D. thesis, Dept. of Math., University of California, Berkeley, 1978.
 [20]
 H. D. Simon, The Lanczos Algorithm for Solving Symmetric Linear Systems, Report PAM74, Center for Pure and Appl. Math., Univ. of California, Berkeley, 1982.
 [21]
 H. Takahasi & M. Natori, Eigenvalue Problem of Large Sparse Matrices, Rep. Comp Center, Univ. Tokyo, No. 4, 19711972, pp. 129148. MR 0362871 (50:15309)
 [22]
 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 0184422 (32:1894)
 [23]
 E. Wilson, private communication.
 [24]
 O. C. Zienkiewicz, The Finite Element Method, 3rd ed., McGrawHill, London, 1977.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F10,
65F25
Retrieve articles in all journals
with MSC:
65F10,
65F25
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819840725988X
PII:
S 00255718(1984)0725988X
Article copyright:
© Copyright 1984
American Mathematical Society
