Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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, 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.
  • 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." 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.
  • 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, 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.
  • 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 Finite Element Method, 3rd ed., McGraw-Hill, 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
  • © 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