I need simple explanation of the Multigrid Method or some literature about this.
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:
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.
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, Multigrid Tutorial, SIAM, 2000 (You can download slides here and here) This is a casual source, providing a gentle introduction to multigrid principles, mostly for elliptic problems.
Brandt, Multigrid Techniques, revised edition, SIAM 2011, (or download the pdf). This is a great development of multigrid philosophy and multiscale modeling and stands a good chance of profoundly changing your way of thinking about implicit solvers. Achi Brandt's website contains many more references, including his 2000 Review of Multiscale Scientific Computation.
Trottenberg, Oosterlee, and Schueller, Multigrid, Academic Press, 2001 This has more worked examples than Brandt, including many experiments and details on specific methods, especially in the context of fluid dynamics.
Hackbusch, Multigrid Methods and Applications, Springer, 1985 This provides a rigorous convergence theory, including "multigrid of the second kind" for Fredholm integral operators.
Another classic:
Example codes can be found at MGNet
