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.