Numerical Linear Algebra
where the algebra stops being the arithmetic
Ladder

Multigrid — the ladder

3 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 00.250.50.751-1-0.500.51mode frequency θ / πdamping factor per sweeppredicted±0.333measureda coarse grid seestwo routes to one factorsmoothing factor, scanned0.33smoothing factor, closed form0.33worst mode disagreement4.4·10⁻¹⁶63 interior points, one sweepthe left-hand end is what the coarse grid is for

    The error smoothing cannot reach

    One weighted Jacobi sweep multiplies every mode of the error by a number, and the number is a sine. Half the modes are cut by three or better, and the other half come back at 0.999 — which is not a failure of the method but the fact the whole of multigrid is built on.

    rung 1 · iterative
  2. 15731pointsfinest gridone unknown — the recursion bottoms out in a divisionthe coarse operator, two ways‖RA_hP − A_2h‖/‖A_2h‖10⁻¹⁸unknowns / finest grid1.7cycle cost, in fine sweeps12each coarse point reaches three fine ones½, 1, ½ — and the restriction is its transpose

    The same problem on a coarser grid

    Restriction, the coarse operator and interpolation are three matrices with nine distinct entries between them. Two of the three are each other's transpose, and their product with the fine operator is the coarse discretisation exactly — not approximately, entry for entry, at every level.

    rung 2 · iterative
  3. 10¹10¹.³10¹.⁶10¹.⁹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰¹10².²00.250.50.751grid points nresidual reduction per stepJacobiGauss–SeidelV-cycleV-cycle spread, 8× in size0.003Jacobi at n = 1270.99work exponent, fitted0.079the dashed curve is cos(πh), Jacobi's closed formthe flat line is the whole method

    A rate that does not notice the size

    The V-cycle reduces the residual by a factor of ten a cycle at fifteen points and at a hundred and twenty-seven. Jacobi on the same four problems goes from 0.981 to 0.9978, climbing towards one. One of those is a constant and the other is an exponent, and that is the whole distinction the field turns on.

    rung 3 · iterative

All ladders