LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares

Abstract

An iterative method is given for solving Ax ~ffi b and minU Ax -b 112, where the matrix A is large and sparse.The method is based on the bidiagonalization procedure of Golub and Kahan.It is analytically equivalent to the standard method of conjugate gradients, but possesses more favorable numerical properties.Reliable stopping criteria are derived, along with estimates of standard errors for x and the condition number of A. These are used in the FORTRAN implementation of the method, subroutine LSQR.Numerical tests are described comparing I~QR with several other conjugate-gradient algorithms, indicating that I~QR is the most reliable algorithm when A is ill-conditioned.