2 Adaptive Mesh Algorithms

This section provides a high-level description of the structured adaptive mesh algorithm. We present the salient features of the method to motivate the abstractions described in Section 3. Further numerical details can be found elsewhere [2,5,15,19].

Adaptive methods may be structured or unstructured, depending on how they represent the numerical solution to the problem. Unstructured adaptive methods [10,11] store the solution using graph or tree representations; these methods are called ``unstructured'' because connectivity information must be stored for each unknown. Structured methods, such as adaptive mesh refinement [2] and structured multigrid algorithms [5,19], employ a hierarchy of nested mesh levels in which each level consists of many simple, rectangular grids. Each rectangular grid in the hierarchy represents a structured block of many thousands of unknowns. Because of these dissimilar data representation strategies, structured adaptive methods require different software support and implementation approaches than unstructured methods. Here we consider only structured adaptive methods.

Structured adaptive mesh methods solve partial differential equations using a hierarchy of nested, locally structured finite difference grids. The grid hierarchy can be thought of as a single composite grid in which the discretization is non-uniform. All grids at the same level of the hierarchy have the same mesh spacing, but successive levels have finer spacing than the ones preceding it, providing a more accurate representation of the solution.

Adaptive mesh methods refine this discretization of space to accurately represent localized physical phenomena (see Figure 1). When creating a new level, the algorithm refines the hierarchy according to an error estimate calculated at run-time. These new higher-resolution grids, called refinement patches, are used only where necessary. In general, the location and size of refinement patches must be computed at run-time, as they cannot be predicted a priori.

  
Figure 1: Three levels of a structured adaptive mesh hierarchy. The eight dark circles represent regions of high error, such as atomic nuclei in materials design applications. The mesh spacing of each level is half of the previous coarser level.

Adaptive mesh algorithms communicate information about the numerical solution between levels of the hierarchy and also among grids at the same level of the hierarchy. Around the boundary of each grid patch is a ghost cell region which locally caches data from adjacent grids or, where no neighboring grids exist, from the next coarser level of the hierarchy. Without the proper software support, managing these bookkeeping details can be difficult because of the irregular and unpredictable placement of refinement patches [9]. Note that ghost cell regions and communication are required by the adaptive mesh method and are not simply artifacts of the parallel implementation.