Hierarchical Grid Structure

The primary reason why AMR is difficult to code is the data structure problem. Almost all of the current AMR methods for structured grids are designed for 2-D or 3-D problems. Although there should be no big change when implemented for 1-D problems, many features which appear only in higher dimensions can be simplified. Here we discuss only the 1-D structure. The 2-D data structure will be described in a later report, Part II[11].

The data in the AMR algorithm has several levels. If u(ix, iu, ilevel) were used to store the data, it would be extremely wasteful of memory, because at higher refined levels, only a very small part of the grid is used. In order to efficiently manage all the discrete points at the same level, we need to cluster them into several disconnected segments, called patches, and treat the patch as the basic data unit. According to the grid structure proposed by Berger([2,3]), a patch should have the following attributes:

• level of the current patch
• integration time of the current patch
• time step-size $\Delta t$ for this patch
• number of ghost boundaries in each direction (only one direction in 1D)
• number of buffer zones in each direction (only one direction in 1D)
• number of grids in each direction (only one direction in 1D)
• logical grid index for each point
• spatial step-length in each direction (only $\Delta x$)
• physical grid location for each point in this patch (only xposition)
• solution for each point in this patch--u₁, u₂...
• pointers to parent patches (only one parent in 1D)
• refinement ratio between its parent and current patch
• pointers to the child grids
• refinement ratio between its child and the current patch
• multiple pointers to the siblings (no siblings in 1D).

We have indicated the simplification (included in parenthesis) for each attribute. The most important of these simplifications is that there is only one parent and no siblings for patches in a 1-D AMR grid. This simplifies the algorithms for clustering, refining, projection and injection, and integration. We will talk about this in the next section.

Our implementation of the data structure is done using an indexed linear array, which can be easily implemented using Fortran, C or C ++. First we define some notation. Let G denote the whole hierarchical grid, G_i,j the j-th patch at the i-th level, $G_i = \bigcup_{i}G_{i,j}$ the grid at the i-th level. For each patch, we use the notation nxbe(4), where nxbe(1) to nxbe(2) is the left ghost boundary, nxbe(3)to nxbe(4) the right ghost boundary and nxbe(2) to nxbe(3) the region of interest. Our overall data structure consists of

|n|G₁ | G₂ | ... | G_n|,

where n denotes the total number of levels of the grid. An array stores the starting position of each level. We also have an array to store the level attributes such as the current integration time, time step-size for the current level, number of ghost boundaries, number of buffer zones in the current level and refinement ratio to the parent. For each level grid G_i, the structure consists of

|m_i|p₁|G_i,1|p₂|G_i,2|...|p_mi|G_i,mi|,

where m_i denotes the number of patches in level i and p_j denotes the index of the j-th patch in the coarse grid which is the parent of the patch G_i,j. The goal of introducing p_j is to facilitate the projection and injection operations between the coarse grid and fine grid. The starting position of each patch G_i,j in G_i is also stored for later use. The data structure for each patch G_(i,j) contains the information related to a single mesh. This data structure is very efficient; only a small storage overhead is needed. Because the data structure of each level changes only when refinement takes place, dynamic memory allocation and deallocation is very easy with this data strcture.

It should be noted that some features of the data structure described here apply only to the 1-D problem. In the 2-D case, due to the existence of siblings and multiple parents of each patch, the grid structure for each level should be modified. We will discuss this in detail in Part II [11].