Preconditioned GMRES methods for least squares problems

For least squares problems of minimizing parallel to b - Ax parallel to 2 where A is a large sparse m x n (m ! n) matrix, the common method is to apply the conjugate gradient method to the normal equation A(T)Ax = A(T)b. However, the condition number of A(T)A is square of that of A, and convergence becomes problematic for severely ill-conditioned problems even with preconditioning. In this paper, we propose two methods for applying the GMRES method to the least squares problem by using an n x m matrix B. We give the necessary and sufficient condition that B should satisfy in order that the proposed methods give a least squares solution. Then, for implementations for B, we propose an incomplete QR decomposition IMGS(l). Numerical experiments showed that the simplest case 1 = 0 gives the best results, and converges faster than previous methods for severely ill-conditioned problems. The preconditioner IMGS(0) is equivalent to the case B = (diag(A(T)A))(-1)A(T), so (diag(A(T)A))(-1)A(T) was the best preconditioner among IMGS(l) and Jennings' IMGS(T). On the other hand, CG-IMGS(0) was the fastest for well-conditioned problems.