Preconditioned GMRES methods for least squares problems (Q946857)

The authors deal with the linear least squares problem: \[ \min \|\mathbf b-\mathbf A\mathbf x\|_{2}, \quad x\in \mathbb R^n,\;\mathbf A\in \mathbb R^{m\times n},\;m>n, \] where \(\mathbf A\) is a large sparse matrix with full column rank. In the first part conventional solution methods are assessed and their shortcomings ascertained. They are referenced in particular: a direct method using \(QR\) decomposition, an incomplete \(QR\) decomposition, the conjugate gradient \(CGLS\) method and the \(CR-LS(k)\) method. In the next part two versions of the generalized minimal residual (GMRES(k)) method are developed together with all proofs needed. They are based on a \(\mathbf B\in\mathbb R^{n\times m}\) mapping matrix to create a Krylov subspace (i) in the (larger) \(m\)-dimensional space and (ii) in the (smaller) \(n\)-dimensional space. Some possibilities of the matrix \(\mathbf B\) construction are discussed. As the most effective method for the matrix \(\mathbf B\) determination reveals the incomplete \(QR\) decomposition \(IMGS(l)\). Wide numerical experiments are done which enables the authors to obtain an overview concerning detailed properties of the preconditioners introduced. In the final part a relation of the parameter \(l\), preconditioning time, number of iterations and iteration time are evaluated for four \(1000\times 320, 4.9\%\) sparse matrices and seven \(10000\times 1000, 1.5\%\) sparse matrices. Results and efficiency of the proposed algorithms are presented in a form of tables, plots and very detailed commentary. It seems that the case \(l=0\) provides the best results and converges faster than conventional methods, especially when the problem is ill-conditioned. The list of references is large enough concentrating to the topic itself without any side steps to general resources.