Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

The Lanczos algorithm with selective orthogonalization


Authors: B. N. Parlett and D. S. Scott
Journal: Math. Comp. 33 (1979), 217-238
MSC: Primary 65F15
MathSciNet review: 514820
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The simple Lanczos process is very effective for finding a few extreme eigenvalues of a large symmetric matrix along with the associated eigenvectors. Unfortunately, the process computes redundant copies of the outermost eigenvectors and has to be used with some skill. In this paper it is shown how a modification called selective orthogonalization stifles the formation of duplicate eigenvectors without increasing the cost of a Lanczos step significantly. The degree of linear independence among the Lanczos vectors is controlled without the costly process of reorthogonalization.


References [Enhancements On Off] (What's this?)

  • [A] K. CLINE, G. H. GOLUB & G. W. PLATZMAN, "Calculation of normal modes of oceans using a Lanczos method" in Sparse Matrix Computations (J. Bunch and D. Rose, Editors), Academic Press, New York, 1976.
  • [J] CULLUM & W. E. DONATH, A Block Generalization of the Symmetric s-step Lanczos Algorithm, Report #RC 4845 (#21570), IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1974.
  • [C] Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 0264450
  • [G] H. GOLUB, R. UNDERWOOD & J. H. WILKINSON, The Lanczos Algorithm for the Symmetric $ Ax = \lambda Bx$ Problem, Technical Report STAN-CS-72-270, Computer Science Department, Stanford University, 1972.
  • [W] KAHAN, Inclusion Theorems for Clusters of Eigenvalues of Hermitian Matrices, Computer Science Report, University of Toronto, Toronto, Canada, 1967.
  • [W] KAHAN & B. PARLETT, An Analysis of Lanczos Algorithms for Symmetric Matrices, Electronics Research Memorandum ERL-M467, University of California, 1974.
  • [W] W. Kahan and B. N. Parlett, How far should you go with the Lanczos process?, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 131–144. MR 0458836
  • [S] Shmuel Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369–378. MR 0234618, 10.1090/S0025-5718-1966-0234618-4
  • [C] Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 0042791
  • [J] LEWIS, Algorithms for Sparse Matrix Eigenvalue Problems, Technical Report STAN-CS77-595, Computer Science Department, Stanford University, 1977.
  • [C] C. PAIGE, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph. D. Thesis, University of London, 1971.
  • [C] C. C. Paige, Computational variants of the Lanczos method for the eigenproblem, J. Inst. Math. Appl. 10 (1972), 373–381. MR 0334480
  • [C] 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
  • [R] UNDERWOOD, An Iterative Block Lanczos Method for the Solution of Large Sparse-Symmetric Eigenproblems, Ph. D. Thesis, Stanford University, STAN-CS-75-496, 1975.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F15

Retrieve articles in all journals with MSC: 65F15


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1979-0514820-3
Keywords: Eigenvalues, eigenvectors, symmetric matrices, Lanczos method
Article copyright: © Copyright 1979 American Mathematical Society