Volume 8, pp. 26-35, 1999.

Preconditioners for least squares problems by LU factorization

A. Björck and J. Y. Yuan


Iterative methods are often suitable for solving least-squares problems $\min\|Ax-b\|_2$, where $A \in {\bf R}^{m\times n}$ is large and sparse. The use of the conjugate gradient method with a nonsingular square submatrix $A_{1} \in {\bf R}^{n\times n}$ of $A$ as preconditioner was first suggested by Läuchli in 1961. This conjugate gradient method has recently been extended by Yuan to generalized least-squares problems. In this paper we consider the problem of finding a suitable submatrix $A_1$ and its LU factorization for a sparse rectangular matrix $A$. We give three algorithms based on the sparse LU factorization algorithm by Gilbert and Peierls. Numerical results are given, which indicate that our preconditioners can be effective.

Full Text (PDF) [124 KB]

Key words

Linear least squares, preconditioner, conjugate gradient method, LU factorization.

AMS subject classifications

65F10, 65F20.

ETNA articles which cite this article

Vol. 42 (2014), pp. 85-105 James Baglama and Daniel J. Richmond: Implicitly restarting the LSQR algorithm

< Back