Iterative eigenvalue solutions-lanczos algorithm for symmetric matrices

Abstract

Lanczos algorithm is an effective tool for constructing an approximate tridiagonalization of a symmetric matrix. The basic procedure creates a set of vectors and makes them orthogonal to create an orthonormal basis of the Krylov subspace. While the original formulation failed in finite precision, subsequent modification where one reorthogonalized the set of vectors is quite stable. In its current form, it is known for its efficiency in computing a subset of eigenvalues and eigenvectors for large sparse symmetric matrices via this tridiagonal representation. This thesis revisits the Lanczos algorithm and its behavior in finite precision. The starting point is a well-known observation that the Lanczos method fails when few of the eigenvalues converges. At that point, the vectors lose orthogonality and the method produces spurious eigenvalues. Furthermore, it is also known that larger the spectral gap, faster such failure occurs. This failure is typically circumvented via reorthogonalization of the Lanczos vectors. In this thesis, it is shown that augmenting the original matrix is an effective way to reduce the spectral gap and thus slow down considerably the emergence of spurious eigenvalues. It is shown that the new approach of augmented matrix leads to a stable scheme and thus provides an alternate way to think about Lanczos and other Krylov subspace-based methods in finite precision.