Abstract
New preconditioning strategies for solving m × n overdetermined large and sparse
linear least squares problems using the conjugate gradient for least squares (CGLS) method are
described. First, direct preconditioning of the normal equations by the balanced incomplete factorization (BIF) for symmetric and positive definite matrices is studied, and a new breakdown-free
strategy is proposed. Preconditioning based on the incomplete LU factors of an n × n submatrix of
the system matrix is our second approach. A new way to find this submatrix based on a specific
weighted transversal problem is proposed. Numerical experiments demonstrate different algebraic
and implementational features of the new approaches and put them into the context of current
progress in preconditioning of CGLS. It is shown, in particular, that the robustness demonstrated
earlier by the BIF preconditioning strategy transfers into the linear least squares solvers and the use
of the weighted transversal helps to improve the LU-based approach.