The Lanczos algorithm with selective orthogonalization
Authors:
B. N. Parlett and D. S. Scott
Journal:
Math. Comp. 33 (1979), 217238
MSC:
Primary 65F15
DOI:
https://doi.org/10.1090/S00255718197905148203
MathSciNet review:
514820
Fulltext 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.

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.
CULLUM & W. E. DONATH, A Block Generalization of the Symmetric sstep Lanczos Algorithm, Report #RC 4845 (#21570), IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1974.
 Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI https://doi.org/10.1137/0707001 H. GOLUB, R. UNDERWOOD & J. H. WILKINSON, The Lanczos Algorithm for the Symmetric $Ax = \lambda Bx$ Problem, Technical Report STANCS72270, Computer Science Department, Stanford University, 1972. KAHAN, Inclusion Theorems for Clusters of Eigenvalues of Hermitian Matrices, Computer Science Report, University of Toronto, Toronto, Canada, 1967. KAHAN & B. PARLETT, An Analysis of Lanczos Algorithms for Symmetric Matrices, Electronics Research Memorandum ERLM467, University of California, 1974.
 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
 Shmuel Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369–378. MR 234618, DOI https://doi.org/10.1090/S00255718196602346184
 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 LEWIS, Algorithms for Sparse Matrix Eigenvalue Problems, Technical Report STANCS77595, Computer Science Department, Stanford University, 1977. C. PAIGE, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph. D. Thesis, University 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 UNDERWOOD, An Iterative Block Lanczos Method for the Solution of Large SparseSymmetric Eigenproblems, Ph. D. Thesis, Stanford University, STANCS75496, 1975.
Retrieve articles in Mathematics of Computation with MSC: 65F15
Retrieve articles in all journals with MSC: 65F15
Additional Information
Keywords:
Eigenvalues,
eigenvectors,
symmetric matrices,
Lanczos method
Article copyright:
© Copyright 1979
American Mathematical Society