IMPLICITLY RESTARTED KRYLOV SUBSPACE METHODS FOR LARGE-SCALE LEAST-SQUARES PROBLEMS

The LSQR algorithm is a popular Krylov subspace method for obtaining solutions to large-scale least-squares problems. For some matrices, however, LSQR may require a prohibitively large number of iterations to determine an approximate solution within a desired accuracy. This is often the case when the solution vector has large components in the direction of the singular vectors associated with the smallest singular values of the matrix. This dissertation describes how the Krylov subspaces generated from LSQR can be conveniently updated to contain good approximations to the singular vectors corresponding to the smallest singular values of the matrix. The updates can be carried out by using harmonic Ritz vectors to augment the Krylov subspaces, or by applying harmonic Ritz values as implicit shifts. Computed examples show each proposed method to be competitive with existing methods. Furthermore, theoretical results show the connection between the proposed methods, and MATLAB functions and demos are provided showing their implementation and correct use