Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading Press et. al., "Numerical Recipes" book, which contain section about multigrid method for numerically solving boundary value problems.

However, the chapter is quite brief and I would like to understand multigrids to a point where I will be able to implement more advanced and faster version than that provided in the book.

The tutorials I found so far are very elaborate and aimed on graduate students. I have notions on several related topics (relaxation methods, preconditioning), but still the combination of PDEs and the multigrid methods is mind-blowing for me...

Thanks for any tips for a good explanatory book, website or article.

share|improve this question
    
What equation you are trying to solve, there are many newly developed fast multigrid methods like AMG, local multigrid, etc. –  Shuhao Cao Sep 20 '12 at 3:44
    
@ShuhaoCao I am especially interested in linear elliptic (Poisson) equation, but I would like to understand how to use multigrid with other PDEs (e.g. diffusion equation). I am also interested in other relaxation methods than Gauss-Seidel, still usable with multigrid (e.g. Conjugate Gradient). –  Libor Sep 20 '12 at 10:45
add comment

1 Answer

up vote 0 down vote accepted

First please don't be bluffed by those fancy terms coined by computational scientists, and don't worry about preconditioning or conjugate gradient. The multigrid method for numerical PDE can be viewed as a standalone subject, basically what it does is: make use of the "information" on both finer and coarser mesh, in order to solve a linear equation system(obtained from the discretization of the PDE on these meshes), and it does this in an iterative fashion.

IMHO Vassilevski from Lawrence Livermore national laboratory puts up a series of very beginner-oriented lecture notes, where he introduced the motivation and preliminary first, how to get the $Ax = b$ type linear equation system from a boundary value problem of $-\Delta u = f$ with $u = g$ on $\partial \Omega$, what is condition number and how does it affect our iterative solvers.

Then he introduced all the well-established aspects of multigrid: what is the basic idea in two-grid, how do we do smoothing on the finer mesh, and error correction on the coarser mesh, V-cycle, W-cycle, etc. Algebraic multigrid(the multigrid that uses information from mesh is often called geometric method), also the adaptive methods are covered too.

Some example codes for Poisson equation can be easy google'd. If you got more time, this book has a user-friendly and comprehensive introduction on this topic together with some recent advancements.

share|improve this answer
    
Thanks. The reason I am craving for state-of-the-art method for numerically solving PDEs is that I am working with images tens of megapixels large, and every slight improvement of the solver have large impact on the computation time. For example, when I switched from "rapid Poisson solver" based on FFT to simple multigrid (FMG), the difference in computation time was from two minutes to six seconds (!). Of course, I am curious if this can be improved even more :) –  Libor Sep 20 '12 at 22:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.