Elements of the Multigrid Method

What are the components of a multigrid solver [25]? The first step is to discretize the problem. We have already done this in the sections above by deriving lattice field equations for the Poisson equation. The next step is a relaxation method for reducing the errors on a given grid, also presented above. Then, the crucial element of the multigrid method is the coarse grid correction (CGC) cycle. During this process, the current approximation on the fine scale is passed to the next coarser level ($h \rightarrow 2h$), iterations are performed there on a slightly modified problem (a `defect correction' is added [cf. Sect. 2.4.3]), a correction is applied back on the fine scale, and relaxation iterations are again performed there. The additional elements required for the CGC are a restriction operator for passage from fine to coarse scales, an interpolator to go from coarse to fine, and a technique for applying the corrections. The grid Laplacian operator is trivially changed by inserting the new grid size in the finite difference representation. In a full multigrid solver, the CGC is iteratively repeated on increasingly coarse scales to provide corrections from all length scales. Excellent detailed discussions of each of these elements are given in the MG literature [18,21].

To summarize briefly, the restriction operator locally averages the function on the fine scale to obtain the coarse grid value. Typically, this is done by a simple integration formula such as trapezoid rule in a local region around the coarse grid point. For the interpolation step, it is common to use simple linear interpolation. It can be shown that the sum of the orders (each of the discrete operations is accurate to a certain order) of the restriction and interpolation must add up to at least the order of the differential equation being solved, so the rather simple procedures discussed here are sufficient. The correction step computes the difference between the current coarse grid value and a restricted form of the fine grid function, then interpolates this back to the fine scale and adds to the current approximation, so the computational elements are just restriction and interpolation again. Thus a multigrid program is relatively simple and modular, with subroutines only for relaxation, interpolation, restriction, defect correction computation, and correction sweep. We outline the steps in a nonlinear algorithm below.