Thick-Restart Lanczos Method for Large Symmetric Eigenvalue Problems

By Kesheng Wu, Horst D. Simon. SIAM Journal on Matrix Analysis and Applications, 2000

309 citations recorded by the source corpus.

In this paper, we propose a restarted variant of the Lanczos method for symmetric eigenvalue problems named the thick-restart Lanczos method. This new variant is able to retain an arbitrary number of Ritz vectors from the previous iterations with a minimal restarting cost. Since it restarts with Ritz vectors, it is simpler than similar methods, such as the implicitly restarted Lanczos method. We carefully examine the effects of the floating-point round-off errors on stability of the new algorithm and present an implementation of the partial reorthogonalization scheme that guarantees accurate Ritz values with a minimal amount of reorthogonalization. We also show a number of heuristics on deciding which Ritz pairs to save during restart in order to maximize the overall performance of the thick-restart Lanczos method.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/0ecfd2048fe0786ee706dde097e4eb6bf66b8aa8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Restarted block-GMRES with deflation of eigenvalues (2005, methodology): “A mathematically equivalent method, called GMRES with deflated restarting (GMRES-DR) [26], is also related to Wu and Simon’s restarted Lanczos eigenvalue method [ 49 ].”
Recycling Krylov Subspaces for Sequences of Linear Systems (2006, methodology): “Finally, we note that GCRO-DR uses more or less the Arnoldi method with dense restarting for approximating an invariant subspace [33, 38].”
SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems (2005, methodology): “Other available libraries are BLZPACK [Marques 1995], PLANSO [Wu and Simon 1997], and TRLAN [Wu and Simon 2001], which implement different .avors of the Lanczos method.”
Efficient, high-quality image contour detection (2009, methodology): “We found MATLAB's eigensolver performed similarly to TRLan [18] on Normalized Cuts prob- lems.”
Handbook of Big Data (2016, methodology): “Wu and Simon [33] described an eigenvalue method called the thick-restarted Lanczos tridiagonalization, which is simple to implement”
A Krylov–Schur approach to the truncated SVD (2012, methodology): “When one is interested in a small number of eigenvalues, restarted methods such as the implicitly restarted Arnoldi process are the methods of choice, see [27] [28] [33] [3] [29] for more details.”
A Krylov-Schur Algorithm for Large Eigenproblems (2001, methodology): “When A is Hermitian, the Krylov–Schur method becomes a restarted Lanczos algorithm—in fact the algorithm of Wu and Simon [18].”
A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity (2006, background): “It is a generalization of Wu and Simon’s thick-restart Lanczos [24].”