During this process, the solver or kernel of a simulation evolves the solution by advancing it forward a specified time interval. Although the solver is the lynch-pin of any numerical simulation, its details are not directly relevant to AMR, because AMR abstracts it into a ``black box'' operation; that is, given the correct input, the solver is expected to produce the correct output, and otherwise is not a concern of the AMR strategy.
Many user codes are written for a single mesh. The input to the user code includes boundary conditions, the initial condition, a routine that defines the differential equations, and other related information such as the time step-size, the spatial step length and set-up information for the solver. We must check what we have before calling the user solver. First, and maybe most importantly, the external boundary routine supplied by the user should not be called inside the user solver without any recoding, because the sub-grid may have only one or no external boundary. We can add a testing procedure to see whether the current patch reaches the boundaries or not in the user's boundary routine. This usually does not work because the information given in the user's boundary routine is not sufficient to do the testing. Another approach is to supply the boundary value outside the solver and set up the user's boundary routine as a dummy inside the user solver. We can include enough information in our boundary routine to do the testing. Most AMR methods, including the Berger's AMR, do not store the solutions for the ghost boundary, and obtain the initial value just before integration. This works only when the solver does not collect boundary values from the parent grid or external boundaries during a one timestep integration. Many fully-discretized PDE solvers with a predictor and second order corrections belong to this category. This kind of solvers can be plugged into our AMR system directly. For a semi-discretized PDE and method of lines (MOL) approach, the values at the ghost boundaries are usually not calculated by the solver but collected from the parent coarse grid or according to the external boundary conditions during the integrations. If an implicit or high order explicit temporal integration method (such as a third order TVD Runge Kutta method [14]) is used, the solutions at intermediate times are required at the ghost boundaries. This is why an implicit or high order explicit integrator cannot be used in Berger's AMR method.
In our AMR system, we store the ghost boundary values as well as the internal node values. For a semi-discretized PDE and a single-step high order explicit method, we compute the time derivatives at the ghost boundaries using the boundary values at the forward time (collected before the time integration of the current patch) and backward time and keep them as constant during a one time-step integration. The external boundary values are collected if the current patch reaches the external boundaries. Then the time derivatives for the internal nodes are computed by the user routine. After that, we advance the whole grid, including the ghost boundaries, one intermediate step. The process continues till the one time-step integration is completed. The implicit integration can be done similarly. For a multi-step method, which needs information from previous time steps, the information at those times should be saved. This requires much more storage to store the grid data structure and solution, and must update values from the old grid to the new grid. We do not support it in our current AMR system.
Given the user solver for a single grid, we can reuse two kinds of routines. First, if the solver collect the boundary values only once and at the beginning of each time integration, we can plug the whole solver (for one time step) into our AMR system without modifications. The only other things we do are some name-matching and parameter-setting between our AMR system and the user solver. If the boundary values are collected more than once by the solver, we need to extract the user's time derivative routine, and use our time integration routines to advance the solutions. Usually the time derivative routine is given by the user for the semi-discretized PDE and MOL approach. So we have no difficulty in achieving high order accuracy by our AMR system.
The evolving algorithm is much more complex when implemented for 2D problems because of the existence of sibling and overlay internal boundaries. Apart from the external boundaries and parent coarse grids, the ghost boundary values are also collected from the internal boundaries. Therefore, we cannot integrate each patch separately if boundary collections are done more than once for a single time step. We will discuss this in Part II [11]..