Stabilizing randomized GMRES through flexible GMRES

Technical Summary: Stabilizing Randomized GMRES Through Flexible GMRES

Problem Statement
The paper addresses the challenge of solving large, sparse linear systems $Ax = b$ using randomized Krylov subspace methods. While randomization has proven highly effective for low-rank matrix approximation and overdetermined least squares problems, its application to general nonsymmetric linear systems is more difficult. Unlike overdetermined systems, general linear systems lack inherent redundancy, making the solution vector sensitive to perturbations in all matrix components. Consequently, "sketching the problem" is less viable than "sketching the algorithm."

Existing randomized Krylov solvers, such as sketched GMRES (sGMRES), aim to reduce the expensive orthogonalization costs associated with standard GMRES by projecting the problem into a lower-dimensional space using a sketching operator $S$. However, sGMRES suffers from stability issues. Specifically, when using truncated Arnoldi processes to generate non-orthogonal Krylov bases, the basis can become highly ill-conditioned, leading to stagnation or numerical instability. While restarting sGMRES is a common remedy, it often fails to converge for difficult problems, as the restart length required for convergence may be prohibitively large.

Methodology
The authors propose a hybrid approach that uses Flexible GMRES (FGMRES) as an outer wrapper to stabilize sketched GMRES (sGMRES). The core methodology involves the following components:

1. Theoretical Foundation (FGMRES Residual Bound):
   The authors derive a new, practical upper bound for the FGMRES residual. By introducing a flexible version of the Full Orthogonalization Method (FFOM), they establish that the FGMRES residual at iteration $m$, denoted $\|r_m\|$, is bounded by the product of the FFOM residual at the previous iteration and the residual of the inner preconditioner:
   $$\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$$
   This bound implies that if the inner solver (the preconditioner) reduces the residual effectively, the outer FGMRES iteration will also reduce the global residual, provided the FGMRES and FFOM residuals remain comparable. This theoretical result justifies using FGMRES to guarantee non-increasing residual norms even if the inner solver is unstable.

2. Algorithmic Structure (FGMRES-sGMRES):
   The proposed algorithm, referred to as fastGMRES, operates as follows:

   • Outer Loop: Executes FGMRES iterations.
   • Inner Loop (Preconditioner): At each outer iteration $j$, the preconditioner $M_j$ is an approximate solution to $Az = v_j$ computed via $k$ iterations of sGMRES.
   • sGMRES Implementation: The inner sGMRES solver constructs a Krylov basis $B_k$ using a truncated Arnoldi process (orthogonalizing only against the last $t$ vectors). The solution $z_j$ is found by minimizing the sketched residual $\|S(v_j - Az)\|$ over the range of $B_k$.
   • Stopping Criteria: The inner sGMRES loop terminates based on three conditions:
     1. A maximum iteration limit $k_{\max}$ (e.g., 500) to control memory.
     2. A condition number threshold for the sketched basis $SAB_k$ (e.g., $10^{15}$) to prevent severe ill-conditioning.
     3. The estimated FGMRES residual bound falling below the target tolerance.

3. Parameterization:
   The method requires minimal parameter tuning. The primary parameter is the Arnoldi truncation parameter $t$. The authors investigate $t=0$ (a pure power basis with no orthogonalization) up to $t=5$.

Key Contributions

• Stabilization Mechanism: The paper demonstrates that wrapping sGMRES within an FGMRES outer loop effectively stabilizes the randomized solver. The outer loop ensures non-increasing residual norms, overcoming the stagnation issues typical of restarted sGMRES.
• New Residual Bound: The derivation of the bound $\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$ provides a theoretical justification for the method's robustness and offers a practical tool for predicting convergence based on the inner solver's performance.
• Simplicity and Robustness: The proposed "fastGMRES" method requires very little user input. Unlike other deflated restarting methods (e.g., GMRES-SDR or RGS-GMRES-MDR) that require careful selection of subspace sizes and the number of deflated vectors, fastGMRES performs robustly with fixed parameters ($t=0$ or small $t$, fixed sketching dimension).
• Efficiency via $t=0$: The authors report a counter-intuitive finding that setting the truncation parameter $t=0$ (no orthogonalization in the inner loop) often yields the best time-to-solution performance, particularly for problems where matrix-vector products are cheap.

Numerical Results
The authors evaluate the method on several challenging problems from the SuiteSparse Matrix Collection and other benchmarks:

• vas stokes 1M: A difficult problem where restarted sGMRES stagnates. The FGMRES-stabilized version converges steadily. The method outperforms restarted sGMRES significantly and is competitive with GMRES-SDR and RGS-GMRES-MDR, despite requiring fewer parameter choices.
• NACA12: The method converges robustly with and without ILU preconditioning. Notably, $t=0$ remains the fastest configuration, even for the unpreconditioned case where other methods struggle or time out.
• ML Geer: A large-scale problem ($n \approx 1.5$ million). The method converges robustly for all tested $t$, though $t=0$ shows a slight delay in later iterations due to the increasing cost of the outer FGMRES orthogonalization.
• Benchmarking: In a comparison against BiCGSTAB, GMRES, GMRES-DR, and GMRES-SDR across 10 problems, fastGMRES is among the most reliable. It fails to converge within the time limit on only one problem (where all other methods also failed), whereas BiCGSTAB fails on two. While GMRES-SDR with carefully tuned parameters is sometimes faster, fastGMRES achieves comparable performance without the need for parameter tuning.

Significance and Claims
The paper claims that the combination of FGMRES and sGMRES offers a "practical randomized solver" that balances efficiency, robustness, and ease of use. The significance lies in:

1. Reliability: It guarantees non-increasing residual norms, a property often lost in randomized or restarted Krylov methods.
2. Low Tuning Overhead: It eliminates the need for complex parameter selection (such as deflation counts or restart lengths) that plagues other advanced Krylov methods.
3. Computational Efficiency: The surprising effectiveness of $t=0$ suggests that avoiding inner products in the inner loop can be highly beneficial, particularly for parallel computing and mixed-precision scenarios where communication for orthogonalization is a bottleneck.

The authors conclude that while the method does not always outperform the best-tuned existing solvers, it provides a highly competitive, "set-and-forget" alternative that is robust across a wide range of difficult linear systems. Future work is suggested to explore multi-level FGMRES structures to mitigate the orthogonalization costs of the outer loop for very large iteration counts.