Science Fair Project Encyclopedia
Multigrid
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
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details