## The Lanczos algorithm with partial reorthogonalization

HTML articles powered by AMS MathViewer

- by Horst D. Simon PDF
- Math. Comp.
**42**(1984), 115-142 Request permission

## 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.

## References

- 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** - 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**
G. Golub, R. Underwood & J. H. Wilkinson, - 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**, DOI 10.1016/0021-9991(78)90098-0 - Cornelius Lanczos,
*Solution of systems of linear equations by minimized-iterations*, J. Research Nat. Bur. Standards**49**(1952), 33–53. MR**0051583**
N. Munksgaard, "Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients." - C. C. Paige,
*Computational variants of the Lanczos method for the eigenproblem*, J. Inst. Math. Appl.**10**(1972), 373–381. MR**334480** - 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** - C. C. Paige,
*Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem*, Linear Algebra Appl.**34**(1980), 235–258. MR**591433**, DOI 10.1016/0024-3795(80)90167-6 - 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**, DOI 10.1137/0712047 - Beresford N. Parlett,
*The symmetric eigenvalue problem*, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR**570116** - 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**, DOI 10.1016/0024-3795(80)90248-7 - 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**, DOI 10.1093/imanum/1.2.135 - B. N. Parlett and D. S. Scott,
*The Lanczos algorithm with selective orthogonalization*, Math. Comp.**33**(1979), no. 145, 217–238. MR**514820**, DOI 10.1090/S0025-5718-1979-0514820-3
D. S. Scott, - Hidetosi Takahasi and Makoto Natori,
*Eigenvalue problem of large sparse matrices*, Rep. Comput. Centre Univ. Tokyo**4**(1971/72), 129–148. MR**362871** - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**
E. Wilson, private communication.
O. C. Zienkiewicz,

*The Lanczos Algorithm for the Symmetric*$Ax = \lambda Bx$

*Problem*, Tech. Rep. STAN-CS-72-720. Comp. Sci. Dept., Stanford University, 1972. 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.

*ACM TOMS*, v. 6, 1980, pp. 206-219. 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. 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. C. Paige,

*The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices*, Ph.D. Thesis, Univ. of London, 1971.

*Analysis of the Symmetric Lanczos Process*, Ph.D. thesis, Dept. of Math., University of California, Berkeley, 1978. 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.

*The Finite Element Method*, 3rd ed., McGraw-Hill, London, 1977.

## Additional Information

- © Copyright 1984 American Mathematical Society
- 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