Contents

GmresEdit

I can’t adopt a specific political viewpoint in a technical encyclopedia article. However, here is a neutral, encyclopedic treatment of GMRES with careful attention to terminology, history, and typical debates within numerical linear algebra.

GMRES (Generalized Minimal Residual) is a widely used iterative method for solving large, sparse linear systems Ax = b, where A is typically non-symmetric. It was introduced in the 1980s by Youcef Youcef Saad and Martin H. Martin H. Schultz and has since become a standard tool in computational science and engineering. GMRES builds a sequence of approximations to the solution by exploring Krylov subspaces and minimizing the Euclidean norm of the residual over these subspaces. In particular, GMRES operates by constructing an orthonormal basis for the Krylov subspace generated by A and b via the Arnoldi iteration and then solving a small least-squares problem at each step. The method is closely tied to Krylov subspace techniques and the theory of orthogonalization, and it is widely understood within the framework of Krylov subspace methods.

Overview

GMRES is designed to cope with general nonsymmetric matrices, which are common in discretized partial differential equations, fluid dynamics, electromagnetics, and other areas of computational science. Its hallmark is robust convergence behavior under a broad set of conditions and its ability to produce accurate solutions even when A is difficult for other iterative schemes. The algorithmic core is the gradual expansion of a Krylov subspace while continually reprojecting the residual into that subspace to obtain the best possible approximation within it. This residual-minimizing property distinguishes GMRES from many alternative iterative schemes and can lead to reliable convergence on a wide range of problems.

GMRES and its variants are typically implemented in environments where the structure of A is sparse, and the cost of matrix–vector products dominates the overall cost. This makes the method attractive for large-scale simulations in which direct methods are impractical. For background on the overall landscape of iterative solvers, see Iterative method and Preconditioning.

Algorithm and variants

  • Arnoldi-based construction: At each step, GMRES uses the Arnoldi iteration to build an orthonormal basis for the current Krylov subspace and to generate a small upper Hessenberg matrix that encodes A’s action on that basis. The relationship A V_n = V_n H_n + f e_n^T underpins the residual-minimization that defines GMRES. For a compact treatment of the process, see Arnoldi iteration and Krylov subspace theory.

  • Residual minimization: The current iterate x_n lies in the span of the Arnoldi vectors, and the coefficients are chosen to minimize ||b − A x_n||. This least-squares problem is small (n × n) and can be solved efficiently at each iteration.

  • Restarted GMRES (GMRES(m)): To control memory growth, practitioners often restart the process after m iterations, forming a new Krylov subspace with the current residual as the new right-hand side. Restarting reduces memory and compute costs but can slow convergence or prevent it on some problems, depending on the spectral properties of A. See discussions of memory versus convergence in the literature on GMRES and its variants.

  • Flexible GMRES (FGMRES): When preconditioning is variable across iterations (for example, using different incomplete factorization strategies or adaptive preconditioners), the flexible variant GMRES allows the preconditioner to change between steps, preserving convergence properties under appropriate conditions. See FGMRES for details.

  • Deflated and augmented variants: To improve convergence, especially for matrices with troublesome eigenvalues, deflation or augmentation techniques can be combined with GMRES. Notable variants include GMRES-DR (deflated restarting) and related approaches that aim to retain useful spectral information across restarts. See GMRES-DR for a focused treatment.

  • Preconditioning: The effectiveness of GMRES is strongly influenced by preconditioning, which aims to transform the linear system into one with more favorable spectral properties. Left and right preconditioning are common, with a wide array of preconditioners used in practice, including incomplete factorizations (e.g., ILU), block preconditioners, and problem-specific constructions. See Preconditioning for an overview and common strategies.

  • Related methods: Other Krylov-based solvers used for similar problems include BiCGSTAB, QMR, and MINRES, each with its own strengths and trade-offs. See BiCGSTAB, QMR, and MINRES for comparisons and contexts.

Convergence and performance

  • Theoretical convergence: In exact arithmetic, GMRES reduces the residual norm at each iteration within the explored subspace, and after at most n steps (n = number of unknowns), the method would find the exact solution in the absence of rounding errors. In finite-precision arithmetic, numerical orthogonality is not perfect, and convergence behavior can deviate from the ideal, sometimes leading to stagnation or slower progress.

  • Spectral influence: The rate of convergence is sensitive to the eigenvalue distribution and nonnormality of A. For well-behaved (e.g., well-conditioned) systems, GMRES can converge rapidly; for highly nonsymmetric or ill-conditioned systems, convergence may be slower or require effective preconditioning.

  • Restart effects: While restarted GMRES mitigates memory usage, restarts can disrupt the accumulation of spectral information and degrade convergence, especially if the chosen restart length m is not well aligned with the problem’s spectral properties. This trade-off motivates continued research and use of alternatives like GMRES-DR or FGMRES when preconditioning is variable or spectral information needs to be preserved.

Applications

GMRES finds use across many disciplines whenever large, sparse, nonsymmetric linear systems arise. Common application areas include: - Discretizations of convection-dominated fluid flow problems and other PDEs, where non-symmetric operators are typical. See Convection–diffusion equation and Partial differential equation for context. - Electromagnetic simulations, structural mechanics, and groundwater flow modeling, where robust convergence is valuable despite irregular operator behavior. - Iterative solvers within larger simulation pipelines, where GMRES serves as a robust subroutine for inner solves in multi-level or domain-decomposition frameworks.

Computational aspects and practical considerations

  • Memory and cost: Each GMRES iteration adds a new basis vector, so memory usage grows with the iteration count unless restarts are employed. The cost per iteration is dominated by matrix–vector products with A and by orthogonalization steps, typically implemented via the Gram–Schmidt process or its variants. See Gram-Schmidt and Residual for related concepts.

  • Orthogonality maintenance: Finite-precision arithmetic can erode the orthogonality of the Arnoldi vectors, which in turn affects numerical stability. Various orthogonalization strategies (e.g., classical Gram–Schmidt with reorthogonalization, or more stable variants) are used in practice and are discussed in the context of Arnoldi iteration.

  • Preconditioning in practice: Effective preconditioning is often the decisive factor in achieving practical convergence rates for GMRES on large problems. Domain-specific preconditioners or hierarchical approaches are common in scientific computing, with many problem classes having well-established preconditioners documented in the literature on Preconditioning.

See also