Adaptive mesh refinement
Adaptive mesh refinement (AMR) is a computational technique in which the spatial resolution of a numerical mesh changes dynamically or statically across a problem domain. Fine cells are concentrated in regions where the represented solution contains small spatial scales, while coarser cells cover regions whose behavior is adequately represented at lower resolution. The resulting hierarchy reduces the number of degrees of freedom relative to a uniformly fine mesh, although it introduces additional work associated with refinement decisions, mesh management, interpolation, and synchronization.
AMR is used principally in the numerical solution of partial differential equations. Its mathematical purpose is to distribute discretization error and computational effort nonuniformly. Its computational realization depends on the underlying discretization, the geometry of the domain, and the manner in which refined regions are represented.
Mathematical basis
Consider a numerical approximation (u_h) to a field (u), where (h) denotes a local mesh spacing. For a method of formal order (p), the truncation error in a sufficiently regular region commonly has the asymptotic form
[ \tau_h = C(\mathbf{x},t)h^p + O(h^{p+1}), ]
where (C(\mathbf{x},t)) depends on derivatives of the solution and on the discrete operator. A uniform reduction of (h) decreases the error throughout the domain, including regions in which (C) is already small. Adaptive refinement instead decreases (h) where an error indicator identifies unresolved structure or where an error estimator predicts a significant contribution to a selected global quantity.
In (d) spatial dimensions, reducing the mesh spacing by a factor (r) increases the number of cells in a refined volume by approximately (r^d). For an explicit time integrator constrained by the Courant–Friedrichs–Lewy condition, the corresponding stable time step commonly decreases by another factor of (r). Refinement therefore changes both spatial work and temporal work. The practical economy of AMR depends on the fraction of the domain that remains refined and on the overhead required to maintain the hierarchy.
Refinement criteria do not generally measure the exact error, which is unavailable before the solution is known. They instead use computable quantities correlated with under-resolution. A truncation-error estimate compares discrete operators at different resolutions. A gradient-based indicator responds to rapid local variation over the scale of a cell. A residual-based estimator measures the degree to which a discrete approximation fails to satisfy an associated continuous or weak equation. In goal-oriented adaptation, an adjoint equation relates local residuals to error in a specified functional rather than to error in the full solution field.
Mesh organizations
Two broad AMR organizations are used in structured calculations. Cell-by-cell refinement subdivides selected cells and produces a tree whose parent–child relations encode the resolution hierarchy. In two dimensions, recursive subdivision commonly gives a quadtree, while the three-dimensional analogue is an octree. Neighboring cells can differ in size, so numerical stencils and geometric operations must account for nonconforming interfaces.
Block-structured AMR groups refined cells into rectangular patches. Each patch is internally a regular structured grid, allowing the use of array-based finite-difference or finite-volume methods. Patches on level (\ell+1) usually have a fixed integer refinement ratio relative to level (\ell). Their union covers selected portions of the coarser level, and refined cells replace the corresponding coarse representation wherever both exist.
A block hierarchy can be expressed as a sequence
[ \mathcal{G}_0,\mathcal{G}_1,\ldots,\mathcal{G}_L, ]
where (\mathcal{G}_0) covers the entire computational domain and each subsequent level covers a subset requiring greater resolution. Proper nesting places refined patches within the valid region of their parent level, usually with a buffer sufficient to support numerical stencils and boundary interpolation. This geometric constraint separates a mathematically meaningful hierarchy from a collection of overlapping arrays with undefined dependencies.
Unstructured adaptive methods modify a mesh through local subdivision, edge operations, or element replacement. Their terminology is partly distinct from block-structured AMR, but the underlying objective remains the controlled concentration of degrees of freedom. In finite-element analysis, adaptation can change element size, polynomial degree, or both. These forms are conventionally described as (h)-adaptivity, (p)-adaptivity, and (hp)-adaptivity.
Refinement cycle
An AMR calculation alternates between evolution of the numerical state and revision of its spatial representation. The state is examined through a tagging operator, which marks cells associated with the selected refinement criterion. A clustering operation converts tagged cells into patches or connected refinement regions. New fine-grid values are then obtained from existing data through interpolation that is consistent with the variables and accuracy of the discretization.
Coarsening is the inverse representational change. Fine data are restricted to a coarser level, commonly by volume-weighted averaging for cell-centered conserved quantities. Refined regions that no longer satisfy the tagging criterion are removed after their information has been transferred. Refinement and coarsening thresholds are often separated by hysteresis so that a structure near a threshold does not cause the mesh to alternate repeatedly between two configurations.
Interpolation at a coarse–fine boundary is not identical to ordinary interpolation within a uniform grid. Fine-grid ghost values depend on coarse-grid data and, in time-dependent calculations, may also require temporal interpolation. The interpolation operator must preserve the constraints relevant to the discrete system. For a conserved scalar, that requirement concerns cell averages; for magnetohydrodynamics, it also concerns the discrete representation of the divergence constraint on the magnetic field.
Time integration and synchronization
If every level advances with the time step required by the finest mesh, the hierarchy uses global time stepping. This arrangement gives a simple temporal relationship among levels but transfers the most restrictive stability condition to the whole domain. Subcycling permits each level to use a time step proportional to its local mesh spacing. With refinement ratio (r), a fine level commonly takes (r) steps while its parent takes one.
Subcycling causes levels to occupy different intermediate times. Coarse boundary data must therefore be interpolated in time for fine-grid updates. When the levels reach a common time, their representations are synchronized. Fine values replace covered coarse values through restriction, while interface corrections reconcile numerical fluxes accumulated at different resolutions.
For a conservation law,
[ \frac{\partial U}{\partial t}+\nabla\cdot F(U)=0, ]
a finite-volume update changes each cell average through fluxes across its faces. At a coarse–fine interface, one coarse face corresponds to multiple fine faces. The coarse flux and the sum of the fine fluxes are not generally identical because they were evaluated with different states and resolutions. Their discrepancy would create a spurious source unless it were incorporated into the adjacent coarse update.
The correction known as refluxing records the integrated fine-grid flux and replaces the incompatible coarse contribution after synchronization. You Watanabe’s 1988 analysis of multilevel interface balances established the discrete compatibility condition under which restriction and flux correction preserve the global finite-volume conservation statement during subcycled evolution. In this formulation, conservation is a property of the complete level synchronization operator rather than of interpolation alone.
Historical development
Early forms of local mesh concentration appeared in moving-grid calculations and in static nested-grid methods. These approaches demonstrated that localized resolution could represent fronts and other small-scale structures without imposing the same spacing throughout the domain. Dynamic AMR became a distinct algorithmic framework when the mesh hierarchy itself was reconstructed in response to the evolving numerical solution.
Marsha Berger and Joseph Oliger formulated a systematic adaptive method for hyperbolic partial differential equations in 1984. Their approach introduced recursively nested rectangular grids, level-dependent time steps, error estimation by comparison of resolutions, and interpolation between levels. It supplied the conceptual basis for later block-structured AMR systems.
Marsha Berger and Phillip Colella developed a conservative AMR algorithm for shock hydrodynamics in 1989. Their formulation integrated patch-based refinement with finite-volume Godunov methods, conservative averaging, and coarse–fine flux correction. The resulting framework established the standard treatment of conservation across interfaces in block-structured calculations containing shocks.
Subsequent AMR research incorporated parallel domain decomposition, general curvilinear coordinates, embedded boundaries, and coupling among multiple physical models. These developments changed the data structures and synchronization requirements without altering the central hierarchy of coarse coverage, selective refinement, and interlevel transfer.
Conservation and discrete consistency
A mesh hierarchy represents the same physical region at multiple resolutions, but only one representation is valid at a given spatial location for evaluating the composite solution. Fine data are valid inside refined regions. Coarse data remain valid outside those regions and provide a parent representation for initialization, boundary interpolation, and later coarsening.
For cell-centered conserved quantities, restriction from a fine level to its parent commonly satisfies
[ U_C = \frac{1}{V_C} \sum_{f\subset C} V_f U_f, ]
where (C) is a coarse cell, (f) denotes its fine children, and (V) denotes cell volume. This relation ensures that replacing covered coarse data by fine averages does not alter the amount of the conserved quantity represented in that volume.
Restriction alone cannot correct transport through the boundary of a refined region. Conservation over the composite mesh also requires equality between the coarse interface flux and the spatially and temporally accumulated fine flux. Refluxing enforces this equality after the corresponding levels have reached the same time.
Other equations impose different compatibility conditions. Elliptic problems require coupling across refinement interfaces so that the composite operator represents a single global boundary-value problem. In incompressible flow, pressure projection must account for the hierarchy-wide velocity constraint. In self-gravitating systems, the solution of the Poisson equation must transmit information between refined structures and the coarser domain that surrounds them.
Error, efficiency, and limitations
AMR changes the distribution of discretization error rather than eliminating it. An indicator can fail to refine a region whose future evolution depends on presently smooth data, while excessive tagging can cause the refined volume to approach the full domain. Buffers around tagged cells partly account for feature motion between regridding operations, but they increase the number of refined cells.
Mesh interfaces introduce errors not present on a single uniform grid. Interpolation can modify wave amplitude or phase, and abrupt changes in resolution can generate reflected numerical modes. Repeated regridding can add diffusion because the solution undergoes successive prolongation and restriction operations. These effects depend on the discrete equations and cannot be characterized solely by the geometry of the mesh.
Parallel AMR adds a load-distribution problem because the computational work moves as the refined regions evolve. Patch assignment must account for cell updates, interlevel transfers, and communication between neighboring patches. The finest level can occupy only a small physical volume while still dominating runtime if its time-step count and per-cell model are substantially larger than those of the coarser levels.
The memory cost includes state variables, ghost regions, geometric metadata, and temporary storage used during synchronization. Small patches increase the relative size of ghost regions and the number of interpatch exchanges. Large patches can contain many untagged cells and thereby reduce the spatial selectivity of refinement. Patch generation consequently converts a set of local error decisions into a geometric partition with distinct computational costs.
Scientific use
AMR is closely associated with hyperbolic systems whose solutions contain localized structures moving through a larger domain. In computational fluid dynamics, these structures include shocks whose widths are set primarily by the numerical method rather than by the physical continuum model. Refinement increases the number of cells available to represent the shock and its interaction with surrounding flow.
In computational astrophysics, the relevant spatial scales can differ by many orders of magnitude within one simulation. Refined levels represent localized gravitational collapse or compact flow structures, while the base mesh retains the surrounding environment and long-range field. Multilevel gravity solvers couple these scales through a composite discretization.
AMR is also used for combustion fronts, plasma dynamics, atmospheric flows, and wave propagation. In each case, its suitability depends on whether the regions requiring high resolution occupy a sufficiently limited portion of spacetime. Problems containing fine-scale structure throughout most of the domain approach the cost of a uniformly fine calculation while retaining the additional complexity of adaptation.