multigrid method to solve PDE

I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with multigrid method.

Can someone explain this in detail or at least provide clearly pseudocode or source code, even with good literature for very beginners? Thanks!

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:

2. Project onto a coarse grid (also known as restriction)
3. Approximate the solution on the coarse grid (using some other solver)
4. Project the coarse grid solution onto the finer grid (also known as prolongation)
5. 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.

• Thank you for detailed answer! Now I have some basic knowledge about multigrdi method. Now I have specific question about restriction and prolongation processes. I read that some Restriction matrix R and Interpolation Matrix M and formulas like A2 = RAI used to do projections between grids. But I didn't understand how to construct matrices R and I..Is there any ideas about this? – Nurlan Jan 21 '13 at 9:33
• Look at slides 45-57 of Briggs multigrid tutorial (part 1) that ChristianClason posted. There, Briggs describes the process for Geometric Multigrid Method. That's the simplest explanation that I can find. If you have further questions about it, feel free to post a new question! :) – Paul Jan 21 '13 at 15:10

This site is possibly not a good place to ask for a detailed explanation with pseudocode (as stated in the FAQ, "If you can imagine an entire book that answers your question, you’re asking too much."), so you might want to start with one of the classical books on this topic (listed below) and come back with specific questions about concrete details you have trouble with.

• Briggs is really good! – vanCompute Jan 10 '13 at 17:53

Another classic:

• Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992.

Example codes can be found at MGNet