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.

See also

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

The key idea is the following: Assuming you have a differential equation which can be solved approximately (with a given accuracy) on a grid with a given grid point density $N$. Assuming furthermore that this solution may be obtained from the solution on a sparser grid with a given grid point density $N_{1}$ (typically $N/2$) with an effort that is proportional to $N$, i.e. $kN$. Assuming furthermore that this holds true for any given grid $i$ with density $N_{i}$ and corresponding sparser grid $N_{i+1}$ (i.e. $k$ is approximately constant overall grids). Then the total effort spent obtaining a solution on the finest grid is (see Geometric_series)

$E=kN+kN_{1}+kN_{2}+...$

$=kN+k^{2}N+k^{3}N+...$

$=Nk(1+k+k^{2}+...)$

$={\frac {Nk}{1-k}}$

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

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