Workbench home page | About the workbench | Multigrid algorithm library | German Scientific Computing

Multigrid iterations typically converge at a rate independent of the problem size. They will thus provide a solution with prescribed accuracy in a fixed number of iterations, independent of how fine the mesh is.

However, the finer the mesh, the better accuracy can be expected, and thus the more and more iterations are needed to apply to exploit the accuracy of the discretization. In total, this effect contributes a logarithmic factor to the complexity estimate.

This changes, when better initial values are used to start the multigrid
iteration.
The natural technique is *nested iteration*, where a multigrid method
on the coarser level is used to supply an initial guess by interpolating its
result.

If this is used recursively, the so-called *full multigrid method*
results.
It starts on the coarsest discretization with an exact solver.
These results are interpolated to the next finer grid,
where a few
cycles
(V or W) of the multigrid method are applied.
The result is again interpolated to the next finer grid, where
again a few cycles of multigrid suffice to produce a solution whose
algebraic accuracy and differential accuracy match.

This algorithmic scheme typically requires just one or two V-cycles on each level to maintain truncation error accuracy on each level. The resulting method has optimal complexity in the sense that it produces solutions at cost proportional to the number of unknowns.

Care must be taken to maintain sufficient accuracy in all components of the method, in particular in the initial interpolation operations to the current finest grid.

Ulrich Ruede , Thu Feb 2 21:05:19 MEZ 1995

Updated by Craig C. Douglas