Preconditioners for least squares problems by LU factorization

Abstract. Iterative methods are often suitable for solving least-squares problems min kAx, bk2, whereA 2 R m n is large and sparse. The use of the conjugate gradient method with a nonsingular square submatrix A1 2 R n 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 A1 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. (1.1) Key words. Linear least squares, preconditioner, conjugate gradient method, LU factorization