Multigrid Workbench: Full Multigrid

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

The Multigrid Workbench: Full multigrid

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