5.3.1 Relaxation and Multigrid Techniques

Having transformed the given elliptic PDE into a set of linear equations $\mbox{${\bf A}$} \cdot \mbox{$\bf v$}=\mbox{$\bf b$}$, we can apply any iterative technique to find $\mbox{$\bf v$}$.
For example, the Jacobi scheme reads

$$\mbox{$\bf v$}^{n+1} = \left[ \mbox{${\bf I}$} + \frac{1}{4}... ...mbox{$\bf v$}^{n} + \frac{(\Delta l)^{2}}{4} \mbox{$\bf\rho$}$$

The somewhat faster Gauss-Seidel and SOR methods are also easy to apply.

Problem:

The estimated rate of convergence is linked to the largest (by absolute value) eigenvalue of the iteration matrix constructed from $\mbox{${\bf A}$}$.

In the case of the Poisson equation, the Jacobi and Gauss-Seidel iteration matrices have spectral radii that are close to $1$ $\Longrightarrow$Slow convergence!

Solution: Let $\mbox{$\bf e$} \equiv \mbox{$\bf v$}-\mbox{$\bf v$}^{n}$ be the residual error after the $n$-th relaxation step. Convergence depends not only on $\mbox{${\bf A}$}$, but also on the properties of the iterated vector $\mbox{$\bf e$}$. By applying multigrid schemes we may manipulate these properties so as to improve convergence by orders of magnitude.

Let $K \equiv N \cdot M$ be the total number of grid points; the iterated vectors $\mbox{$\bf v$}^{n}$ and $\mbox{$\bf e$}$ are then both of dimension $K$. $\mbox{$\bf e$} \equiv (e_{0}, \dots e_{K-1})$ may be written as a sum of Fourier components, or modes,

$$e_{j} = \frac{1}{K}\sum_{k=0}^{K-1} E_{k} \exp^{-2 \pi ijk/K}$$

where

$$E_{k} = \sum_{j=0}^{K-1} e_{j} \exp^{2 \pi ijk/K}$$

Relaxation is faster for the ``oscillatory'' high wave number modes of $\mbox{$\bf e$}$ than for the ``smooth'', low wave number components.

Multigrid: Double the lattice width: $\Longrightarrow$Each wave number is automatically increased by a factor of two. $\Longrightarrow$Faster convergence of the modes!

Basic procedure:

• Do several iterations on the fine grid, to get rid of the oscillatory modes
• Double the grid spacing by considering only every other lattice point (or by a more refined recipe) and relax the long-wavelength modes through a number of steps.
• If necessary, go through a cascade of such coarsening stages
• Reconstruct the fine grid gradually, using some interpolation scheme.