Dynamically adaptive numerical techniques for solving differential equations provide a means for concentrating effort to computationally demanding regions. In the case of hierarchical AMR methods, this is achieved by tracking regions in the domain that require additional resolution and dynamically overlaying finer grids over these regions. Techniques based on AMR start with a base coarse grid with the lowest acceptable resolution that covers the entire computational domain. As the solution progresses, regions in the domain with high solution error and requiring additional resolution are flagged and finer grids are overlaid on the flagged regions of the coarse grid. Refinement proceeds recursively so that regions on the finer grid requiring higher resolution are similarly flagged, and even finer grids are overlaid on these regions. The resulting grid structure is a dynamic adaptive grid hierarchy. The figure below shows adaptive grid hierarchy for the classic Berger AMR formulation.

• Patch based partitioners : In this class of partitioners, distribution decisions are made independently for each newly created grid. The grid may be kept on the local processor or sent in its entirety to another processor. If the grid is considered too large, it may be split. Patch based partitioning techniques induce lots of inter-grid communication but keep intra-grid communication low.

• Domain based partitioners : Domain based partitioners partition the physical domain rather than the grids themselves. The domain is partitioned along with all its belonging grids on all refinement levels.These techniques generate partitions free from inter-grid communication, but can induce larger intra-grid communication overheads. Grids with bad aspect ratios may also be created.

• Hybrid partitioners : Hybrid partitioners combine the two approaches. Using these techniques, partitioning is performed in two steps. The first step uses domain based techniques to generate meta-partitions that are mapped to a group of processors. The second step uses a combination of domain and patch based techniques to optimize the distribution of each meta-partition within its processor group.

AMR Terminology

1. Base Grid : Initial griding of the computational domain, typically a uniform ôcoarseö mesh with minimum required resolution.

2. Grid Hierarchy : Hierarchical grid structure with multiple levels of grid resolution.

3. Time Integration : Solving the PDE on the grid to take one timestep.

4. Local Truncation Error (LTE) : Locally computed error in the PDE solution. Used to identify grid points requiring refinement.

5. Refinement : Addition of finer resolution grids in regions with high LTE. Refinement is performed both in time and space.

6. Regriding : Creating the new grid hierarchy, adding high-resolution grids in refined regions and removing high-resolution grids no longer required. The regriding process includes the initialization of refined grids.

7. Clustering : Combining grid points with high LTE into regular regions to be refined.

8. Prolongation : Transfer of information from a coarser grid to a finer grid. Prolongation is used to initialize higher resolution grids on creation.

9. Restriction : Transfer of information from finer grids to coarser grid. Restriction is performed every timestep to ensure that the solutions on the fine and coarse grids do not diverge.