Restarting the Arnoldi Method

An unfortunate aspect of the Lanczos/Arnoldi process is that one cannot know in advance how many steps will be required before eigenvalues of interest are well approximated by the Ritz values. This is particularly true when the problem has a wide range of eigenvalues but the eigenvalues of interest are clustered. Without a spectral transformation, many Lanczos steps are required to obtain the selected eigenvalues. In order to recover eigenvectors, one is obliged either to store all of the Lanczos basis vectors (usually on a peripheral device) or to re-compute them. Also, very large tridiagonal eigenvalue problems will have to be solved at each step. In the Arnoldi process that is used in the non-Hermitian case, not only do the basis vectors have to be stored, but the cost of the Hessenberg eigenvalue subproblem is at the k-th step. The obvious need to control this cost has motivated the development of restarting schemes.