Title: Generalized Minimal Residual Methods for Singular Linear Systems or Linear Least-Squares Problems
Abstract: GMRES (Saad and Schultz 1986) is a famed generalized minimal-residual method for solving nonsingular unsymmetric or non-Hermitian linear systems. It may suffer non-benign breakdown on nearly singular systems (Brown and Walker 1997). When working, the solver returns only a least-squares solution for a singular problem (Reichel and Ye 2005). We present GMRES-QLP and GMRES-URV, both successful revamps of GMRES, for returning the unique pseudoinverse solutions of (nearly) singular linear systems or linear least-squares problems. On nonsingular problems, they are numerically more stable than GMRES. In any case, users do not need to know a priori whether the systems are singular, ill-conditioned, or incompatible; the solvers constructively reveal such properties. The solvers leverage the QLP and URV decompositions (Stewart 1998 and 1999) to reveal the rank of the Hessenberg matrix from the Arnoldi process, incurring only minor additional computational cost in comparison to GMRES. We present extensive numerical experiments to demonstrate the scalability and robustness of the solver, with or without preconditioners or restart.