2D Poisson equation. Multigrid
Multigrid algorithm 
We can write linear equation as
Au = f.
Let v is an approximation to u, e = u - v
is an error and r = f - Av is residual. Then residual equation is
Ae = r.
If we write weighted Jacobi operator as
vnew = Rω vold,
then error reduction equation is
enew = Rωeold.
Weighted Jacobi relaxation smooths the error but low frequencies
are undamped. On the coarse grid, however, this error appears more oscillatory, and relaxation will
be more effective.
Therefore we go to a coarse grid and relax on the residual equation Ae = r,
with an initial guess of e = 0. Later coarse error is interpolated on fine grid and
is used for fine error correction.
Steps 1 - 3 and 5 - 6 are repeated level times.
See also multigrid with fixed boudaries.
- two smoothing Jacobi iterations on ith grid
- compute ith residual
- reduce residual on coarse i+1th grid
- 2rel "deep" Jacobi iterations on the coarsest grid
- ith error is interpolated on fine i-1th grid
and is used for i-1th error correction
- two smoothing Jacobi iterations on fine i-1th grid
 William L. Briggs, Van Emden Henson, Steve F. McCormick
A Multigrid Tutorial
(look at "Tutorial Slides")
Simulations on GPU
updated 7 Aug 2012