1 Introduction to Flexible GMRES (FGMRES)

1.1 Motivation for flexibility in Krylov methods

Flexible GMRES (FGMRES) addresses a practical limitation of many Krylov subspace solvers: the assumption that the preconditioning action behaves consistently across iterations. In large-scale computations, preconditioners may be updated, recomputed, approximated, or applied through nested procedures whose outcomes change over time. When that variability is significant, using a solver designed for a single fixed preconditioning operator can degrade performance or complicate interpretation.

FGMRES preserves the core Krylov-subspace idea while allowing the preconditioning step to vary from one iteration to the next. This makes it suitable for adaptive workflows, nonlinear or time-dependent contexts, and settings where the “best” preconditioner at one step is not the same as at another.

1.2 Relation to standard GMRES and preconditioned GMRES

GMRES solves a linear system by building an orthonormal basis for a Krylov subspace and producing an approximate solution whose residual norm is minimized over an expanding subspace. Preconditioned GMRES modifies this process by applying a preconditioner that is typically fixed and either integrated as a left or right transformation.

FGMRES generalizes preconditioned GMRES by letting the preconditioning map change between iterations. Despite this flexibility, the method still constructs a subspace-based approximation and performs least-squares minimization to select the iterate that reduces the residual most effectively within the generated space.

1.3 When a flexible approach is advantageous

FGMRES is most useful when the preconditioning operation cannot be represented by one stationary linear operator. Common cases include:

  • Nested methods where the inner solver accuracy or stopping rule evolves.
  • Nonlinear or time-varying models, where the effective linearization changes during the outer iteration.
  • Constraint handling or penalty strategies that are updated adaptively.
  • Computational strategies that switch between different approximations, levels, or discretizations during the solve.

In such environments, FGMRES can be viewed as a robust umbrella that tolerates nonstationary or inexact preconditioning while still benefiting from Krylov acceleration.

2 Mathematical Formulation

2.1 Problem statement and notation

Consider a linear system \[ Ax=b, \] with \(A\) a (generally nonsymmetric) matrix and \(b\) a right-hand side vector. Let \(x_0\) be an initial guess and define the initial residual \[ r_0=b-Ax_0. \] FGMRES generates successive approximations \(x_m\) by expanding the solution search space through a Krylov-like construction.

2.2 Preconditioning as a variable linear operator

In classical preconditioned GMRES, one often uses a fixed preconditioner \(M\) (or \(M^{-1}\)) that is treated as constant throughout the iteration. In FGMRES, the preconditioning step may vary: \[ z_j = M_j^{-1} v_j, \] where \(v_j\) is an appropriate vector from the Krylov basis generation and \(M_j\) denotes the preconditioning operator used at iteration \(j\). Each application can be exact or approximate, and \(M_j\) may represent a genuinely changing operator or an inexact application of an otherwise fixed preconditioner.

The key modeling point is that the algorithm does not require the existence of a single operator \(M^{-1}\) that matches every step.

2.3 Residuals, search spaces, and approximation updates

At iteration \(m\), the method forms an approximate solution in the affine space \[ x_m = x_0 + \sum_{j=1}^{m} \alpha_j z_j, \] where the vectors \(z_j\) are the preconditioned images produced during basis construction, and the coefficients \(\alpha_j\) are chosen to reduce the residual.

The residual after forming \(x_m\) is \[ r_m=b-Ax_m, \] and FGMRES selects \(\alpha_j\) through a least-squares problem tied to the Arnoldi relation that emerges during orthogonalization.

2.4 Arnoldi process with variable preconditioning

The Arnoldi-like process underlies GMRES: it generates orthonormal vectors \(v_j\) and forms an upper Hessenberg matrix \(H_m\) capturing the action of \(A\) on the basis.

In FGMRES, a typical construction proceeds by:

  1. Generating an orthonormal sequence \(\{v_j\}\) from the residual.
  2. Applying a variable preconditioner to obtain \(\{z_j\}\).
  3. Computing \(w_j = Az_j\).
  4. Orthogonalizing \(w_j\) against the existing \(v_i\) to maintain orthonormality, while filling the entries of \(H_m\).

The nonstationarity resides in the \(z_j\) vectors: they come from \(M_j^{-1}\), not from a single fixed transformation. The least-squares step then uses the Hessenberg structure created from the \(Az_j\) images.

3 Algorithmic Description

3.1 Core FGMRES iteration loop

An outline of the FGMRES process over \(m\) inner iterations (before any restart) is as follows:

  1. Initialize \(x\leftarrow x_0\), \(r_0=b-Ax_0\), and normalize \(r_0\) to form \(v_1\).
  2. For \(j=1,2,\dots,m\):
  • Compute \(z_j\) via the preconditioning operator used at step \(j\): \(z_j=M_j^{-1}v_j\).
  • Compute \(w_j = A z_j\).
  • Orthogonalize \(w_j\) against prior \(v_i\) to obtain \(v_{j+1}\) and the Hessenberg coefficients.
  1. Solve a small least-squares problem that updates the coefficient vector for the next approximation.
  2. Update \(x_m = x_0 + \sum_{j=1}^{m}\alpha_j z_j\).

This framework keeps the residual-minimizing character of GMRES while decoupling it from any assumption that preconditioning is fixed.

3.2 Generation of the flexible Krylov basis

The “basis” relevant for solution construction is not the \(\{v_j\}\) alone, but the preconditioned set \(\{z_j\}\). The vectors \(\{v_j\}\) are used for orthogonality and residual minimization structure, while the final update uses the corresponding \(\{z_j\}\).

Practically, the method requires storing both:

  • The orthonormal vectors \(v_j\) used in orthogonalization and the Hessenberg matrix formation.
  • The preconditioned vectors \(z_j\) needed to form \(x_m\).

This dual storage is one of the distinguishing computational costs relative to simpler preconditioned GMRES variants.

3.3 Least-squares residual minimization

At iteration \(m\), the Arnoldi-like relation produces an upper Hessenberg matrix \(H_m\) and a residual representation involving the first basis vector \(v_1\). GMRES selects coefficients \(\alpha\in\mathbb{R}^m\) to minimize \[

\| \beta e_1 - H_m \alpha \|,

\]

where \(\beta=\|r_0\|\) and \(e_1\) is the first coordinate vector.

FGMRES uses the same least-squares objective form, but with the Arnoldi relation built from \(Az_j\) generated using varying preconditioning. The coefficients \(\alpha\) define how much each stored \(z_j\) contributes to the updated solution.

3.4 Implementation details (storage and operations)

A typical implementation stores:

  • \(V_{m+1}=[v_1,\dots,v_{m+1}]\),
  • \(Z_m=[z_1,\dots,z_m]\),
  • \(H_m\in\mathbb{R}^{(m+1)\times m}\).

Operations include:

  • Applying \(A\) to each \(z_j\),
  • Applying the variable preconditioner to each \(v_j\),
  • Orthogonalizing \(w_j=Az_j\) against \(V_m\),
  • Solving the small least-squares problem, usually via QR-based updates.

Because preconditioners may be applied approximately, the orthogonalization stage remains the main numerical stability mechanism, while the least-squares solve ensures the iterate corresponds to the minimum-residual property within the constructed space.

3.5 Stopping criteria and practical considerations

FGMRES commonly stops when:

- The relative residual \(\|r_m\|/\|b\|\) falls below a tolerance,
  • Or the residual norm stagnates,
  • Or a maximum number of iterations is reached.

When restarts are used, stopping may occur before the restart boundary if the desired accuracy is achieved. Additionally, when inner solves implement the preconditioning action, their stopping thresholds can interact with outer convergence; adaptive rules are often used to balance cost and accuracy.

4 Connections and Special Cases

4.1 Recovery of standard GMRES as a special case

If no preconditioning is applied, or if the “preconditioner” is the identity at every step (so \(z_j=v_j\)), FGMRES reduces to standard GMRES. More generally, if a fixed preconditioner is used and applied consistently such that \(z_j=M^{-1}v_j\) for all iterations, the method aligns with commonly used preconditioned GMRES formulations (with the appropriate left/right interpretation).

4.2 Relation to right-preconditioned GMRES

In some presentations, right-preconditioned GMRES solves for a transformed variable using an operator like \(A M^{-1}\). FGMRES relates to this setting when the variable preconditioning corresponds to applying \(M_j^{-1}\) to the basis vectors in a way consistent with the right-preconditioned viewpoint.

However, because \(M_j\) may change, FGMRES does not collapse to a single right-preconditioned operator; it instead maintains the residual-minimizing structure through the Arnoldi process built from the varying images.

4.3 Comparison to inexact and nonstationary iterative methods

Inexact Krylov methods allow errors in operations that are ideally exact, such as approximate matrix-vector products or approximate solves inside preconditioners. Nonstationary iterative methods modify the iteration operator itself over time. FGMRES overlaps both themes by permitting errors or changes in the preconditioning step while still enforcing a GMRES-like minimization principle at each restart window.

Where other nonstationary approaches may require specialized convergence proofs for each operator variation pattern, FGMRES is designed to accommodate a broad class of variable preconditioning behaviors without rewriting the outer iteration’s structure.

5 Convergence Theory and Behavior

5.1 Residual minimization viewpoint

A central lens for GMRES-type methods is polynomial approximation: GMRES chooses a polynomial that reduces the residual within a given subspace. FGMRES keeps the least-squares residual minimization, but the effective mapping from basis generation to solution update is influenced by the sequence of preconditioned vectors \(z_j\).

As a result, convergence can still be framed in terms of “best approximation within the constructed space,” though the space itself depends on the variable preconditioner sequence.

5.2 Conditions affecting convergence (high-level)

High-level convergence factors include:

  • The degree of nonnormality and spectrum distribution of \(A\),
  • The quality and stability of the preconditioning actions \(M_j^{-1}\),
  • The degree to which variable preconditioning preserves directions that are useful for residual reduction,
  • Numerical effects such as loss of orthogonality during Arnoldi.

Even when preconditioning varies, convergence typically improves when each \(M_j^{-1}\) remains a reasonable approximate inverse in the sense relevant to the current residual direction.

5.3 Impact of varying preconditioners

Varying preconditioners can help or harm depending on how they change the generated search space:

  • Helpful variation occurs when each update improves alignment with the residual’s “hard” components or progressively enhances the approximation quality.
  • Harmful variation can arise when the preconditioner changes too abruptly or inconsistently, effectively reorienting the search space in ways that do not support continued residual reduction.

Because FGMRES stores all preconditioned vectors from the iteration window, it can partially compensate for nonstationarity within that window, but repeated restart windows may still be sensitive to long-term trends.

In practice, one often observes:

  • Faster residual decreases when preconditioners improve during the solve (e.g., tightened inner tolerances).
  • Slower or irregular decreases when preconditioner quality fluctuates (e.g., alternating strategies or coarse approximations early on).
  • Occasional plateauing when preconditioning becomes ineffective or when breakdown-like numerical issues reduce the effective dimension of the subspace.

Residual history plots are therefore commonly used for diagnosis, since the least-squares minimization is explicit in the GMRES framework.

6 Preconditioning Strategies for FGMRES

6.1 Stationary vs. nonstationary preconditioners

Stationary preconditioning uses one operator throughout, while nonstationary preconditioning updates across outer iterations. FGMRES naturally accommodates both, but its advantage is most evident when updates cannot be represented by a single fixed linear map.

Nonstationary strategies can include time-adaptive operator approximations, changing discretization levels, or adaptive regularization parameters that alter the effective linear solve.

6.2 Inexact inner solves and adaptive stopping

When the preconditioning step itself is performed by an iterative inner solver, one may stop the inner iteration early. That yields an inexact application \(z_j\approx M_j^{-1}v_j\). In FGMRES, this inexactness can vary from step to step if the inner stopping criterion is adaptive.

Adaptive stopping is often designed so that early outer iterations use cheaper, rougher inner solves, while later iterations become more accurate as the outer residual decreases.

6.3 Block, multilevel, and operator-splitting preconditioners

FGMRES can be paired with advanced preconditioning frameworks, including:

  • Block preconditioners for systems with coupled variables,
  • Multilevel methods (e.g., coarse-grid corrections) where the effective action may depend on current scales,
  • Operator-splitting preconditioners where each step uses a different composition of operators.

If these preconditioners introduce time-varying or iteration-varying behavior (for example, via changing level counts or dynamically selected blocks), FGMRES provides a compatible outer solver.

6.4 Handling singular or ill-conditioned preconditioners

Some preconditioning operators may be singular or poorly conditioned, particularly when they are approximate or based on incomplete subproblems. While ill-conditioned preconditioning can still affect convergence, FGMRES can mitigate issues by:

  • Allowing the algorithm to incorporate each preconditioned vector even when earlier ones were computed under different assumptions.
  • Enabling inner safeguards (regularization, damping, or fallback strategies) that change from iteration to iteration.

Numerically, orthogonalization and least-squares steps remain central to maintaining stability, especially when preconditioned vectors have reduced effective rank.

7 Computational Aspects

7.1 Cost model: matvecs, preconditioner applications, and orthogonalization

The dominant costs per outer iteration include:

  • One application of \(A\) to \(z_j\),
  • One application of the preconditioner to \(v_j\),
  • Orthogonalization of \(w_j\) against the existing basis vectors.

Orthogonalization typically costs on the order of \(O(m)\) inner products and vector updates per iteration within a restart window, accumulating to a total of \(O(m^2)\) work over \(m\) iterations, in addition to the matrix-vector products and preconditioner applications.

7.2 Orthogonalization choices and numerical stability

Classical Gram–Schmidt and modified Gram–Schmidt are common orthogonalization schemes. With nonsymmetric problems and variable preconditioning, loss of orthogonality can become more pronounced, leading to reduced effectiveness of the Krylov basis.

Many implementations therefore use modified Gram–Schmidt with reorthogonalization, or orthogonalization strategies that monitor breakdown-like events (e.g., small norms in \(w_j\) after projection).

7.3 Restarting strategies and their interaction with flexibility

FGMRES is commonly used in restarted form (FGMRES(m)). Restarting limits memory usage and orthogonalization cost but can reduce the method’s ability to exploit long-range subspace information.

Because flexibility already increases storage needs (storing \(z_j\) vectors), restart length selection becomes a trade-off:

  • Larger \(m\) increases per-cycle cost but provides a richer search space.
  • Smaller \(m\) reduces cost but may make convergence more sensitive to preconditioner variability.

7.4 Parallelization considerations

Parallel implementations must coordinate:

  • Distribution of \(A\) and vector operations for \(Az_j\),
  • Preconditioner application, which may involve multigrid or block operations with communications,
  • Global reductions required for inner products during orthogonalization and QR/least-squares updates.

Flexibility can complicate pipelining or batching strategies, since the preconditioner may behave differently each iteration. Still, the structure of the Arnoldi and least-squares steps provides well-defined synchronization points.

8 Numerical Examples and Benchmarks (Generic)

8.1 Testing on representative linear systems

Benchmarks for FGMRES typically test nonsymmetric and challenging matrices where fixed preconditioning is insufficient or difficult to represent. Representative categories include:

  • Convection-dominated problems leading to nonsymmetric operators,
  • Systems with strong coupling across variables,
  • Discretizations where preconditioner quality varies with current solution components.

The evaluation focuses on robustness across problem instances and sensitivity to preconditioner updates.

8.2 Comparing fixed-preconditioner GMRES vs. FGMRES

A common comparison assesses iteration counts and wall-clock time between:

  • GMRES using a fixed preconditioner operator,
  • FGMRES using the same underlying preconditioning idea but implemented in an iteration-varying way.

If variability stems from changing inner tolerances or evolving operator approximations, GMRES may show degraded or inconsistent behavior, while FGMRES better preserves the intended residual minimization under those changes.

8.3 Effect of inner-solver variability on performance

When the preconditioning step is executed by an inner iterative method, varying inner accuracy can influence both convergence rate and total compute cost. Benchmarks often vary:

  • Inner stopping thresholds across outer iterations,
  • Inner solver iteration caps,
  • Strategies for tightening tolerances as the outer residual decreases.

FGMRES is particularly useful in these experiments because it is designed to remain effective when preconditioning is not identical from one basis step to the next.

9 Practical Guidance

9.1 Choosing flexible preconditioner updates

Effective FGMRES usage begins with selecting how \(M_j\) varies. Practical guidance includes:

  • Ensure each preconditioner application is at least a reasonable approximation in early iterations.
  • Avoid abrupt, low-quality preconditioner switches late in the solve unless motivated by a strong computational advantage.
  • If updates correspond to adaptive inner solves, tie inner tolerance behavior to outer residual progress.

When preconditioner updates are too aggressive, the search space can fluctuate in a way that slows minimization.

9.2 Parameter selection (restart length, tolerances)

Common parameters include:

  • Restart length \(m\): chosen based on memory limits and desired per-cycle progress.
- Outer tolerance for \(\|r\|\): chosen relative to the accuracy requirements of the final application.
  • Inner tolerance scheduling: chosen to balance cost with the need for preconditioning accuracy.

A typical heuristic is to start with a coarser inner tolerance and tighten it as the outer residual decreases, while ensuring the inner errors do not dominate the outer residual reduction.

9.3 Diagnostics: residual history and breakdown signals

Useful diagnostics include:

  • Residual norm vs. iteration, highlighting stagnation or irregular spikes.
  • Measures of orthogonality loss or unexpectedly small Hessenberg subdiagonal elements, which can signal numerical trouble.
  • Monitoring whether the least-squares problem becomes ill-conditioned, which may occur if the effective basis dimension collapses.

These indicators help distinguish between genuine slow convergence and algorithmic instability.

9.4 Common implementation pitfalls

Common pitfalls include:

  • Incomplete storage of preconditioned vectors \(z_j\), which prevents correct solution updates.
  • Incorrect association between \(v_j\) used for preconditioning and the corresponding \(z_j\) used later in the update.
  • Poorly conditioned QR or least-squares solves at large \(m\).
  • Restart misconfiguration that resets history in a way that undermines the flexibility benefits.

Robust testing on smaller instances can catch these issues early.

10 Further Reading

10.1 Foundational references on flexible GMRES

Foundational treatments cover the derivation of FGMRES from Arnoldi relations with variable preconditioning and discuss the least-squares minimization perspective. These references typically emphasize how the method generalizes preconditioned GMRES and what assumptions can be relaxed.

Related extensions include methods for inexact preconditioning, variants with different orthogonalization or recycling strategies, and approaches that incorporate variable operators in other Krylov frameworks. These can be useful for understanding the broader design space for nonstationary and approximate linear solvers.

Textbooks on iterative methods for linear systems and survey articles on Krylov subspace techniques provide background on GMRES, preconditioning, and practical algorithm design. For FGMRES specifically, additional resources often focus on variable preconditioning, nested iterations, and performance engineering considerations for large-scale computations.