Preconditioners for least squares problems by LU factorization (Q1292262)

The authors consider the problem of finding suitable preconditioners in the iterative solution of least squares problems \(\min\| Ax-b\|_2\) where the rectangular matrix \(A\) is large and sparse. Two basic conjugate gradient methods using an appropriate submatrix \(A_1\) as a preconditioner are proposed and bounds for the rate of convergence are derived. It is shown how one of these methods can be adapted to solve a generalized least squares problem. An algorithm for selecting \(n\) linearly independent rows from \(A\) to form \(A_1\) is outlined. The methods are tested on some sparse rectangular matrices from the Harwell-Boeing sparse matrix collection. It follows from the comparison results that the preconditioned conjugate method is much better than the conjugate gradient method.