Solution of sparse rectangular systems using LSQR and Craig (Q1907877)

Least squares QR factorization (LSQR) and \textit{E. J. Craig's} method [J. Math. Phys. 34, 64-73 (1955; Zbl 0065.10901)] are two well-known methods for solving compatible square and rectangular systems. By including regularization, the author extends Craig's method to incompatible systems, and observes that it solves the same damped least squares problems as LSQR. The methods may therefore be compared on rectangular systems of arbitrary shape. In fact, the damped least squares problem ``\(\min|Ax- b|^2+ |\delta x|^2\)'' and the problem ``\(\min|x|^2+ |s|^2\) subject to \(Ax+ \delta s= b\)'' are equivalent and compatible for any \(\delta> 0\). The solution of the least squares problem satisfies the augmented system \[ (\begin{smallmatrix} I\\ A^T\end{smallmatrix} \begin{smallmatrix} A\\ - \delta^2 I\end{smallmatrix}) (\begin{smallmatrix} r\\ x\end{smallmatrix})= (\begin{smallmatrix} b\\ 0\end{smallmatrix}), \] and this is used by the author to establish a direct method for sparse linear equations and least squares problems. In sections 3 to 5 the author reviews iterative methods for symmetric and rectangular systems and states some results about the connection of the methods. Finally, numerical tests show the different performance of extended LSQR and extended Craig's method. It seems that LSQR is the more reliable method on overdetermined systems as well as on underdetermined systems (with or without regularization).