COMSOL Blog

On Solvers: The V-Cycle Multigrid

Tips & Tricks | Posted on February 13th, 2013 by Valerio Marra

As discussed in On Solvers: Multigrid Methods (referred to as “Part 1″), iterative methods eliminate oscillatory error components efficiently while leaving the smooth ones almost untouched (smoothing property). The main idea behind multigrid methods is to use the smoothing property, spatial aliasing, and the residual correction to the advantage of convergence. Before putting all the pieces of this proverbial puzzle together, we need to introduce residual correction and, even though we talked about it in the previous blog post, dig a little bit more into spatial aliasing. Let’s start with the latter.

Spatial Aliasing and Nested Iteration

In Part 1 we learned that because of spatial aliasing, oscillatory waves of appear as smoother waves on the coarser grid (where we have denoted with the grid having spacing ). On the same line, it can be shown that smooth waves on appear more oscillatory on . It is a good idea then to move to a coarser grid when convergence begins to stall: predominant smooth waves on will appear more oscillatory on where the smoothing property of iterative methods make them more efficient.

This means that coarse grids can be used to generate improved initial guesses as in the following nested iteration procedure:

• Iterate on on the coarsest grid
• …
• Iterate on on to obtain an initial guess for
• Iterate on on to obtain an initial guess for
• Iterate on on to obtain a final approximation to the solution

Nested iteration seems to be a good procedure, but once we are on the fine grid, what happens if we still have smooth error components and convergence begins to stall? This is when the residual equation will come in handy and multigrid methods will show us the way to use it together with nested iteration effectively.

Note: information between the grids is transferred through functions called prolongation (from coarse grid to fine grid) and restriction (from fine grid to coarse grid) operators. Although they represent an important part of multigrid methods and are a fascinating subject, for the sake of brevity we will not cover them in this blog post.

The Residual Equation and Coarse Grid Correction

The solution is unknown while we compute the approximate solution and the norm of the algebraic error is a measure of how well our iterative method is converging to the solution (that can also be written as ). Since the algebraic error is also unknown, we have to rely on a measure that can be computed: the residual   . After some algebra, we find the important relationship between and ; the residual equation . This equation is important because it will lead us to the idea of residual correction: we compute the approximate solution , we compute , we solve directly on thanks to the residual equation, and we then compute a new approximate solution using the definition of the algebraic error: .

Thanks to the residual equation, we can iterate directly on the error and use the residual correction to improve the approximate solution. We have learned that while iterating on , convergence will eventually begin to stall if smooth error components are still present. We can then iterate the residual equation on the coarser grid , return to , and correct the approximated solution first obtained here. This procedure is called coarse grid correction:

• Iterate times on to obtain the approximate solution until desired convergence is reached
• Compute the residual
• Solve the residual equation to obtain the algebraic error (the restriction operator needed by has been omitted)
• Correct with : (the prolongation operator needed by has been omitted)
• Iterate times on to obtain the approximate solution until desired convergence is reached

We now know what to do when convergence begins to stall on the finest grid!

The coarse grid correction outlined above can be represented by this diagram:

Coarse grid correction procedure involving and .

Our First Multigrid Method: The V-Cycle

One question remains about the coarse grid correction: what if we don’t reach the desired error convergence on the coarse grid?

Let’s think about this for a moment. Solving the residual equation on the coarse grid is not at all different from solving a new equation. We can apply coarse grid correction to the residual equation on , which means that we need for the correction step. If a direct solution is possible on , we don’t need to apply the coarse grid correction anymore and our solution method will look like a V (see image below).

V-cycle multigrid solution method.

This solution method is called V-cycle multigrid. It is apparent that multigrid methods are recursive in nature; a V-cycle can have more than three levels, or two V-cycles can be executed sequentially to form the so called W-cycle.

The Full Multigrid V-Cycle

So far we have devoted our attention to the coarse grid correction idea, but how can we take advantage of nested iteration too? Let’s recall that nested iteration generates improved initial guesses thanks to coarse grids. If the initial guess for the first iteration on the fine grid of the V-cycle is obtained from nested iteration, then we have what is called the full multigrid V-cycle. The full multigrid is more expensive but allows for a faster convergence than just the V-cycle. It has to be noted that here we presented the V-cycle, W-cycle, and full multigrid V-cycle in their simplest forms; different variations are adopted where, although the solution procedure is called W-cycle, it hardly resembles the shape of a W. Moreover, in order to solve complex multiphysics problems and reach optimal performances, multigrid methods are not used alone; they can be used to improve the convergence of other iterative methods. This is what happens in COMSOL Multiphysics under the hood!

The techniques that multigrid methods put together are used since a long time back and have been known for their limitations. The beauty of multigrid methods comes from their simplicity and the fact that they integrate all these ideas in such a way that limitations are overcome, and the resulting algorithm is more powerful than the sum of its elements.

Resources

• This series of blog posts was inspired by A Multigrid Tutorial by William L. Briggs. Briggs’ tutorial guided me through the coding of my first CFD solver. I encourage anyone interested in multigrid methods to read it.
• As already highlighted in Part 1 of this blog post duo, more details on COMSOL Multiphysics solvers can be found in the article Fast Solvers for Complex Problems, written by my colleague Jacob Yström for Machine Design. Comparison between direct and iterative solver with respect to memory usage and CPU time are also discussed in the article.

Comments

Login to Comment