TABLE OF CONTENTS Multigrid methods were invented for partial differential equations such as Poisson's equation, but they work on a wider class of problems too. In contrast to other iterative schemes that we have discussed so far, multigrid's convergence rate is independent of the problem size N, instead of slowing down for larger problems. As a consequence, it can solve problems with n unknowns in O(n) time or for a constant amount of work per unknown. This is optimal, modulo the (modest) constant hidden inside the O( ).
Here is why the other iterative algorithms that we have discussed cannot be optimal for the model problem. In fact, this is true of any iterative algorithm that computes approximation x m+1 by averaging values of x m and the right-hand side b from neighboring grid points. This includes Jacobi's, Gauss-Seidel, SOR( ?), SSOR with Chebyshev acceleration (the last three with red-black ordering), and any Krylov subspace method based on matrix-vector multiplication with the matrix T N N; this is because multiplying a vector by T N N is also equivalent to averaging neighboring grid point values. Suppose that we start with a right-hand side b on a 31-by-31 grid, with a single nonzero entry, as shown in the upper left of Figure 6.9. The true solution x is shown in the upper right of the same figure; note that it is everywhere nonzero...
