# How exactly does the *full* multigrid algorithm run?

So I understand (or at least I believe I do) how a V-cycle runs. I've written in Matlab the 1-D, recursive version of a V-cycle. However, when I ran my code for FMG, my solution wasn't converging. I believe my trouble lies in my understanding of the actual FMG part. What I currently know is this:

1. Just prior to the FMG Interpolation, I've relaxed my solution $u$
2. Interpolate both the error and $u$ (?)
3. Execute a 2-grid v-cycle, passing the error into the v-cycle (?)
4. Relax the error (on the 2nd coarsest grid)
5. Interpolate $u$ and the error
6. Update $u$ by adding the error to it.
7. Run a v-cycle, then repeat from step 4.

I'm not sure about the order, but I could also be wrong about what exactly I interpolate and pass into my v-cycle. If I'm missing anything from the algorithm, please let me know.

Where did you come up with interpolating the "error"? (And how do you measure the error?)

On the first visit to a finer grid, the entire solution $u$ must be interpolated, ideally using a higher order operator (e.g., postprocessed/reconstructed solution for FEM). This FMG interpolation is $u^h \gets \mathbb{I}_H^h u^H$. (It's okay to use the a normal interpolation $\mathbb{I}_h^H = I_h^H$, but this typically gives up some efficiency, at least for smooth problems.)

After FMG interpolation, you just apply one or more V-cycles (or W-cycles, etc). (Make sure to run at least one smoother before restricting.) The most common choices are linear defect correction in which only the residual $r^h = A^h u^h - b^h$ is restricted and the Full Approximation Scheme (FAS) which is a natural for nonlinear problems because it avoids global linearization (e.g, Newton or Picard).

In FAS, the fine grid state is restricted using the state restriction operator $\tilde u^H \gets \hat I_h^H \tilde u^h$. State restriction is not required by linear defect correction multigrid (a convenient attribute). The most common state restrictions are nodal injection (for FD and FE) and coarse cell averages (for FV and mixed FE). Now we can write the FAS coarse grid equation (equally valid for nonlinear $A$) as

$$A^H u^H = \underbrace{I_h^H b^h}_{b^H} + \underbrace{A^H \hat I_h^H \tilde u^h - I_h^H A^h \tilde u^h}_{\tau_h^H}$$

where we have identified the coarse representation of the right hand side, $b^H$, and the additional correction $\tau_h^H$ which represents the influence of the fine grid on the coarse grid equation. Note the property that the restriction of the fine grid solution $u^{h*}$ satisfies the coarse grid equation: $A^H \hat I_h^H u^{h*} = b^H + \tau_h^{H*}$. After solving the coarse grid equation, FAS interpolates the change, leading to an updated fine solution $u^h \gets \tilde u^h + I_H^h (u^H - \hat I_h^H \tilde u^h)$.

• The error was calculated as I computed the residuals on proceeding from the finest to coarsest grid. It's initial approximation per grid is just zero, where it's then relaxed by some iterative method. – AlanH Dec 31 '12 at 22:19
• How does the error (of the initial guess at the solution) play a role in all of this? – AlanH Dec 31 '12 at 22:28
• 1. Error is very different from a residual, and generally not available before convergence (because knowing the error accurately means you also know the solution). MG never moves "error", just residuals, state, and state increments. 2. The FMG initial guess on the fine grid is the interpolation of the solution of the last grid, $u^h \gets \mathbb{I}_H^h u^H$. – Jed Brown Dec 31 '12 at 23:17
• In Briggs' two-grid correction scheme specifically mentions interpolating error from the coarse to fine grid. Not to sound obstinate, but is this somehow different from what you have explained? – AlanH Jan 2 '13 at 17:44
• You have likely mixed up the effect of the iteration on the error with the mechanics of the iteration process. In iterative solvers, we frequently talk about the iteration matrix $T = I - P^{-1}A$ and similar quantities. The error in an iteration behaves as $e_{n+1} = T e_n$, but error can never be evaluated a priori and thus never appears in the iteration. The iteration matrix and discussion of the error is an analysis tool, but error can only be evaluated after convergence. – Jed Brown Jan 2 '13 at 22:50