Chemistry Reference
In-Depth Information
Repeat V-cycle
h
Interpolate
Restrict
2h
Interpolate
Restrict
4h
Figure 4
The V-cycle in a multigrid solver. An initial guess is made on the fine level,
iterations are performed, and then the approximate solution is passed to the coarser
level. This process is repeated until the coarsest grid is reached. The solver then
progresses through interpolation (correction) steps back to the finest level. The V-cycle
can be repeated.
level, is termed a V-cycle (Figure 4). The solver can loop back around the
V-cycle as many times as desired until a specified magnitude of the residual
is obtained. If the MG Poisson solver is working properly, the residual
should be reduced by an order of magnitude during each V-cycle. The author
still remembers the first working Poisson MG code he wrote, and how dra-
matic the difference in convergence rate is once the multiple levels are incor-
porated! See Figure 5.
In the preceding discussion, we started on the finest level with some initi-
al approximation and then proceeded through the V-cycle. This approach
works fine, but there is a way to obtain a good initial approximation with little
computational cost called the FMG method (Figure 6). In this approach, itera-
tions are first performed by taking the coarsest level as the starting point (mak-
ing it the current finest grid). The current approximation is then interpolated
to the next level, and one or more V-cycles are performed there. This process is
repeated until the finest grid is reached, at which point a very good preliminary
estimate of the solution on the finest level is generated. The total cost of this
''preconditioning'' is very low, and it is almost always a good idea to use FMG
if we have little or no prior knowledge about the solution on the fine level. If
we do have a good initial guess at the solution, it then makes sense to use that
guess and start with V-cycles on the finest level.
For the Poisson problem, the total number of grid points for all the
grid levels in three dimensions is only a small constant (greater than one)
times the number of fine-grid points (indicated by
N
g
).
58
It is observed that
the convergence rate does not depend on the system size, and the residual
decreases exponentially with the number of iterations, i.e., a plot of the log
of the residual vs. the number of iterations decreases linearly. Thus, the
