Solution of sparse rectangular systems using LSQR and CRAIG

We examine two iterative methods for solving rectangular systems of linear equations: LSQR for over-determined systemsAx b, and Craig's method for under-determined systemsAx = b. By including regularization, we extend Craig's method to incompatible systems, and observe that it solves the same damped least-squares problems as LSQR. The methods may therefore be compared on rectangular systems of arbitrary shape.Various methods for symmetric and unsymmetric systems are reviewed to illustrate the parallels. We see that the extension of Craig's method closes a gap in existing theory. However, LSQR is more economical on regularized problems and appears to be more reliable if the residual is not small.In passing, we analyze a scaled augmented system associated with regularized problems. A bound on the condition number suggests a promising direct method for sparse equations and least-squares problems, based on indefiniteLDL ^T factors of the augmented matrix.Dedicated to Professor Åke Björck in honor of his 60th birthdayPresented at the 12th Householder Symposium on Numerical Algebra, Lake Arrowhead, California, June 1993.Partially supported by Department of Energy grant DE-FG03-92ER25117, National Science Foundation grant DMI-9204208, and Office of Naval Research grant N00014-90-J-1242.