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.
