5.3 Iterative Methods
115
the restriction and interpolation schemes are the most important of these.
The rate of convergence does, of course, depend on the choices made but the
range of performance between the worst and the best methods is probably
less than a factor of two.
The most important property of the multigrid method is that the number
of iterations on the finest grid required to reach a given level of convergence
is roughly independent of the number of grid nodes. This is as good as one
can expect to do - the computational cost is proportional to the number of
grid nodes. In two- and three-dimensional problems with about 100 nodes
in each direction, the multigrid method may converge in one-tenth to onehundredth of the time required by the basic method. An example will be
presented below.
The iterative method on which the multigrid method is based must be a
good smoother; its convergence properties as a stand-alone method are less
important. Gauss-Seidel and SIP are two good choices but there are other
possibilities.
In two dimensions, there are many possibilities for the restriction operator.
If the method described above is used in each direction, the result would be
a nine point scheme. A simpler, but nearly as effective, restriction is the five
point scheme:
Similarly, an effective prolongator is bilinear interpolation. In two dimensions,
there are three kinds of points on the fine grid. Those which correspond to
coarse grid points are given the value at the corresponding point. Ones which
lie on lines connecting two coarse grid points receive the average of the two
coarse grid values. Finally, the points a t the centers of coarse grid volumes
take the average of the four neighbor values. Similar schemes can be derived
for FV methods and 3D problems.
The initial guess in an iterative solution method is usually far from the
converged solution (a zero field is often used). It therefore makes sense t o solve
the equation first on a very coarse grid (which is cheap) and use that solution
to provide a better guess for the initial field on the next finer grid. By the
time we reach the finest grid, we already have a fairly good starting solution.
Multigrid methods of this type are called full multigrid (FMG) methods. The
cost of obtaining the initial solution for the finest grid is usually more than
compensated by the savings on fine grid iterations.
Finally, we remark that it is possible to construct a method in which one
solves equations for approximations to the solution rather than for corrections
at each grid. This is called the full approximation scheme (FAS) and is often
used for solving non-linear problems. It is important to note that the solution
obtained on each grid in FAS is not the solution that would be obtained if
that grid were used by itself but a smoothed version of the fine grid solution;
115
the restriction and interpolation schemes are the most important of these.
The rate of convergence does, of course, depend on the choices made but the
range of performance between the worst and the best methods is probably
less than a factor of two.
The most important property of the multigrid method is that the number
of iterations on the finest grid required to reach a given level of convergence
is roughly independent of the number of grid nodes. This is as good as one
can expect to do - the computational cost is proportional to the number of
grid nodes. In two- and three-dimensional problems with about 100 nodes
in each direction, the multigrid method may converge in one-tenth to onehundredth of the time required by the basic method. An example will be
presented below.
The iterative method on which the multigrid method is based must be a
good smoother; its convergence properties as a stand-alone method are less
important. Gauss-Seidel and SIP are two good choices but there are other
possibilities.
In two dimensions, there are many possibilities for the restriction operator.
If the method described above is used in each direction, the result would be
a nine point scheme. A simpler, but nearly as effective, restriction is the five
point scheme:
Similarly, an effective prolongator is bilinear interpolation. In two dimensions,
there are three kinds of points on the fine grid. Those which correspond to
coarse grid points are given the value at the corresponding point. Ones which
lie on lines connecting two coarse grid points receive the average of the two
coarse grid values. Finally, the points a t the centers of coarse grid volumes
take the average of the four neighbor values. Similar schemes can be derived
for FV methods and 3D problems.
The initial guess in an iterative solution method is usually far from the
converged solution (a zero field is often used). It therefore makes sense t o solve
the equation first on a very coarse grid (which is cheap) and use that solution
to provide a better guess for the initial field on the next finer grid. By the
time we reach the finest grid, we already have a fairly good starting solution.
Multigrid methods of this type are called full multigrid (FMG) methods. The
cost of obtaining the initial solution for the finest grid is usually more than
compensated by the savings on fine grid iterations.
Finally, we remark that it is possible to construct a method in which one
solves equations for approximations to the solution rather than for corrections
at each grid. This is called the full approximation scheme (FAS) and is often
used for solving non-linear problems. It is important to note that the solution
obtained on each grid in FAS is not the solution that would be obtained if
that grid were used by itself but a smoothed version of the fine grid solution;