Chemistry Reference
In-Depth Information
MULTIGRID METHODS
The MG method was developed in the late 1960s and early 1970s. Early
multilevel ideas from Fedorenko were fully developed by Brandt, Hackbusch,
and others into highly efficient PDE solvers.
105,107-109
This method cleverly
utilizes multiple grid levels to accelerate the convergence rate of iterative sol-
vers. The trick is to design a coarse-grid representation such that, if we had the
exact numerical solution on the fine grid, nothing would happen during the
coarse-grid correction process. This is termed
zero correction at convergence.
How Does Multigrid Overcome Critical Slowing Down?
The basic idea of the original MG method is to set up a series of coarser
grids, with each next-coarser grid typically having a grid spacing twice that on
the finer level. After a few iterations on the fine grid, the problem is passed to
the coarser level, iterated there, and then moved to a yet coarser level. This is
repeated until the coarsest grid is reached. For some problems, such as the
Poisson equation, the coarsest grid can contain only one interior point. In
other problems, like the eigenvalue problem, the coarsest level must contain
enough resolution to at least approximately represent the wiggles in the eigen-
functions, so there can be limits on how coarse we can go.
Why does this process work? The main explanation is that components
of the error having wavelengths roughly the size of a small multiple of the grid
spacing on a given level get removed efficiently by the relaxation process.
105
A
careful analysis of the spectral properties of the Gauss-Seidel method shows
that errors with those wavelengths get decimated quickly. Thus, by proceeding
through a range of coarser levels, errors with
all
wavelengths can be removed.
This is one of the few cases in computational science where it almost seems as
if we get something for nothing—in three dimensions, the cost of the updates
on the next coarser level is one eighth that on the fine level, yet by going to the
coarser level, we are solving the hardest part of the problem.
Full Approximations Scheme (FAS) Multigrid, and Full
Multigrid (FMG)
The question one might ask is: Can we design a coarse-grid problem that
possesses the important zero correction at convergence property? Here we will
discuss the full approximation scheme (FAS) multigrid method, since it is gen-
eral in scope.
105,107,108
The FAS approach can be employed to solve both lin-
ear and nonlinear problems, and many of the problems in which we are
interested are nonlinear in nature (Poisson-Boltzmann, eigenvalue, etc.).
We first introduce some of the basic operations in an MG process. We
have already discussed the FD representation, but we need operations that
pass functions between the grid levels. Those are
restriction
(fine to coarse)
