c2006 Gilbert Strang6.3 Multigrid MethodsThe Jacobi and Gauss-Seidel iterations produce smooth errors. The error vector ehas its high frequencies nearly removed in a few iterations. But low frequencies arereduced very slowly. Convergence requires O(N2) iterations—which can be unaccept-able. 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 fewtimes before changing from fine to coarse and coarse to fine. The remarkable resultis that multigrid can solve many sparse and realistic systems to high accuracy in afixed number of iterations, not growing with n.Multigrid is especially successful for symmetric systems. The key new ingredientsare 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. The return step to the fine grid is by an interpolation matrix I = Ih2h.3. The original matrix Ahon the fine grid is approximated by A2h= RAhI onthe coarse grid. You will see how this A2his smaller and easier and faster thanAh. I will start with interpolation (a 7 by 3 matrix I that takes 3 v’s to 7 u’s):Interpolation Iv = uu on the fine (h) grid fromv on the coarse (2h) gridvalues are the u’s.12121 121 121v1v2v3=v1/2v1v1/2+v2/2v2v2/2+v3/2v3v3/2=u1u2u3u4u5u6u7(1)This example has h =18on the interval 0 ≤ x ≤ 1 with zero boundary conditions.The seven interior values are the u’s. The grid with 2h =14has three interior v’s.Notice that u2, u4, u6from rows 2, 4, 6 are the same as v1, v2, v3! Those coarse gridvalues vjare just moved to the fine grid at the points x =14,24,34. The in-betweenvalues u1, u3, u5, u7on the fine grid are coming from linear interpolation between0, v1, v2, v3, 0:Linear interpolation in rows 1, 3, 5, 7 u2j+1=12(vj+ vj+1) . (2)The odd-numbered rows of the interpolation matrix have entries12and12. We almostalways use grid spacings h, 2h, 4h, . . . with the convenient ratio 2. Other matrices Iare possible, but linear interpolation is easy and effective. Figure 6.10a shows thenew values u2j+1(open circles) between the transferred values u2j= vj(solid circles).6.3. MULTIGRID METHODSc2006 Gilbert Strangu1u2= v10 1j=1m=1 m=3j=7uj= sin2jπ8vm=2+√24sin2mπ4(a) Linear interpolation by u = Ih2hv (b) Restriction by R2hhu =12(Ih2h)TuFigure 6.10: Interpolation to the h grid (7 u’s). Restriction to the 2h grid (3 v’s).When the v’s represent smooth errors on the coarse grid (because Jacobi or Gauss-Seidel has been applied on that grid), interpolation gives a good approximation tothe errors on the fine grid. A practical code can use 8 or 10 grids.The second matrix we need is a restriction matrix R2hh. It transfers u on afine grid to v on a coarse grid. One possibility is the one-zero “injection matrix” thatsimply copies v from the values of u at the same points on the fine grid. This ignoresthe odd-numbered fine grid values u2j+1. Another possibility (which we adopt) is thefull weighting operator R that comes from transposing Ih2h.Fine grid h to coarse grid 2h by a restriction matrix R2hh=12(Ih2h)TFull weighting Ru = vFine grid u to coarse grid v141 2 11 2 11 2 1u1u2u3u4u5u6u7=v1v2v3. (3)The effect of this restriction matrix is shown in Figure 6.10b. We intentionally chosethe special case in which uj= sin(2jπ/8) on the fine grid (open circles). Then v onthe coarse grid (dark circles) is also a pure sine vector. But the frequency is doubled(a full cycle in 4 steps). So a smooth oscillation on the fine grid becomes “half assmooth” on the coarse grid, which is the effect we wanted.Interpolation and Restriction in Two DimensionsCoarse grid to fine grid in two dimensions from bilinear interpolation: Startwith values vi,jon a square or rectangular coarse grid. Interpolate to fill in ui,jby asweep (interpolation) in one direction followed by a sweep in the other direction. Wecould allow two spacings hxand hy, but one meshwidth h is easier to visualize. Ahorizontal sweep along row i of the coarse grid (which is row 2i of the fine grid) willc2006 Gilbert Strangfill in values of u at odd-numbered columns 2j + 1 of the fine grid:Horizontal sweep u2i,2j= vi,jand u2i,2j+1=12(vi,j+ vi,j+1) as in 1D. (4)Now sweep vertically, up each column of the fine grid. Interpolation will keep thosevalues (4) on even-numbered rows 2i. It will average those values to find u = I2D von the fine-grid odd-numbered rows 2i + 1:Vertical sweepAverages of (4)u2i+1,2j= (vi,j+ vi+1,j)/2u2i+1,2j+1= (vi,j+ vi+1,j+ vi,j+1+ vi+1,j+1)/4 .(5)The entries in the tall thin coarse-to-fine interpolation matrix I2D are 1,12, and14.The full weighting fine-to-coarse restriction operator R2D is the transpose I2DT,multiplied by14. That factor is needed (like12in one dimension) so that a constantvector of 1’s will be restricted to a constant vector of 1’s. (The entries along each rowof the wide matrix R add to 1.) This restriction matrix has entries14,18, and116andeach coarse-grid value v is a weighted average of nine fine-grid values u:Restriction matrix R =14ITRow i, j of R produces vi,jvi,juses u2i,2jand 8 neighborsThe nine weights add to 11/161/161/8 1/81/161/81/81/162i−1 2i 2i+1u2i,2j/4You can see how a sweep along each row with weights14,12,14, followed by a sweepdown each column, gives the nine coefficients in that “restriction molecule.” Itsmatrix R2D is an example of a tensor product or Kronecker product kron(R, R). A3 by 7 matrix R in one dimension becomes a 9 by 49 restriction matrix R2D in twodimensions.Now we can transfer vectors between grids. We are ready for the geometricmultigrid method, when the geometry is based on spacings h and 2h and 4h. Theidea extends to triangular elements (each triangle splits naturally into four similartriangles). The geometry can be more complicated than our model on a square.When the geometry becomes too difficult, or we are just given a matrix, we turn(in the final paragraph) to algebraic multigrid. This will imitate the multi-scaleidea, but it works directly with Au = b and not with any underlying geometric grid.A