LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
Christopher C. Paige, Michael A. Saunders · ACM Transactions on Mathematical Software · 1982
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.
Cited by 4,387 works. doi:10.1145/355984.355989 Open-access PDF
Authors
References
- The Algebraic Eigenvalue Problem
- Methods of conjugate gradients for solving linear systems
- Computational Methods of Linear Algebra
- An iteration method for the solution of the eigenvalue problem of linear differential and integral operators
- Numerical methods for solving linear least squares problems
- Calculating the Singular Values and Pseudo-Inverse of a Matrix
- Solution of Sparse Indefinite Systems of Linear Equations
- Algorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems
- Solution of sparse linear least squares problems using givens rotations
- Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations