Flexible GMRES converges in two phases

1. Problem Statement

The Flexible GMRES (FGMRES) algorithm is a standard iterative solver for large-scale linear systems $Ax=b$ that allows for variable preconditioning. This flexibility is crucial when the preconditioner $M_j$ is an iterative method itself (e.g., in Newton-Krylov methods) or when the matrix $A$ is only accessible via matrix-vector products.

Despite its widespread use, the convergence theory of FGMRES remains poorly understood, particularly regarding how the residual tolerance ($\mu$) of the inner preconditioner affects the convergence of the outer FGMRES loop.

• The Gap: Existing convergence bounds for standard GMRES rely on polynomial representations of the residual, which do not hold for FGMRES because the search space is not a standard Krylov subspace due to varying preconditioners.
• The Question: Does FGMRES converge geometrically at the rate of the preconditioner's tolerance $\mu$, or does the convergence behavior change as iterations progress? Can the method stagnate?

2. Methodology

The authors develop a rigorous convergence analysis based on the relationship between FGMRES and the Flexible Full Orthogonalization Method (FFOM).

• Recursive Bound Derivation:

  • They establish a recursive relationship between the FGMRES residual ($r^{FG}_m$) and the FFOM residual ($r^{FF}_{m-1}$) combined with the preconditioner residual ($r^P_m$).
  • Using the property that $r^{FG}_m \perp \text{span}(AZ_m)$, they derive the inequality:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • They relate the FFOM and FGMRES residuals via a geometric identity involving the ratio of successive FGMRES residuals, leading to a recursive bound on the contraction factor $\gamma_m$:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{where } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Explicit Solution via Chebyshev Polynomials:

  • Assuming a uniform bound on the preconditioner residual $\|r^P_j\| \leq \mu$, they analyze the recurrence relation for the contraction factors.
  • By transforming the recurrence into a linear system, they identify that the product of contraction factors relates to Chebyshev polynomials of the second kind ($U_m$).
  • This allows them to derive a closed-form a priori upper bound for the residual norm.

• Sharpness Construction:

  • To prove the bound is "sharp" (cannot be improved), the authors construct specific counter-examples. They demonstrate that for any linear system and any $\mu \leq 1/2$, there exists a sequence of preconditioners (and a specific matrix $A$) where the FGMRES residual exactly equals the derived upper bound.

3. Key Contributions

A. The Two-Phase Convergence Behavior

The paper's central finding is that FGMRES convergence is governed by two distinct phases, dependent on the preconditioner tolerance $\mu$:

1. Phase 1 (Initial Geometric Convergence):

   • For small iteration counts $m$, the convergence rate is approximately $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • This phase dominates when $\mu$ is small (e.g., $\mu \ll 0.5$).

2. Phase 2 (Deterioration or Stagnation):

   • As $m$ increases, the convergence rate deteriorates from $\mu$ to a new asymptotic rate $\nu$.
   • The asymptotic rate is given by:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Case $\mu \leq 0.5$: The rate $\nu$ is slightly larger than $\mu$ (e.g., if $\mu=0.1$, $\nu \approx 0.1005$). For very small $\mu$, the rate remains practically constant. However, as $\mu \to 0.5$, the rate deteriorates significantly, approaching $\nu \approx \sqrt{\mu}$.
   • Case $\mu > 0.5$: The method may stagnate or break down after an initial reduction phase. The "stalling index" $m^*$ (the number of iterations before stagnation) decreases rapidly as $\mu$ exceeds 0.5.

B. The Sharp Upper Bound

The authors derive the following sharp upper bound for the residual at step $m$ (assuming $\mu \leq 1/2$):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
where $U_m$ is the Chebyshev polynomial of the second kind.

• This bound is attainable: The authors prove that there exist linear systems and preconditioner sequences where equality holds.
• This implies that the derived bound represents the worst-case scenario for FGMRES under the given assumptions.

C. Convergence Guarantee Condition

The paper establishes a critical threshold: FGMRES is guaranteed to converge to the exact solution (without stagnation) if and only if $\mu \leq 1/2$.

• If $\mu > 1/2$, the theoretical bound allows for stagnation, and the authors show that stagnation can indeed occur in practice for specific systems.

4. Results and Numerical Demonstrations

The theoretical findings are validated through numerical experiments in MATLAB:

1. Sharpness Verification: A constructed $2500 \times 2500$ system with an inner GMRES(100) preconditioner ($\mu=0.5$) showed that the computed FGMRES residual matched the theoretical upper bound exactly, confirming the bound is tight.
2. Stagnation Illustration: For $\mu = 0.55$, the residual reduced initially but stagnated after 6 iterations, matching the predicted "stalling index."
3. Real-World Application: On a large sparse matrix from a 3D Poisson problem (finite element discretization), the new bound closely tracked the actual convergence behavior of FGMRES-GMRES, demonstrating its practical relevance even for non-constructed systems.

5. Significance and Implications

• Theoretical Breakthrough: This is the first work to provide a sharp, attainable upper bound for FGMRES that explicitly accounts for the variable preconditioner tolerance. It resolves the mystery of why FGMRES sometimes converges slower than expected despite a good inner solver.
• Practical Guidance for Tuning:
  • If a preconditioner can be tuned (e.g., by setting a target residual $\mu$), the results suggest keeping $\mu \leq 0.5$ is essential for guaranteed convergence.
  • For very tight tolerances ($\mu \ll 0.5$), the two-phase behavior is negligible, and the method converges geometrically at rate $\mu$.
  • For looser tolerances ($\mu \approx 0.5$), users should expect a slowdown in convergence rate as the iteration count grows.
• Comparison to Restarted GMRES: The paper notes that while restarted GMRES has a theoretical convergence rate of $O(\mu^j)$, FGMRES often outperforms it in practice due to deflation effects (the inner solver sees deflated right-hand sides). However, the worst-case bound for FGMRES is strictly worse than the restarted GMRES bound when $\mu$ is close to 0.5, highlighting a trade-off between flexibility and worst-case stability.
• Limitations: The analysis assumes $\|r^P_j\| \leq \mu$ is constant. The authors acknowledge that methods like "fastGMRES" with randomized sketching may have varying $\mu$, and extending the analysis to such cases remains an open challenge.

In summary, the paper provides a definitive characterization of FGMRES convergence, proving that it operates in two phases and establishing a hard limit ($\mu \leq 0.5$) for guaranteed convergence, backed by sharp mathematical bounds and numerical evidence.