2D Poisson equation. Multigrid

This GPU based script draws ui,n/4 cross-section after multigrid V-cycle with the reduction level = 6 and "deep" relaxation iterations 2rel. Boundaries are periodic
fi,j = sin(2πi/n) sin(2πj/n)

n rel level ω

Multigrid algorithm [1]

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.

Multigrid V-cycle

  1. two smoothing Jacobi iterations on ith grid
  2. compute ith residual
  3. reduce residual on coarse i+1th grid

  4. 2rel "deep" Jacobi iterations on the coarsest grid

  5. ith error is interpolated on fine i-1th grid and is used for i-1th error correction
  6. two smoothing Jacobi iterations on fine i-1th grid
Steps 1 - 3 and 5 - 6 are repeated level times. See also multigrid with fixed boudaries.

[1] William L. Briggs, Van Emden Henson, Steve F. McCormick   A Multigrid Tutorial (look at "Tutorial Slides")

Simulations on GPU     updated 7 Aug 2012