Content deleted Content added
Add infobox |
Providing reference |
||
Line 212:
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 }}</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.
== Multigrid in time methods ==
| |||