In the numerical solution of partial differential equations (PDE) a discrete domain is chosen where algebraic analogues of the PDEs are solved. One standard method is to introduce a grid and estimate the values of the unknowns at the grid points through the solutions of these algebraic equations. The spacing of the grid points determines the local error and hence the accuracy of the solution. The spacing also determines the number of calculations to be made to cover the domain of the problem and thus the cost of the computation.

For well behaved problems a grid of uniform mesh spacing (in each of the coordinate directions) gives satisfactory results. However, there are classes of problems where the solution is more difficult to estimate in some regions (perhaps due to discontinuities, steep gradients, shocks, etc.) than in others. One could use a uniform grid having a spacing fine enough so that the local errors estimated in these difficult regions are acceptable. But this approach is computationally extremely costly. Besides for time dependent problems it is difficult to predict in advance a mesh spacing that will give acceptable results.

In the adaptive mesh refinement technique we start with a base coarse grid. As the solution proceeds we identify the regions requiring more resolution by some parameter characterizing the solution, say the local truncation error. We superimpose finer subgrids only on these regions. Finer and finer subgrids are added recursively until either a given maximum level of refinement is reached or the local truncation error has dropped below the desired level. Thus in an adaptive mesh refinement computation grid spacing is fixed for the base grid only and is determined locally for the subgrids according to the requirements of the problem.

In our implementation, we maintain a *shadow* hierarchy to estimate
the local truncation error. The shadow hierarchy is a 2:1 coarser copy of
the main grid hierarchy. The grid functions on the main hierarchy are
updated along with those on the shadow hierarchy. This is equivalent to
taking one integration step in the shadow hierarchy and two integration
steps in the main hierarchy. When it is time for regridding, the
truncation error is estimated by subtracting the grid functions on the
shadow hierarchy from the corresponding values on the main hierarchy. The
advantage of this method is that we do not replicate fine grid storage
at regridding times.

When a fine grid is created, the function values at the fine grid points
are obtained through a linear interpolation of the function values at the
grid points of the underlying coarser grid. This initialization of the
fine grid point values is known as * prolongation*.

After a fine grid (nested within a coarse grid) has been integrated the
coarse grid values are updated by injecting the fine grid solution values
onto the coarse grid points. This updating process of the coarse grid
values is called * restriction*.

When the program is run on parallel processors we maintain a *ghost*
region for intra-grid communication. Suppose we distribute the computation
on a grid over several processors we keep a buffer or ghost region along
the inner boundaries of each component grid. The values in the ghost region
are used to updated the inner boundary values of neighboring component
grids.

Next chapter: Berger-Oliger Method

Return to: Table of Contents