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

Technical Summary: NR-SSOR Right Preconditioned RRGMRES for Non-Range-Symmetric Systems and Rank-Deficient Rectangular Least Squares Problems

Problem Statement
The Generalized Minimal Residual (GMRES) method is a standard Krylov subspace iterative solver for linear systems $Ax = b$. However, when $A$ is singular and the system is inconsistent (i.e., $b \notin R(A)$), GMRES is known to break down without providing a least squares (LS) solution unless $A$ is range-symmetric (EP), meaning $R(A) = R(A^T)$. Specifically, if $R(A^T) \neq R(A)$—a condition that includes cases where the index of $A$ is greater than or equal to 1—there exist initial vectors $x_0$ and right-hand sides $b$ for which GMRES fails. Furthermore, even when $A$ is range-symmetric, the least squares subproblems solved within GMRES can become dangerously ill-conditioned if $b \notin R(A)$.

Existing approaches, such as breakdown-free GMRES, lack theoretical guarantees of always working. Similarly, while the AB-GMRES method (applying GMRES to $ABz=b$) can handle singular systems, standard choices for the preconditioner $B$ (such as $B=A^TC$ with stationary inner iterations) do not guarantee that $AB$ is range-symmetric for inconsistent systems, potentially leading to failure in finding an LS solution.

Methodology
The authors propose a robust iterative method combining three key components:

1. Right Preconditioning with $B = CA^T$: Instead of solving $Ax=b$ directly, the method solves a transformed least squares problem $\min_z \|b - ABz\|_2$ where $B = CA^T$ and $C \in \mathbb{R}^{n \times n}$ is a symmetric positive definite (SPD) matrix. This transformation ensures that the product $AB = ACA^T$ is symmetric and range-symmetric, regardless of whether $A$ itself is range-symmetric. Consequently, the method can determine an LS solution $x = CA^Tz$ without breakdown for arbitrary singular $A$ and $b$.
2. RRGMRES (Range-Restricted GMRES): To address the ill-conditioning issues inherent in GMRES for inconsistent systems, the authors employ RRGMRES instead of standard GMRES. RRGMRES restricts the search space to the range of $A$, providing greater stability for inconsistent range-symmetric systems. Theoretical analysis shows that the smallest singular value of the Hessenberg matrix in RRGMRES is bounded below, a property not guaranteed in standard GMRES.
3. NR-SSOR Preconditioner: The paper introduces the use of the Non-Symmetric SSOR (NR-SSOR) method as an inner-iteration right preconditioner to construct the matrix $C$. The authors prove that if $A$ has no zero columns and the relaxation parameter $\omega$ satisfies $0 < \omega < 2$, the resulting matrix $C$ (derived from the NR-SSOR iteration) is symmetric positive definite. This theoretical guarantee validates the use of NR-SSOR within the proposed framework for both square singular systems and rectangular rank-deficient least squares problems ($A \in \mathbb{R}^{m \times n}$).

Key Contributions

• Theoretical Justification: The paper proves that for the NR-SSOR right preconditioner $B = CA^T$, the matrix $C$ is SPD under standard conditions ($A$ has no zero columns, $0 < \omega < 2$). This ensures that $AB$ is range-symmetric, allowing the method to robustly find LS solutions for non-range-symmetric systems and rectangular problems.
• Robustness for Inconsistent Systems: The proposed NR-SSOR right preconditioned RRGMRES is shown to determine a least squares solution for arbitrary $b \in \mathbb{R}^m$ and singular $A$, including cases where the index of $A \ge 1$ and $R(A) \neq R(A^T)$.
• Extension to Rectangular Problems: The method is successfully extended to underdetermined and overdetermined rectangular least squares problems, where $A$ may be rank-deficient.
• Comparison with MINRES-QLP: The paper establishes a comparison framework with MINRES-QLP, a method known for handling singular symmetric systems, noting that while MINRES-QLP finds min-norm solutions for consistent systems, the proposed method offers superior performance for inconsistent systems with non-range-symmetric matrices.

Numerical Results
Extensive numerical experiments were conducted on:

1. GP Inconsistent Systems: Matrices with index 1 where $R(A) \cap N(A) = \{0\}$ but $R(A) \neq R(A^T)$.
2. Index 2 Inconsistent Systems: Matrices where the index is 2.
3. Underdetermined Least Squares Problems: Large-scale rectangular matrices (e.g., Maragal, landmarkT, lp dfl001).

The results demonstrate that:

• Convergence: Standard GMRES and RRGMRES applied directly to $Ax=b$ often fail to converge to a least squares solution for these inconsistent, non-range-symmetric systems.
• Superiority of NR-SSOR: The NR-SSOR preconditioned RRGMRES consistently achieves significantly smaller residuals (often $10^{-10}$ to $10^{-15}$) compared to other preconditioners like $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ or $B = A^T$.
• Efficiency: The proposed method requires fewer iterations and significantly less computation time (up to 87.9 times faster in specific underdetermined cases) compared to unpreconditioned or differently preconditioned variants.
• Comparison with MINRES-QLP: In inconsistent scenarios, the proposed method achieved residuals orders of magnitude smaller than MINRES-QLP and reached these minima in fewer iterations.

Significance
The paper claims that the proposed NR-SSOR right preconditioned RRGMRES provides a theoretically justified and numerically robust solution for a class of difficult linear algebra problems: singular, non-range-symmetric systems and rank-deficient rectangular least squares problems. By proving the SPD nature of the preconditioner matrix $C$ derived from NR-SSOR, the authors ensure that the method avoids the breakdowns associated with standard GMRES in inconsistent settings. The numerical experiments validate that this approach is not only theoretically sound but also practically efficient, outperforming existing methods like AB-GMRES with other preconditioners and MINRES-QLP in terms of residual reduction and computational speed for inconsistent systems.