Premium
Preconditioned Krylov subspace method for the solution of least‐squares problems
Author(s) -
Yin junFeng,
Hayami Ken,
Bai ZhongZhi
Publication year - 2007
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200701146
Subject(s) - krylov subspace , generalized minimal residual method , mathematics , overdetermined system , iterative method , linear system , underdetermined system , factorization , algorithm , mathematical analysis
We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least‐squares problems min ∥ Ax – b ∥ 2 , with A ∈ R m×n , based on the Krylov subspaces K k ( BA, Br ) and K k ( AB, r ), respectively, where B ∈ R n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least‐squares problems, the preconditioned GMRES methods are the best for large, sparse and ill‐conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly‐proposed GMRES‐type methods. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)