Content deleted Content added
Brews ohare (talk | contribs) →Algorithm: chapter title |
Brews ohare (talk | contribs) sources; links to other articles |
||
Line 1:
'''Multigrid (MG) methods''' in [[numerical analysis]] are a group of [[algorithm]]s for solving [[differential equations]] using a [[hierarchy]] of [[discretization]]s. They are an example of a class of techniques called [[Multiresolution analysis|multiresolution methods]], very useful (but not limited to) problems exhibiting [[Multiscale modeling|multiple scales]] of behavior. The main idea of multigrid is to accelerate the convergence of a base iterative method by correcting, from time to time, the solution globally by solving a [[coarse problem]]. This idea is similar to [[extrapolation]] between coarser and finer grids. The typical application for multigrid is in the numerical solution of [[elliptic operator|elliptic]] [[partial differential equation]]s in two or more dimensions.<ref name=Oswald>{{cite book |title=Multigrid |author=U Trottenberg, CW Oosterlee, A Schüller |publisher=Academic Press |year=2001 |isbn=012701070X |url=http://books.google.com/books?id=-og1wD-Nx_wC&printsec=frontcover&dq=isbn:012701070X#v=onepage&q=elliptic&f=false}}</ref>
Multigrid methods can be applied in combination with any of the common discretization techniques. In these cases, multigrid methods are among the fastest solution techniques known today. In contrast to other methods, multigrid methods are general in that they can treat arbitrary regions and [[boundary condition]]s. They do not depend on the separability of the equations or other special properties of the equation. They are also directly applicable to more-complicated non-symmetric and nonlinear systems of equations, like the [[Lamé system]] of [[Elasticity (physics)|elasticity]] or the [[Navier-Stokes equations]].
Line 7:
Other extensions of multigrid methods include techniques where no partial differential equation nor geometrical problem background is used to construct the multilevel hierarchy. Such '''algebraic multigrid methods''' (AMG) construct their hierarchy of operators directly from the system matrix and thus become true black-box solvers for [[sparse matrices]].
Another set of multiresolution methods is based upon [[wavelets]]. These wavelet methods can be combined with multigrid methods.<ref name=Engquist>{{cite book |url=http://books.google.com/books?id=mtsy6Ci2TRoC&pg=PA140 |author=Björn Engquist and Olof Runborg |editors=TJ Barth, TF Chan, R Hairns |chapter=Wavelet-based numerical homogenization with applications |title=Multiscale and Multiresolution Methods |isbn=3540424202 |volume=Vol. 20 of Lecture notes in computational science and engineering |publisher=Springer |year=2002 | |page=140 ''ff''}}</ref><ref name=Oswald2>{{cite book |url=http://books.google.com/books?id=-og1wD-Nx_wC&dq=wavelet+multigrid&printsec=frontcover&source=in&hl=en&ei=bx8ZS_v1KIaQsgO-5pn3Bw&sa=X&oi=book_result&ct=result&resnum=12&ved=0CD0Q6AEwCw#v=snippet&q=wavelet%20&f=false |author=U Trottenberg, CW Oosterlee, A Schüller |title=''op. cit.'' |isbn=012701070X }}</ref> The [[finite element method]] may be recast as a multigrid method by choosing linear [[wavelets]] as the basis.
== Algorithm ==
| |||