Iterative Solution of Sparse Linear Least Squares using LU Factorization

Gary W Howell (1) , Marc Baboulin (2)

1 NC State - North Carolina State University [Raleigh]
2 ParSys - LRI - Systèmes parallèles (LRI)

In this paper, we are interested in computing the solution of an overdetermined sparse linear least squares problem Ax=b via the normal equations method. Transforming the normal equations using the L factor from a rectangular LU decomposition of A usually leads to a better conditioned problem. Here we explore a further preconditioning by inv(L1) where L1 is the n × n upper part of the lower trapezoidal m × n factor L. Since the condition number of the iteration matrix can be easily bounded, we can determine whether the iteration will be effective, and whether further pre-conditioning is required. Numerical experiments are performed with the Julia programming language. When the upper triangular matrix U has no near zero diagonal elements, the algorithm is observed to be reliable. When A has only a few more rows than columns, convergence requires relatively few iterations and the algorithm usually requires less storage than the Cholesky factor of AtA or the R factor of the QR factorization of A.

Mots clés: Sparse linear least squares; iterative methods; preconditioning; conjugate gradient algorithm; lsqr algorithm; LU factorization

Domaines: Analyse numérique [cs.NA]; Calcul parallèle, distribué et partagé [cs.DC]

Gary W Howell, Marc Baboulin. Iterative Solution of Sparse Linear Least Squares using LU Factorization. International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia 2018), Jan 2018, Tokyo, Japan. ⟨10.1145/3149457⟩. ⟨hal-01706012⟩