The classic iterative method essentially only plays a "smooth" effect, even if it can quickly eliminate the high-frequency part of the residual, but the effect is not very good for the low-frequency part. The basic idea of the multi-grid method is: first of all Establish a set of coarse and fine grids for the fixed solution area, and form the corresponding difference or finite element discrete equation. For this discrete equation, first use the usual iterative method on the fine grid, such as Richardson iteration and Gauss-Seidel iteration. Iteratively eliminate the high-frequency part of the residual, and then transfer the low-frequency part of the residual to the coarse grid for correction. After several cycles, a solution that satisfies the accuracy is obtained. Since the residual correction is performed on the coarse grid , So the corresponding workload is relatively small.

The Jacobi and Gauss-Seidel iterations produce smooth errors. The error vector e has its high frequencies nearly removed in a few iterations. But low frequencies are reduced very slowly. Convergence requires O(N2) iterations - which can be unacceptable. The extremely effective multigrid idea is to change to a coarser grid, on which "smooth becomes rough" and low frequencies act like higher frequencies.

On that coarser grid a big piece of the error is removable. We iterate only a few times before changing from fine to coarse and coarse to fine. The remarkable result is that multigrid can solve many sparse and realistic systems to high accuracy in a fixed number of iterations, not growing with n.

Multigrid is especially successful for symmetric systems. The key new ingredients are the (rectangular !) matrices R and I that change grids:

  1. A restriction matrix R transfers vectors from the fine grid to the coarse grid

  2. An interpolation matrix I=I2hh returns to the fine grid

  3. The original matrix Ah on the fine grid is approximated by A2h=RAHI on the coarse grid. This A2h is smaller and easier and faster than Ah. I will start with interpolation (a 7 by 3matrix I that takes 3 v's to 7 u's):
    12[121121121][v1v2v3]=[v1/2v1v1/2+v2/2v2v2/2+v3/2v3v3/2]=[u1u2u3u4u5u6u7]
    Interpolation Iv=u, u on the fine (h) grid, v on the coarse (2h) grid.

The second matrix we need is a restriction matrix Rh2h. It transfers u on a fine grid to v on a coarse grid. One possibility is the one-zero "injection matrix" that simply copies v from grid values u2j+1. Another possibility (which we adopt) is the full weighting operator R that comes from transposing I2hh.

Fine grid h to coarse grid 2h by a restriction matrix R=12IT
14[121121121][u1u2u3u4u5u6u7]=[v1v2v3]

Geometric multigrid, GMG

Get the iterative result from the original mesh x1, and we require equations satisfied
A1e1=r1=bAx1
Equivalent in coarse grid to solve
A1e2=r2
Among them, r2 is obtained by down sampling from r1 which is equivalent to the left multiplication matrix
C12=[wc1wc0wc1wc1wc0wc1wc1wc0wc1]
After solving the e2 in which the low-frequency error is suppressed, the e1 is obtained by interpolation, and the x1+e1 is used as the new solution.

Interpolation is equivalent to left multiplication matrix
I21=[wi1wi0wi1wi1wi0wi1].
Sampling the residual to a coarse grid, and interpolate the solution to a fine grid after solving, that is r2=C12r1, e1=I21e2.

Comparison available A2=C12A1I21,

Multigrid algorithm solution A1x=b,

  1. If the grid size is small enough to solve the equation accurately or imprecisely, return the solution;.
  2. Otherwise ,Solve iteratively with x0=0 as the initial iterative step, obtain x1. And calculate residual r1=A1x1.
  3. Coarse the residuals r2=C12r1.
  4. order A2=C12A1I21, Solve A2e2=r using multi-grid algorithm.
  5. Interpolate the solution and accumulate x2=x1+I21e2.
  6. Iterate with x2 as the initial iterative step to obtain x3.