In mathematics, more specifically in numerical analysis, multigrid methods are a group of algorithms for solving differential equations using a hierarchy of discretizations. This approach has the advantage over other methods that it scales linearly with the number of discrete nodes used.
In order for the multigrid methods to be applicable, one needs to make several assumptions. Assume that one has a differential equation which can be solved approximately (with a given accuracy) on a grid i with a given grid point
density Ni. Assume furthermore that a solution on any grid Ni may be obtained with a given
effort Wi = ρKNi from a solution on a coarser grid i + 1 with grid point
density Ni + 1 = ρNi (that is, K is not dependent on i).
Then, using the geometric series, we then find for the effort involved in finding the solution on
the finest grid N1
- W1 = W2 + ρKN1
- W1 = W3 + ρ2KN1 + ρKN1
| W1 / (KN1) + 1 = 1 + | ∑ | ρp |
| p | |
- W1 / (KN1) + 1 = 1 / (1 - ρ)
- W1 = (KN1)(1 / (1 - ρ) - 1),
that is, a solution may be obtained in O(N) time.
See also
References and external links
- Brandt, A. 'Multi-Level Adaptive Solutions to Boundary-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