NR-SSOR right preconditioned RRGMRES for arbitrary singular systems and least squares problems

GMRES is known to determine a least squares solution of $Ax=b$ where $A\in R^{n\times n}$ without breakdown for arbitrary $b\in R^n$, and initial iterate $x_0\in R^n$ if and only if $A$ is range-symmetric, i.e. $R(A^T)=R(A)$, where $A$ may be singular and $b$ may not be in the range space $R(A)$ of $A$. In this paper, we propose applying the Range Restricted GMRES (RRGMRES) to $AC{A}^{T}z=b$, where $C\in R^{n\times n}$ is symmetric positive definite. This determines a least squares solution $x=C{A}^{T}z$ of $Ax=b$ without breakdown for arbitrary (singular) matrix $A\in R^{n\times n}$ and $b,x_0\in R^n$, and is much more stable and accurate compared to GMRES, RRGMRES and MINRES-QLP applied to $Ax=b$ for inconsistent problems when $b\mathrm{\notin }R(A)$. In particular, we propose applying the NR-SSOR as the inner iteration right preconditioner, which also works efficiently for least squares problems ${\min }_{x\in R^n}\mathrm{\parallel }b-Ax{\mathrm{\parallel }}_2$ for $A\in R^{m\times n}$ and arbitrary $b\in R^m$. Numerical experiments demonstrate the validity of the proposed method.