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 <math>i<math> with a given grid point density <math>N_i<math>. Assume furthermore that a solution on any grid <math>N_i<math> may be obtained with a given effort <math>W_i = \rho K N_i<math> from a solution on a coarser grid <math>i+1<math> with grid point density <math>N_{i+1} = \rho N_i<math> (that is, <math>K<math> is not dependent on <math>i<math>).
Then, using the geometric series, we then find for the effort involved in finding the solution on the finest grid <math>N_1<math>
- <math>W_1 = W_2 + \rho K N_1<math>
- <math>W_1 = W_3 + \rho^2 K N_1 + \rho K N_1<math>
- <math>W_1 / (K N_1) + 1 = 1 + \sum_p \rho^p <math>
- <math>W_1 / (K N_1) + 1 = 1 / (1 - \rho)<math>
- <math>W_1 = (K N_1) (1 / (1 - \rho) - 1),<math>
that is, a solution may be obtained in <math>O(N)<math> 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 (http://links.jstor.org/sici?sici=0025-5718%28197704%2931%3A138%3C333%3AMASTBP%3E2.0.CO%3B2-M)).
- MGNet: a repository for multigrid and other methods (http://www.mgnet.org/)
- 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. (http://www.scicomp.ucsd.edu/~mholst/pubs/dist/HoSa93b.pdf)
- A multigrid tutorial (http://www.llnl.gov/casc/people/henson/mgtut/welcome.html), ISBN 0-89871-462-1
- Introduction to Algebraic Multigrid (http://www.iwr.uni-heidelberg.de/groups/techsim/chris/amg.pdf)