Content deleted Content added
LucasBrown (talk | contribs) Adding local short description: "Method of solving differential equations", overriding Wikidata description "method of solving system of linear algebrayes equations based on the use of a sequence of decreasing grids and operator" |
Citation bot (talk | contribs) Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical analysis | #UCB_Category 209/235 |
||
Line 206:
Multigrid methods can be generalized in many different ways. They can be applied naturally in a time-stepping solution of [[parabolic partial differential equation]]s, or they can be applied directly to time-dependent [[partial differential equation]]s.<ref>{{cite book |chapter-url=https://books.google.com/books?id=GKDQUXzLTkIC&pg=PA165 |editor1=Are Magnus Bruaset |editor2=Aslak Tveito |title=Numerical solution of partial differential equations on parallel computers |page=165 |chapter=Parallel geometric multigrid |author1=F. Hülsemann |author2=M. Kowarschik |author3=M. Mohr |author4=U. Rüde |publisher=Birkhäuser |year=2006 |isbn=978-3-540-29076-6}}</ref> Research on multilevel techniques for [[hyperbolic partial differential equation]]s is underway.<ref>For example, {{cite book |title=Computational fluid dynamics: principles and applications |page=305 |url=https://books.google.com/books?id=asWGy362QFIC&q=%22The+goal+of+the+current+research+is+the+significant+improvement+of+the+efficiency+of+multigrid+for+hyperbolic+flow+problems%22&pg=PA305 |author= J. Blaz̆ek |year=2001 |isbn=978-0-08-043009-6 |publisher=Elsevier}} and {{cite book |chapter-url=https://books.google.com/books?id=TapltAX3ry8C&pg=PA369 |author=Achi Brandt and Rima Gandlin |chapter=Multigrid for Atmospheric Data Assimilation: Analysis |page=369 |editor1=Thomas Y. Hou |editor2=Eitan Tadmor |editor2-link=Eitan Tadmor |title=Hyperbolic problems: theory, numerics, applications: proceedings of the Ninth International Conference on Hyperbolic Problems of 2002 |year=2003 |isbn=978-3-540-44333-9 |publisher=Springer}}</ref> Multigrid methods can also be applied to [[integral equation]]s, or for problems in [[statistical physics]].<ref>{{cite book |title=Multiscale and multiresolution methods: theory and applications |author=Achi Brandt |chapter-url=https://books.google.com/books?id=mtsy6Ci2TRoC&pg=PA53 |editor1=Timothy J. Barth |editor2=Tony Chan |editor3=Robert Haimes |page=53 |chapter=Multiscale scientific computation: review |isbn=978-3-540-42420-8 |year=2002 |publisher=Springer}}</ref>
Another set of multiresolution methods is based upon [[wavelets]]. These wavelet methods can be combined with multigrid methods.<ref>{{cite book |chapter-url=https://books.google.com/books?id=mtsy6Ci2TRoC&pg=PA140 |author1=Björn Engquist |author2=Olof Runborg |editor1=Timothy J. Barth |editor2=Tony Chan |editor3=Robert Haimes |chapter=Wavelet-based numerical homogenization with applications |title=Multiscale and Multiresolution Methods |isbn=978-3-540-42420-8 |volume=20 of Lecture Notes in Computational Science and Engineering |publisher=Springer |year=2002 |page=140 ''ff''}}</ref><ref>{{cite book |url=https://books.google.com/books?id=-og1wD-Nx_wC&q=wavelet+ |author1=U. Trottenberg |author2=C. W. Oosterlee |author3=A. Schüller |title=Multigrid |isbn=978-0-12-701070-0|year=2001 |publisher=Academic Press }}</ref> For example, one use of wavelets is to reformulate the finite element approach in terms of a multilevel method.<ref>{{cite book |title=Numerical Analysis of Wavelet Methods |author=Albert Cohen |url=https://books.google.com/books?id=Dz9RnDItrAYC&pg=PA44 |page=44 |publisher=Elsevier |year=2003 |isbn=978-0-444-51124-9}}</ref>
'''Adaptive multigrid''' exhibits [[adaptive mesh refinement]], that is, it adjusts the grid as the computation proceeds, in a manner dependent upon the computation itself.<ref>{{cite book |author1=U. Trottenberg |author2=C. W. Oosterlee |author3=A. Schüller |title=Multigrid |chapter=Chapter 9: Adaptive Multigrid |chapter-url=https://books.google.com/books?id=-og1wD-Nx_wC&pg=PA356 |page=356 |isbn=978-0-12-701070-0|year=2001 |publisher=Academic Press }}</ref> The idea is to increase resolution of the grid only in regions of the solution where it is needed.
==Algebraic multigrid (AMG)==
Practically important extensions of multigrid methods include techniques where no partial differential equation nor geometrical problem background is used to construct the multilevel hierarchy.<ref>{{cite book |title=Matrix-based multigrid: theory and applications |author=Yair Shapira |chapter-url=https://books.google.com/books?id=lCDGhpDDk5IC&pg=PA66 |chapter=Algebraic multigrid |page=66 |isbn=978-1-4020-7485-1 |publisher=Springer |year=2003}}</ref> Such '''algebraic multigrid methods''' (AMG) construct their hierarchy of operators directly from the system matrix. In classical AMG, the levels of the hierarchy are simply subsets of unknowns without any geometric interpretation. (More generally, coarse grid unknowns can be particular linear combinations of fine grid unknowns.) Thus, AMG methods become black-box solvers for certain classes of [[sparse matrices]]. AMG is regarded as advantageous mainly where geometric multigrid is too difficult to apply,<ref>{{cite book |author1=U. Trottenberg |author2=C. W. Oosterlee |author3=A. Schüller |title=Multigrid |url=https://books.google.com/books?id=-og1wD-Nx_wC&pg=PA417 |page=417 |isbn=978-0-12-701070-0|year=2001 |publisher=Academic Press }}</ref> but is often used simply because it avoids the coding necessary for a true multigrid implementation. While classical AMG was developed first, a related algebraic method is known as smoothed aggregation (SA).
In an overview paper<ref>Xu, J. and Zikatanov, L., 2017. Algebraic multigrid methods. Acta Numerica, 26, pp.591-721. [https://arxiv.org/pdf/1611.01917.pdf]</ref> by Jinchao Xu and Ludmil Zikatanov, the "algebraic multigrid" methods are understood from an abstract point of view. They developed a unified framework and existing algebraic multigrid methods can be derived coherently. Abstract theory about how to construct optimal coarse space as well as quasi-optimal spaces was derived. Also, they proved that, under appropriate assumptions, the abstract two-level AMG method converges uniformly with respect to the size of the linear system, the coefficient variation, and the anisotropy. Their abstract framework covers most existing AMG methods, such as classical AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG, and spectral AMGe.
| |||