Volume 42, pp. 85-105, 2014.

Implicitly restarting the LSQR algorithm

James Baglama and Daniel J. Richmond

Abstract

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.

Full Text (PDF) [424 KB], BibTeX

Key words

Golub-Kahan bidiagonalization, iterative method, implicit restarting, harmonic Ritz values, large-scale computation, least-squares, LSQR, Krylov subspace

AMS subject classifications

65F15, 15A18

Links to the cited ETNA articles

[10]	Vol. 8 (1999), pp. 26-35 A. Björck and J. Y. Yuan: Preconditioners for least squares problems by LU factorization

< Back