The Lanczos algorithm with partial reorthogonalization

Author:
Horst D. Simon

Journal:
Math. Comp. **42** (1984), 115-142

MSC:
Primary 65F10; Secondary 65F25

DOI:
https://doi.org/10.1090/S0025-5718-1984-0725988-X

MathSciNet review:
725988

Full-text 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****[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****[3]**G. Golub, R. Underwood & J. H. Wilkinson,*The Lanczos Algorithm for the Symmetric**Problem*, Tech. Rep. STAN-CS-72-720. 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 Urbana-Champaign, 1981.**[5]**David S. Kershaw,*The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations*, J. Comput. Phys.**26**(1978), no. 1, 43–65. MR**488669**, https://doi.org/10.1016/0021-9991(78)90098-0**[6]**Cornelius Lanczos,*Solution of systems of linear equations by minimized-iterations*, J. Research Nat. Bur. Standards**49**(1952), 33–53. MR**0051583****[7]**N. Munksgaard, "Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients."*ACM TOMS*, v. 6, 1980, pp. 206-219.**[8]**B. Nour-Omid,*A Newton-Lanczos Method for Solution of Nonlinear Finite Element Equations*, Report UCB/SESM-81/04, Dept. of Civil Engineering, University of California, Berkeley, 1981.**[9]**B. Nour-Omid, B. N. Parlett & R. Taylor, "Lanczos versus subspace iteration for the solution of eigenvalue problems,"*Internat. J. Numer. Methods Engrg.*, v. 19, 1983, pp. 859-871.**[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**334480****[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**501834****[13]**C. C. Paige,*Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem*, Linear Algebra Appl.**34**(1980), 235–258. MR**591433**, https://doi.org/10.1016/0024-3795(80)90167-6**[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**383715**, https://doi.org/10.1137/0712047**[15]**Beresford N. Parlett,*The symmetric eigenvalue problem*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR**570116****[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**, https://doi.org/10.1016/0024-3795(80)90248-7**[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**, https://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**, https://doi.org/10.1090/S0025-5718-1979-0514820-3**[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 PAM-74, 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****[22]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[23]**E. Wilson, private communication.**[24]**O. C. Zienkiewicz,*The Finite Element Method*, 3rd ed., McGraw-Hill, London, 1977.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F10,
65F25

Retrieve articles in all journals with MSC: 65F10, 65F25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0725988-X

Article copyright:
© Copyright 1984
American Mathematical Society