Multigrid method

Remarks

Clause 1 follows by composing the error maps $e \mapsto S e$ of the smoother and $e \mapsto (I - P A_H^{-1} R A_h) e$ of the correction. Clause 2 follows from the factorization $M = (A_h^{-1} - P A_H^{-1} R) \, A_h S^{\nu}$ and the two bounds. Consider a family of finite difference or finite element discretizations of an elliptic equation, with mesh widths $h$ and $H = 2h$. Use damped Jacobi smoothing and standard transfer matrices. Under elliptic regularity assumptions, both properties hold with $C$ and $\eta$ independent of $h$, and $\eta(\nu) \to 0$. Then for $\nu$ large enough the two-grid method contracts the error by a factor less than $1$ that does not depend on $h$. Example: for $A_h$ symmetric positive definite and $S = I - A_h / \norm{A_h}_2$ in the matrix norm $\norm{\cdot}_2$, one has $\norm{A_h S^\nu}_2 \le \max_{0 \le t \le 1} t (1 - t)^\nu \norm{A_h}_2 \le \norm{A_h}_2 / (\nu + 1)$. Solving the coarse problem recursively by the same method gives the V-cycle and the W-cycle.

Going deeper

For a student

For elliptic problems, multigrid reaches a fixed accuracy in $O(n)$ operations, which is optimal up to a constant. The analysis splits into the smoothing property, a statement about the smoother alone, and the approximation property, a statement about the discretizations on the two grids. Algebraic multigrid builds the coarse levels from the matrix alone, without a geometric grid. Multigrid is also used as a preconditioner for the conjugate gradient method, and it is among the fastest iterative methods for such problems.