The Lanczos algorithm with selective orthogonalization

Authors:
B. N. Parlett and D. S. Scott

Journal:
Math. Comp. **33** (1979), 217-238

MSC:
Primary 65F15

DOI:
https://doi.org/10.1090/S0025-5718-1979-0514820-3

MathSciNet review:
514820

Full-text PDF

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.

**[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]**DAVIS & W. KAHAN, "The rotation of eigenvectors by a perturbation. III,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 1-46. MR**0264450 (41:9044)****[G]**H. GOLUB, R. UNDERWOOD & J. H. WILKINSON,*The Lanczos Algorithm for the Symmetric**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]**KAHAN & B. PARLETT, "How far should you go with the Lanczos Algorithm?" in*Sparse Matrix Computations*(J. Bunch and D. Rose, Editors), Academic Press, New York, 1976. MR**0458836 (56:17036)****[S]**KANIEL, "Estimates for some computational techniques in linear algebra,"*Math. Comp.*, v. 20, 1966, pp. 369-378. MR**0234618 (38:2934)****[C]**LANCZOS, "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,"*J. Res. Nat. Bur. Standards*, v. 45, 1950, pp. 255-282. MR**0042791 (13:163d)****[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. PAIGE, "Computational variants of the Lanczos method for the eigenproblem,"*J. Inst. Math. Appl.*, v. 10, 1972, pp. 373-381. MR**0334480 (48:12799)****[C]**C. PAIGE, "Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix,"*J. Inst. Math. Appl.*, v. 18, 1976, pp. 341-349. MR**0501834 (58:19082)****[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.

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