IMPLICITLY RESTARTING THE LSQR ALGORITHM

The LSQR algorithm is a popular method for solving least-squares problems. For some matrices, LSQR may require a prohibitively large number of iterations to determine an approximate solution within a desired accuracy. This paper develops a strategy that couples the LSQR algorithm with an implicitly restarted Golub- Kahan bidiagonalization method to improve the convergence rate. The restart is carried out by first applying the largest harmonic Ritz values as shifts and then using LSQR to compute the solution to the least-squares problem. Theoretical results show how this method is connected to the augmented LSQR method of Baglama, Reichel, and Richmond (Numer. Algorithms, 64 (2013), pp. 263-293) in which the Krylov subspaces are augmented with the harmonic Ritz vectors corresponding to the smallest harmonic Ritz values. Computed examples show the proposed method to be competitive with other methods.