How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?

Question

Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence:

1. Compute the residual $r_i = b-Ax_i$
2. Apply a multigrid cycle to obtain an approximation $\Delta x_i \approx e_i$, where $Ae_i = r_i$.
3. Update $x_{i+1} \gets x_i + \Delta x_i$

The multigrid cycle is some sequence of smoothing, interpolation, restriction, and exact coarse grid solve operations applied to $r_i$ to produce $\Delta x_i$. This is typically a V-cycle or a W-cycle. This is a linear operation so we write $\Delta x_i = B r_i$.

One can interpret this process as preconditioned Richardson iteration. That is, we update $x_{i+1} \gets x_i + B r_i$.

Richardson iteration is a prototypical Krylov subspace method, which suggests the use of multigrid cycles to precondition other Krylov subspace methods. This is sometimes called "accelerating" multigrid with a Krylov method, or alternately can be seen as a choice of a preconditioner for a Krylov method.

Another way to extend the algorithm above is to employ Full Multigrid (FMG). See this answer for a concise description.

In what situations is Krylov-accelerated MG preferable to MG or FMG?

Answer 1

In some cases, (F)MG provides an algorithm with optimal properties. For instance, properly tuned FMG can solve some elliptic problems in a small number of "work units", where a work unit is defined to be the computational effort required to express the problem itself - in this case the operations to form the residual $b-Ax$ on the finest grid. This is such an efficient (hence hard-to-beat) algorithm that it is the basis for an HPC benchmark designed to measure the maximum capacity of a supercomputer to solve realistic physics problems (HPGMG). If such a method is available, it is of course advisable to use it.

However, in many practical cases, an optimal or effective multigrid method is not used. This may be because

• such a method is unknown or unavailable for the given problem
• smoothers and intergrid operators are not sufficient to give textbook convergence
• the coarse grid solver is inexact

In these cases, the solution may be degraded by error which is not reduced as it should be by the multigrid cycle. If this error is contained in a low-dimensional subspace, however, a Krylov method can can solve for this error in a small number of iterations, and hence "clean up" after an imperfect multigrid solve. That is, if $BA$ has a few outlying eigenvalues, a Krylov method should be able to capture the corresponding eigenspaces.

Note that the choice to use a suboptimal method might result in a much "cheaper" multigrid cycle, to the point that Krylov acceleration pays off. That is, there could be problems (and computing systems) where Krylov-accelerated MG can outperform MG. I would be interested in finding a concrete example of this.

(Thanks to @chris above and Matt Knepley who mentioned some of the above in a tutorial)