Electronic Transactions on Numerical Analysis (ETNA)

Volume 2, pp. 1-21, 1994.

An implicitly restarted Lanczos method for large symmetric eigenvalue problems

D. Calvetti, L. Reichel, and D. C. Sorensen

Abstract

The Lanczos process is a well known technique for computing a few, say $k$ , eigenvalues and associated eigenvectors of a large symmetric $n \times n$ matrix. However, loss of orthogonality of the computed Krylov subspace basis can reduce the accuracy of the computed approximate eigenvalues. In the implicitly restarted Lanczos method studied in the present paper, this problem is addressed by fixing the number of steps in the Lanczos process at a prescribed value, $k + p$ , where $p$ typically is not much larger, and may be smaller, than $k$ . Orthogonality of the $k + p$ basis vectors of the Krylov subspace is secured by reorthogonalizing these vectors when necessary. The implicitly restarted Lanczos method exploits that the residual vector obtained by the Lanczos process is a function of the initial Lanczos vector. The method updates the initial Lanczos vector through an iterative scheme. The purpose of the iterative scheme is to determine an initial vector such that the associated residual vector is tiny. If the residual vector vanishes, then an invariant subspace has been found. This paper studies several iterative schemes, among them schemes based on Leja points. The resulting algorithms are capable of computing a few of the largest or smallest eigenvalues and associated eigenvectors. This is accomplished using only $(k + p) n + O ((k + p)^{2})$ storage locations in addition to the storage required for the matrix, where the second term is independent of $n$ .

Full Text (PDF) [270 KB], BibTeX

Key words

Lanczos method, eigenvalue, polynomial acceleration.

AMS subject classifications

65F15.

ETNA articles which cite this article

Vol. 7 (1998), pp. 124-140 J. Baglama, D. Calvetti, and L. Reichel: Fast Leja points

Vol. 7 (1998), pp. 163-181 Andreas Stathopoulos and Yousef Saad: Restarting techniques for the (Jacobi-)Davidson symmetric eigenvalue methods

Vol. 45 (2016), pp. 16-32 Alex Breuer: New filtering strategies for implicitly restarted Lanczos iteration

Vol. 46 (2017), pp. 215-232 Moritz August, Mari Carmen Bañuls, and Thomas Huckle: On the approximation of functionals of very large Hermitian matrices represented as matrix product operators

< Vol. 2 (1994)