Multigrid

The multigrid methods is a group of algorithms for solving differential equations using a hierarchy of discretization. It has the advantage over other methods that it scales linearly with the number of discrete nodes used.

The key idea is the following: Assuming you have a differential equation which can be solved approximately (with a given accuracy) on a grid $i$ with a given grid point density $N_{i}$. Assuming furthermore that a solution on any grid $N_{i}$ may be obtained with a given effort $W_{i}=\rho KN_{i}$ from a solution on a coarser grid $i+1$ with grid point density $N_{i+1}=\rho N_{i}$ (i.e. $K$ is not dependent on $i$).

Using the Geometric_series, we then find for the effort involved in finding the solution on the finest grid $N_{1}$

$W_{1}=W_{2}+\rho KN_{1}$

$W_{1}=W_{3}+\rho ^{2}KN_{1}+\rho KN_{1}$

$W_{1}/(KN_{1})+1=1+\sum _{p}\rho ^{p}$

$W_{1}/(KN_{1})+1=1/(1-\rho )$

$W_{1}=(KN_{1})(1/(1-\rho )-1)$

i.e. a solution may be obtained in $O(N)$ time.

See also

• Numerical analysis
• Partial differential equation
• Finite element method
• Finite difference

References and External links

• Brandt, A. 'Multi-Level Adaptive Solutions to Boudary-Value Problems', Math. Comp, 1977(31), 333-390 (jstor link).
• MGNet: a repository for multigrid and other methods
• M. Holst and F. Saied, Multigrid and domain decomposition methods for electrostatics problems. Domain Decomposition Methods in Science and Engineering (Proceedings of the Seventh International Conference on Domain Decomposition Methods, October 27-30, 1993, The Pennsylvania State University) D. E. Keyes and J. Xu, eds., American Mathematical Society, Providence, 1995.
• A multigrid tutorial, ISBN 0-89871-462-1
• Introduction to Algebraic Multigrid