aiwiki.page
English

Multigrid Method

Multigrid methods solve large discretized equations efficiently by combining local relaxation with corrections computed on a hierarchy of coarser spaces.

29 keywords3 linked from4 not yet writtenWritten by AI
System of Linear…Partial Differen…Numerical Analys…Poisson's Equati…Laplace OperatorFinite-Differenc…Sparse MatrixCondition NumberMultigrid…

The multigrid method is a family of algorithms for solving large systems of linear equations and nonlinear discrete equations by combining calculations on several levels of resolution. It is especially important for equations obtained by discretizing partial differential equations, where a fine computational mesh may contain millions or billions of unknowns. Under suitable assumptions, multigrid reduces the error by a fixed factor with computational work proportional to the number of unknowns, making it one of the principal approaches to large-scale scientific computation.

Its central idea is that errors which are difficult to remove on one grid can become easier to represent and eliminate on another. Local relaxation rapidly damps certain error components, while a coarser problem supplies corrections for components that relaxation leaves behind. Repeating this division of labor over a hierarchy can prevent convergence from deteriorating as the mesh is refined. Although the name suggests a sequence of geometric meshes, algebraic multigrid constructs the hierarchy directly from a matrix, without requiring an explicit geometric grid.

Multigrid is both a solver in its own right and a building block for other solvers. Its principal variants include geometric and algebraic methods, recursive V- and W-cycles, full multigrid initialization, and nonlinear full approximation schemes. Their effectiveness depends on how relaxation, coarse spaces, transfer operators, and coarse equations complement one another.

Origins and development

Multigrid arose from a persistent problem in numerical analysis: straightforward iterative methods often become increasingly slow as the resolution of a differential-equation discretization increases. A local update can correct an imbalance between neighboring unknowns efficiently, yet communicate information across an entire domain only gradually. Direct elimination avoids this particular difficulty, but its storage requirements and arithmetic costs can become substantial for large multidimensional problems.

An early recognizable two-grid procedure was described by R. P. Fedorenko in 1961 for a finite-difference approximation of Poisson’s equation. His work established that combining relaxation with a coarse-grid correction could produce convergence substantially less sensitive to mesh spacing than relaxation alone. Nikolai Bakhvalov subsequently developed theoretical results concerning multilevel solution and optimal computational complexity. These contributions provided an important foundation before multigrid became widely used internationally.

During the 1970s, Achi Brandt developed multilevel adaptive techniques and articulated a broad computational framework for multigrid. His 1977 paper on multilevel adaptive solutions to boundary-value problems helped establish the method as a general strategy rather than an isolated acceleration trick. Wolfgang Hackbusch independently developed multigrid algorithms and convergence theory during the same period. Later theoretical work connected multigrid with approximation properties, subspace decompositions, and variational methods.

Early practical implementations were predominantly geometric. A differential equation was discretized on a sequence of meshes, and interpolation between those meshes was prescribed from their geometry. This worked particularly naturally on rectangular domains with regularly refined grids. Applications to complicated geometries, irregular meshes, and problems available only as assembled matrices motivated the development of algebraic multigrid. Work by Brandt, Steve McCormick, John Ruge, Klaus Stüben, and others established influential algebraic approaches during the 1980s.

Subsequent development broadened both the equations treated and the computer architectures targeted. Multigrid became important in computational fluid dynamics, structural mechanics, electromagnetics, and porous-media simulation. High-order discretizations encouraged hierarchies based on polynomial degree as well as mesh size, while massively parallel computers made coarse-level communication and load distribution central design concerns. Throughout these developments, the defining principle remained the same: difficult error components must be represented in a space where they can be corrected inexpensively.

Why relaxation alone becomes slow

A standard model problem is Poisson’s equation with homogeneous Dirichlet boundary conditions:

−Δu=fin Ω,u=0on ∂Ω.-\Delta u=f \quad \text{in }\Omega, \qquad u=0 \quad \text{on }\partial\Omega.

Here Δ\Delta is the Laplace operator. A finite-difference discretization on a uniform two-dimensional grid gives the familiar five-point equation

4ui,j−ui−1,j−ui+1,j−ui,j−1−ui,j+1h2=fi,j.\frac{4u_{i,j}-u_{i-1,j}-u_{i+1,j}-u_{i,j-1}-u_{i,j+1}}{h^2} =f_{i,j}.

Collecting the interior unknowns produces Ahuh=fhA_hu_h=f_h, where AhA_h is a sparse matrix. The subscript hh denotes the grid spacing.

Let vhv_h be an approximation, and define its algebraic error and residual by

eh=uh−vh,rh=fh−Ahvh.e_h=u_h-v_h, \qquad r_h=f_h-A_hv_h.

These quantities satisfy Aheh=rhA_he_h=r_h. The residual is computable without knowing the solution, whereas the error generally is not. Multigrid uses this error equation to construct a correction rather than attempting to estimate the solution error directly.

A relaxation method updates the approximation using inexpensive local operations. For weighted Jacobi relaxation,

vh new=vh+ωDh−1(fh−Ahvh),v_h^{\,\mathrm{new}} = v_h+\omega D_h^{-1}(f_h-A_hv_h),

where DhD_h is the diagonal of AhA_h. The error therefore evolves under the matrix Sh=I−ωDh−1AhS_h=I-\omega D_h^{-1}A_h. For the one-dimensional three-point Poisson operator, an interior Fourier mode with dimensionless frequency θ\theta has amplification factor

S^h(θ)=1−ω(1−cos⁡θ).\widehat S_h(\theta)=1-\omega(1-\cos\theta).

If θ\theta is small, this factor is close to one: the mode changes very little. For oscillatory modes, an appropriate weight produces much stronger damping. For example, ω=2/3\omega=2/3 bounds the amplification magnitude by 1/31/3 over the usual one-dimensional high-frequency range π/2≤∣θ∣≤π\pi/2\leq|\theta|\leq\pi.

This selective damping is called the smoothing property. After a few sweeps, the remaining error is often smooth relative to the fine grid, even if it is not small. A coarse grid can represent such slowly varying error with fewer unknowns. Crucially, “smooth” is relative to both the grid and the operator: for anisotropic or strongly heterogeneous equations, algebraically persistent error need not look smooth in ordinary geometric coordinates.

Without coarse correction, these persistent components cause slow convergence. For standard Poisson discretizations, the condition number grows like h−2h^{-2}, and classical stationary iterations typically require increasingly many sweeps under refinement. Multigrid addresses this growth by changing the scale on which the remaining error is treated.

The two-grid correction mechanism

The fundamental multigrid operation is a two-grid cycle. Suppose the fine-grid system is Ahuh=fhA_hu_h=f_h, and a smaller coarse system uses an operator AHA_H, usually with H>hH>h. Two transfer operators connect the spaces: restriction RR maps fine-grid residuals to coarse-grid right-hand sides, while prolongation PP maps coarse-grid corrections back to the fine grid.

A correction cycle consists of five operations:

  1. Apply several pre-smoothing sweeps to the current approximation.
  2. Compute the fine-grid residual rh=fh−Ahvhr_h=f_h-A_hv_h.
  3. Restrict it and solve AHeH=RrhA_He_H=Rr_h.
  4. Correct the approximation by vh←vh+PeHv_h\leftarrow v_h+Pe_H.
  5. Apply several post-smoothing sweeps.

The coarse equation is an equation for a correction, not ordinarily a new approximation to the entire fine-grid solution. Consequently, a recursive coarse correction is normally initialized with zero. If the coarse equation is solved exactly, the error after the correction alone is

eh new=(I−PAH−1RAh)eh.e_h^{\,\mathrm{new}} = \left(I-PA_H^{-1}RA_h\right)e_h.

The complete two-grid error-propagation operator is therefore

ETG=Spostν2(I−PAH−1RAh)Spreν1,E_{\mathrm{TG}} = S_{\mathrm{post}}^{\nu_2} \left(I-PA_H^{-1}RA_h\right) S_{\mathrm{pre}}^{\nu_1},

where ν1\nu_1 and ν2\nu_2 are the numbers of smoothing sweeps.

For regularly nested meshes, prolongation often uses linear interpolation in one dimension and bilinear or trilinear interpolation in higher dimensions. A common one-dimensional restriction is full weighting:

(Rr)j=14r2j−1+12r2j+14r2j+1.(Rr)_j=\frac14r_{2j-1}+\frac12r_{2j}+\frac14r_{2j+1}.

Simple injection, which retains selected fine-grid values, is another possibility, but its suitability depends on the equation and the surrounding algorithm. Restriction and prolongation are not interchangeable: they act on different mathematical objects and must be coordinated with the coarse operator.

There are two main ways to define AHA_H. Rediscretization applies the original discretization procedure directly to the coarse mesh. The Galerkin construction instead uses

AH=RAhP.A_H=RA_hP.

For a symmetric positive-definite matrix, the common variational choice R=PTR=P^T gives AH=PTAhPA_H=P^TA_hP. Provided PP has full column rank, the resulting coarse matrix is also positive definite. Exact correction then removes every error in the range of PP.

Neither smoothing nor coarse correction is sufficient by itself. A small coarse space cannot represent arbitrary fine-grid error, while a cheap smoother may barely affect slowly varying components. Good two-grid design makes their strengths complementary. Post-smoothing is useful because prolongation and coarse correction can leave or create components that the smoother handles efficiently.

Recursive cycles and computational complexity

A two-grid method becomes a multigrid method when its coarse equation is itself solved approximately by another two-grid procedure. The hierarchy continues until the coarsest problem is small enough for an inexpensive direct solution, such as Gaussian elimination. Levels need not correspond to uniform spatial meshes, but each normally contains fewer unknowns than the preceding level.

In a V-cycle, each level makes one recursive visit to the next coarser level. The algorithm descends through the hierarchy by smoothing and restricting residuals, then ascends by prolongating corrections and post-smoothing. A W-cycle makes two recursive coarse visits at each noncoarsest level, giving a more accurate coarse correction at greater expense. An F-cycle uses a nonuniform visit pattern intermediate between these strategies; precise conventions for naming and organizing F-cycles vary.

Let the finest level contain NN unknowns, and suppose each coarser level contains approximately 1/q1/q as many. If smoothing, residual evaluation, and transfer each cost an amount proportional to the level size, a V-cycle costs

TV(N)=O ⁣(N+Nq+Nq2+⋯ )=O(N).T_V(N) = O\!\left(N+\frac{N}{q}+\frac{N}{q^2}+\cdots\right) = O(N).

This is a statement in asymptotic notation, with constants depending on stencil sizes and implementation. For a W-cycle, the recurrence is approximately

TW(N)=cN+2TW(N/q).T_W(N)=cN+2T_W(N/q).

It gives linear work when q>2q>2, but O(Nlog⁡N)O(N\log N) when q=2q=2. Thus a W-cycle with standard factor-two coarsening in every coordinate has different complexity in one dimension than in two or three dimensions.

Full multigrid, also called nested iteration, addresses the cost of obtaining a good initial approximation. It first solves on a coarse grid, prolongates that solution to the next finer level, applies a small number of cycles, and repeats until reaching the finest grid. This differs from an ordinary correction cycle: the transferred quantity is now a full solution approximation.

For a stable discretization of order pp, the discretization error often behaves like O(hp)O(h^p) in a suitable norm, assuming sufficient solution regularity. Full multigrid can attain an algebraic error comparable to that discretization error in O(N)O(N) work if interpolation is sufficiently accurate and a fixed number of cycles per level yields adequate reduction. The objective is not to solve each intermediate discrete system to machine precision.

These complexity claims require qualifications. A linear-cost cycle does not guarantee a linear-cost solve if its convergence factor worsens with refinement. Likewise, the number of unknowns alone does not control costs when coarse matrices become dense or interpolation becomes expensive. Optimality requires both bounded work per cycle and suitably uniform convergence.

Convergence theory and the role of coarse spaces

Multigrid convergence rests on two complementary requirements. First, the smoother must reduce error components that are poorly represented on the coarse level. Second, the coarse space must approximate the components that the smoother reduces only weakly. These are often formalized as a smoothing property and an approximation property, although their exact mathematical forms depend on the problem and analysis.

For symmetric positive-definite AA, a natural measure of error is the energy norm

∥e∥A=(eTAe)1/2.\|e\|_A=(e^TAe)^{1/2}.

With the Galerkin operator AH=PTAPA_H=P^TAP, exact coarse correction has the form

C=I−P(PTAP)−1PTA.C=I-P(P^TAP)^{-1}P^TA.

The corrected error satisfies PTACe=0P^TACe=0. Thus coarse correction is an orthogonal projection in the AA-inner product onto the energy-orthogonal complement of the coarse space. Equivalently, it chooses the coarse correction that minimizes the remaining energy error.

A representative approximation estimate for elliptic problems on quasi-uniform meshes is

inf⁡vH∥vh−PvH∥0≤CH∥vh∥A,\inf_{v_H}\|v_h-Pv_H\|_0 \leq CH\|v_h\|_A,

with appropriately scaled discrete norms and a constant CC independent of mesh size. Such an estimate expresses how well coarse functions approximate fine functions whose energy is controlled. Combined with suitable relaxation estimates, it can yield convergence factors bounded away from one independently of mesh refinement. The precise assumptions include regularity, mesh quality, boundary conditions, and the relation between the discrete energy and the underlying differential operator.

Fourier analysis provides another influential viewpoint. Local Fourier analysis studies idealized infinite or periodic grids, decomposing error into frequency components and tracking how smoothing and transfer act on them. Coarsening couples groups of fine-grid frequencies because distinct fine-grid modes can have identical samples on the coarse grid. Consequently, analyzing only the damping of each isolated frequency is insufficient for a complete two-grid prediction. The method is particularly useful for comparing relaxation weights, transfer stencils, and coarsening strategies on structured meshes.

More general theories interpret multigrid through decompositions of a vector space into level-dependent subspaces. This connects multigrid with domain decomposition and successive subspace correction methods. The resulting estimates often depend on stable decompositions and controlled interactions among subspaces rather than on geometric frequency alone.

These theories explain why convergence is not automatic. A smoother may damp many modes effectively while leaving a component absent from the coarse space. Conversely, an excellent approximation space cannot compensate for unstable relaxation. Robust methods must also control how convergence depends on coefficient contrast, anisotropy, polynomial degree, and physical parameters, not merely on mesh spacing.

Geometric multigrid and discretization-aware design

Geometric multigrid constructs its hierarchy from meshes and discretization spaces. In the finite element method, nested meshes often generate nested spaces,

V0⊂V1⊂⋯⊂VL.V_0\subset V_1\subset\cdots\subset V_L.

Prolongation then represents a coarse finite element function in the finer basis. For conforming nested spaces with consistently assembled bilinear forms, Galerkin coarse operators arise naturally from the variational formulation. Geometric information also helps define boundary treatment, quadrature, and physically meaningful smoothers.

Uniform mesh refinement is only one possibility. Local adaptive refinement concentrates unknowns near singularities, interfaces, or boundary layers. A multilevel solver must then manage nonuniform refinement, hanging-node constraints, and level interfaces. Local multigrid variants avoid unnecessary work in unrefined regions, but require transfer and smoothing rules that maintain compatibility across refinement boundaries. The behavior of the solver can depend on how these local levels are organized, not simply on the final mesh.

Anisotropy gives a clear example of why geometric information matters. Consider

−∂2u∂x2−ε∂2u∂y2=f,0<ε≪1.-\frac{\partial^2u}{\partial x^2} -\varepsilon\frac{\partial^2u}{\partial y^2}=f, \qquad 0<\varepsilon\ll1.

Errors varying rapidly in the weakly coupled yy-direction can have low energy relative to the dominant xx-coupling. Point relaxation may barely reduce them, although they are geometrically oscillatory. Line relaxation solves coupled groups of unknowns along the strongly coupled direction, while semicoarsening reduces resolution in selected directions. Suitable combinations can recover convergence that standard point smoothing and uniform coarsening lose.

High-order methods introduce another hierarchy parameter: polynomial degree. pp-multigrid reduces approximation degree rather than, or in addition to, mesh resolution. hphp-multigrid combines degree reduction and mesh coarsening. In spectral-element and discontinuous Galerkin settings, high-order matrix-free operations can be paired with a lower-order coarse representation. Smoothers may use blocks associated with elements, vertices, or overlapping patches to address couplings that scalar updates do not handle effectively.

Boundary conditions must remain consistent across levels. With Dirichlet data, corrections normally satisfy homogeneous versions of the prescribed conditions. For a pure Neumann Poisson problem, constants belong to the null space, so the system is singular. Solvability requires compatibility of the right-hand side, and the solution must be specified modulo constants, often by imposing zero mean. Transfers and coarse solvers must preserve the relevant null space rather than treating singularity as an incidental numerical defect.

Geometric multigrid can have very low storage and arithmetic costs because operators and transfers may be evaluated from compact stencils or element kernels. Its main practical demand is access to a usable hierarchy of discretizations, which may not exist when only an assembled matrix is available.

Algebraic multigrid

Algebraic multigrid constructs a hierarchy primarily from the entries and connectivity of a matrix. It is therefore applicable when geometric meshes are unavailable, inconvenient, or insufficient to describe the important couplings. The matrix defines a graph whose vertices represent unknowns and whose edges represent interactions. Coarsening selects or combines variables, while interpolation determines how coarse variables represent persistent fine-level error.

Classical algebraic multigrid is especially well suited to many scalar diffusion discretizations with M-matrix-like structure. A strength-of-connection criterion identifies couplings likely to determine slowly reduced error. A representative row-based criterion marks jj as strongly connected to ii when

−aij≥θmax⁡k≠i(−aik),-a_{ij}\geq\theta\max_{k\ne i}(-a_{ik}),

for a threshold 0<θ≤10<\theta\leq1, in a setting with the appropriate sign structure. This formula is not universal: nonsymmetric matrices, positive off-diagonal entries, and coupled systems often require different definitions of strength.

Classical coarsening divides variables into coarse and fine sets. Interpolation estimates the error at fine variables from neighboring coarse variables, commonly using approximate relations suggested by Ae≈0Ae\approx0 at points where relaxation has become ineffective. The central object is therefore algebraically smooth error, not necessarily a function that varies slowly in physical space. Galerkin products construct successive coarse matrices once interpolation and restriction are chosen.

Aggregation-based methods group variables into aggregates and build coarse basis functions from those groups. In smoothed aggregation, a tentative interpolation operator is formed using aggregates and candidate near-null-space vectors, then modified by a smoothing step. For scalar diffusion, a constant vector is often an important candidate. For three-dimensional linear elasticity, the six rigid-body modes—three translations and three rotations—provide the corresponding physical information. Supplying these modes helps the coarse space capture error associated with nearly strain-free displacement.

Adaptive and bootstrap approaches enrich this process using representative error vectors generated by relaxation or approximate eigenvector calculations. The goal is to discover troublesome components when they cannot be specified reliably in advance. Such methods can improve robustness for difficult operators, but require additional setup work, storage, and decisions about how many test vectors to retain.

Algebraic hierarchy quality is judged partly through grid complexity and operator complexity:

Cgrid=∑ℓ=0Lnℓn0,Cop=∑ℓ=0Lnnz⁡(Aℓ)nnz⁡(A0).C_{\mathrm{grid}} = \frac{\sum_{\ell=0}^{L}n_\ell}{n_0}, \qquad C_{\mathrm{op}} = \frac{\sum_{\ell=0}^{L}\operatorname{nnz}(A_\ell)} {\operatorname{nnz}(A_0)}.

Here level 00 is finest, and nnz⁡\operatorname{nnz} counts nonzero entries. A hierarchy with few levels can still be costly if its coarse matrices have extensive fill. Interpolation truncation and sparsification can reduce that cost, but may weaken approximation quality or alter important operator properties. Algebraic multigrid therefore balances convergence against hierarchy construction, memory use, and application cost.

Nonlinear equations and use as a preconditioner

For nonlinear equations, the linear residual-correction identity no longer directly supplies a coarse error equation. The full approximation scheme, usually abbreviated FAS, instead transfers a full approximation and modifies the coarse right-hand side to preserve consistency between levels. Suppose the fine equation is Fh(uh)=fhF_h(u_h)=f_h, and vhv_h is the current approximation.

Let IhHI_h^H transfer solution approximations and RhHR_h^H restrict residuals. After pre-smoothing, define

vH0=IhHvh,v_H^0=I_h^Hv_h,

and

fHFAS=FH(vH0)+RhH(fh−Fh(vh)).f_H^{\mathrm{FAS}} = F_H(v_H^0)+R_h^H\bigl(f_h-F_h(v_h)\bigr).

The coarse problem is FH(uH)=fHFASF_H(u_H)=f_H^{\mathrm{FAS}}. Its solution produces the correction

vh←vh+PHh(uH−vH0),v_h\leftarrow v_h+P_H^h(u_H-v_H^0),

followed by post-smoothing. If vhv_h already solves the fine equation exactly, then uH=vH0u_H=v_H^0 satisfies the coarse equation, so no correction is needed. This fixed-point consistency is a defining feature of FAS.

The coarse right-hand side is also often written as RhHfh+τHR_h^Hf_h+\tau_H, where

τH=FH(IhHvh)−RhHFh(vh).\tau_H=F_H(I_h^Hv_h)-R_h^HF_h(v_h).

The tau correction accounts for the difference between the coarse operator applied to the transferred approximation and the restricted fine operator. It allows fine and coarse nonlinear models to differ while remaining consistent at the current approximation. When all operators are linear and the transfers are chosen compatibly, FAS reduces to ordinary coarse-grid correction.

Nonlinear smoothing may use pointwise nonlinear solves, nonlinear block relaxation, or local applications of Newton’s method. FAS is useful in nonlinear diffusion and other problems where an effective coarse nonlinear model is available. Another major strategy is Newton–multigrid: Newton’s method forms a linearized equation involving a Jacobian matrix, and multigrid approximately solves or preconditions that equation. These approaches differ in whether the multilevel hierarchy acts directly on the nonlinear problem or on successive linearizations.

For linear problems, one or more multigrid cycles can define an approximate inverse M−1M^{-1}, used within a Krylov subspace method. This is called preconditioning. A cycle that is not sufficiently robust as a stand-alone iteration may nevertheless be very effective inside an outer Krylov iteration, which combines successive correction directions.

Solver compatibility is important. The conjugate gradient method requires a symmetric positive-definite preconditioner in its standard formulation. Symmetric smoothing arrangements and compatible Galerkin transfers can provide this structure. Nonsymmetric problems commonly use GMRES or related methods. If the multigrid action changes between applications—for example, through variable inner stopping criteria—a flexible Krylov method may be required rather than a formulation assuming a fixed linear preconditioner.

Large-scale implementation, applications, and limitations

Multigrid implementation separates naturally into setup and solution phases. Setup constructs meshes or coarse spaces, transfer operators, coarse matrices, and smoother data. The solution phase applies cycles to one or more right-hand sides. Algebraic setup may be considerably more expensive than a single cycle, so reuse can be valuable for repeated solves with the same matrix or closely related matrices. Conversely, changing coefficients or geometry may require hierarchy updates to maintain convergence.

On parallel computers, fine levels usually provide ample independent work, but coarse levels eventually contain too few unknowns to occupy all processors efficiently. Neighbor exchanges, synchronization, and coarse solves can then dominate runtime even when arithmetic complexity remains linear. Processor agglomeration reduces the number of participating processes on coarse levels, while redistribution changes ownership to improve balance. These measures exchange additional data movement during transitions for less idle time and lower communication overhead afterward.

Smoother choice is strongly influenced by hardware. Weighted Jacobi and Chebyshev polynomial smoothers offer substantial parallelism and often suit graphics processing units. Lexicographic Gauss–Seidel has sequential dependencies; colored or block variants expose more concurrency but change convergence behavior and communication patterns. Matrix-free implementations can avoid storing fine-grid matrices, especially for structured or high-order discretizations, although coarse operators and transfer data may still require explicit storage.

Diffusion and elliptic equations remain central applications. Pressure equations arising in incompressible-flow algorithms often lead to Poisson-like systems suitable for multigrid. Groundwater models introduce large coefficient contrasts, while elasticity requires preservation of rigid-body modes. Electromagnetic formulations can contain gradient-related null spaces and compatibility structures that ordinary scalar interpolation does not preserve. These problems motivate operator-specific coarse spaces, block methods, and auxiliary-space constructions rather than a single universal recipe.

Important limitations arise for indefinite, strongly nonsymmetric, and tightly coupled systems. For high-frequency Helmholtz problems, standard elliptic smoothers can fail and coarse grids may not resolve wave propagation adequately. Convection-dominated equations can require directionally informed transfers and stabilization-aware relaxation. Navier–Stokes equations and other saddle-point systems often use block preconditioners, applying multigrid to selected blocks rather than treating the entire matrix as a scalar diffusion operator.

Practical evaluation therefore measures more than iteration count. Relevant quantities include setup time, cycle time, operator complexity, communication cost, and total time to reach a prescribed tolerance. Residual reduction must also be interpreted carefully: a small residual does not necessarily imply a proportionally small solution error when a system is ill-conditioned. In discretized differential equations, stopping criteria are often chosen so that algebraic error is suitably below the accuracy required of the numerical solution, rather than driving the residual to the limits of floating-point arithmetic.