The main idea behind multigrid is projection. I try to think about it as follows:
Suppose I want to solve a PDE on with a lot of accuracy, so I proceed to discretize the domain (let's say, using finite difference method) on a very fine grid with lots and lots of points. In the end, I setup my system of equations and I'm ready to solve it. I try using my favorite iterative solver (jacobi, gauss seidel, conjugate gradient, etc...). I proceed to wait more than a day and realize my computer is still trying to compute the answer!!!
The reason why these iterative methods aren't working quickly is because (typically) when you setup a large system of equations like this, the matrix itself has eigenvalues extremely close to 1. Why does this matter? Because the rate of convergence of many iterative methods is inversely related to the largest eigenvalue (see Christian Clason's link to Brigg's Multigrid Tutorial Slides, part 1, page 27). So, the closer the largest eigenvalue is to 1, the slower the iterative method is. (Note: this is oversimplifying things a bit, but it helps motivate the need for multigrid).
Obviously, it is always faster to solve the problem if there are fewer unknowns (i.e. on a coarse grid with fewer gridpoints). But more importantly, the solution (or approximate solution) on a coarser grid is a good starting point to solve the problem on a finer grid. This is the key idea behind most (if not all) multigrid methods. Why is this the case? Intuitively, it makes sense, but there is a mathematically rigorous way of justifying this.
Let's look at the fourier modes of the error in an iterative method (for arguments sake, let's say jacobi or gauss seidel) applied to the original fine grid problem. We would see that within the first few iterations, most of the high frequency (highly oscillatory) errors is removed! This is great, but there is low frequency (less oscillatory) error that still remains and doesn't go away quickly. In fact, it is low frequency error that prevents a standard iterative method from converging quickly.
when we solve the problem on a coarser grid (let's say, by an iterative method like jacobi or gauss-seidel), we are essentially able to remove lower frequency errors much more quickly (i.e. in fewer iterations) than on the fine grid. So, if we solve the problem of a coarse grid, we have a solution whose lower frequency errors have been lessed significantly. Thus, it would be useful as a starting point for an iterative method on the finer grid.
While there are different multigrid methods, most of them operate by some variation of following:
- Start with the fine grid problem
- Project onto a coarse grid (also known as restriction)
- Approximate the solution on the coarse grid (using some other solver)
- Project the coarse grid solution onto the finer grid (also known as prolongation)
- Using the projection from 4. as an initial guess, solve the fine grid problem by an iterative method.
For me, the most difficult part of the multigrid method is the projections between grids. The Briggs tutorials suggested by @ChristianClason handle this subject much better than I can.