# Adaptive mesh refinement (AMR) algorithms¶

The basic adaptive refinment strategy used in AMRClaw is
to refine on logically rectangular patches. A single Level 1 grid covers
the entire domain (usually — if it is too large it may be split into
multiple Level 1 grids). Some rectangular portions of this grid are covered
by Level 2 grids refined by some refinement factor *R* in each direction
(anisotropic refinement is now allowed too — see Specifying AMRClaw run-time parameters in setrun.py).
Regions of each Level 2 grid may be covered by Level 3 grids, that are
further refined (perhaps with a different refinement ratio). And so on.

For the hyperbolic solvers in Clawpack the time step is limited by the
Courant number (see Section cfl), and so if the spatial resolution is
refined by a factor of *R* in each direction then the time step will
generally have to be reduced by a factor *R* as well.

The AMR code thus proceeds as follows:

In each time step on the Level 1 grid(s), the values in all grid cells (including those covered by finer grids) are advanced one time step. Before this time step is taken, ghost cells around the boundary of the full computational domain are filled based on the boundary conditions specified in the library routine

bcNamr.f(whereNis the number of space dimensions). Check theMakefileof an application to see where this file can be found.After a step on the Level 1 grid,

Rtime steps must be taken on each Level 2 grid, whereRdenotes the desired refinement ratio in time from Level 1 to Level 2.For each of these time step, ghost cell values must be filled in around all boundaries of each Level 2 grid. This procedure is defined below in Ghost cells and boundary conditions for AMR.

After taking

Rsteps on Level 2 grids, values on the Level 1 grid are updated to be consistent with the Level 2 grids. Any cell on Level 1 that is covered by a Level 2 grid has itsqvalue replaced by the average of all the Level 2 grid cells lying within this cell. This gives a cell average that should be a better approximation to the true cell average than the original value.The updating just described can lead to a change in the total mass calculated on the Level 1 grid. In order to restore global conservation, it is necessary to do a conservation fix up. (To be described…)

This style of AMR is often called *Berger-Oliger-Colella* adaptive
refinement, after the papers of Berger and Oliger [BergerOliger84] and
[BergerColella89].

The Fortran code in $CLAW/amrclaw is based on code originally written by Marsha Berger for gas dynamics, and merged in Clawpack in the early days of Clawpack development by MJB and RJL. The algorithms used in AMRClaw are described more fully in [BergerLeVeque98].

## Ghost cells and boundary conditions for AMR¶

Consider a Level *k > 1* grid for which we need ghost cells all around the
boundary at the start of each time step on this level. The same procedure
is used at other levels.

Some Level k grids will be adjacent to other Level k grids and so any ghost cell that is equivalent to a Level k cell on some other grid has values copied from this this grid.

Some ghost cells will be in the interior of the full computational domain but in regions where there is no adjacent Level k grid. There will be a Level k-1 grid covering that region, however. In this case the ghost cells are obtained by space-time interpolation from values on the Level k-1 grid.

Some ghost cells will lie outside the full computational domain, where the boundary of the Level k grid lies along the boundary of the full domain. For these cells the subroutine

bcNamr(whereNis the number of space dimensions) is used to fill ghost cell values with the proper user-specified boundary conditions, unless periodic boundary conditions are specified (see below).

For many standard boundary conditions it is not necessary for the user to do
anything beyond setting appropriate parameters in *setrun.py* (see
Specifying classic run-time parameters in setrun.py). Only if user-specified boundary conditions are
specified is it necessary to modify the library
routine *bcNamr.f* (after copying to your application directory so as not to
damage the library version, and modifying the *Makefile* to point to the new
version).

There some differences between the *bcNamr.f* routine and the *bcN.f*
routine used for the single-grid classic Clawpack routines (which are found in
*$CLAW/classic/src/Nd/bcN.f*). In particular, it is necessary to check
whether a ghost cell actually lies outside the full computational domain
and only set ghost cell values for those that do. It should be clear how to
do this from the library version of the routine.

If **periodic boundary
conditions** are specified, this is handled by the AMRClaw software along
with all internal boundaries, rather than in *bcNamr.f*. With AMR it is not
so easy to apply periodic boundary conditions as it is in the case of a
single grid, since it is necessary to determine whether there is a grid at
the same refinement level at the opposite side of the domain to copy ghost
cell values from, and if so which grid and what index corresponds to the
desired location.

## Choosing and initializing finer grids¶

Every few time steps on the coarsest level it is generally necessary to revise modify the regions of refinement at all levels, for example to follow a propagating shock wave. This is done by

Flagging cells that need refinement according to some criteria.

Clustering the flagged cells into rectangular patches that will form the new set of grids at the next higher level.

Creating the new grids and initializing the values of

qand also anyauxarrays for each new grid.

Clustering is done using and algorithm developed by Berger and Rigoutsis [BergerRigoutsis91] that finds a nonoverlapping set of rectangles that cover all flagged points and balances the following conflicting goals:

Cover as few points as possible that are not flagged, to reduce the number of grid cells that must be advanced in each time step.

Create as few new grids as possible, to minimize the overhead associated with filling ghost cells and doing the conservation fix-up around edges of grids.

A parameter *cutoff* can be specified (see Specifying AMRClaw run-time parameters in setrun.py) to control
clustering. The algorithm will choose the grids in such a way that at least
this fraction of all the grid points in all the new grids will be in cells
that were flagged as needing refinement. Usually *cutoff = 0.7* is used, so
at least 70% of all grid cells in a computation are in regions where they
are really needed.

Initializing the new grids at Level k+1 is done as follows:

At points where there was already a Level k+1 grid present, this value is copied over.

At points where there was not previously a Level k+1 grid, bilinear interpolation is performed based on the Level k grids.

## Flagging cells for refinement¶

The user can control the criteria used for flagging cells for refinement.

See AMR refinement criteria for details.