Multigrid method: Difference between revisions

Revision as of 14:31, 16 May 2024

Latest revision as of 13:57, 22 July 2025

(6 intermediate revisions by 3 users not shown)

Line 174:

This approach has the advantage over other methods that it often scales linearly with the number of discrete nodes used. In other words, it can solve these problems to a given accuracy in a number of operations that is proportional to the number of unknowns.

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>. Here, <math>\rho = N_{i+1} / N_i < 1</math> is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and <math>K</math> is some constant modeling the effort of computing the result for one 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>. Here, <math>\rho = N_{i+1} / N_i < 1</math> is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and <math>K</math> is some constant modeling the effort of computing the result for one grid point.

The following recurrence relation is then obtained for the effort of obtaining the solution on grid <math>k</math>:

<math display="block">W_k = W_{k+1} + \rho K N_k</math>

:<math>W_k = W_{k+1} + \rho K N_k</math>[[File:Convergence Rate of Multigrid Cycles.svg|alt=Convergence Rate of Multigrid Cycles in comparison to other smoothing operators. Multigrid converges faster than typical smoothing operators. F-Cycle and W-Cycle perform with near equal robustness.|thumb|438x438px|Example of Convergence Rates of Multigrid Cycles in comparison to other smoothing operators.]]

And in particular, we find for the finest grid <math>N_1</math> that

:<math display="block">W_1 = W_2 + \rho K N_1</math>

Combining these two expressions (and using <math>N_{k}N_k = \rho^{k-1} N_1</math>) gives

:<math display="block">W_1 = K N_1 \sum_{p=0}^n \rho^p </math>

Using the [[geometric series]], we then find (for finite <math>n</math>)

:<math display="block">W_1 < K N_1 \frac{1}{1 - \rho}</math>

that is, a solution may be obtained in <math>O(N)</math> time. It should be mentioned that there is one exception to the <math>O(N)</math> i.e. W-cycle multigrid used on a 1D problem; it would result in <math>O(Nlog(N) \log N)</math> complexity. {{Citation needed|date=September 2021}}

==Multigrid preconditioning==

Line 197 ⟶ 196:

==Bramble–Pasciak–Xu preconditioner==

Originally described in Xu’s Ph.D. thesis<ref>Xu, Jinchao. Theory of multilevel methods. Vol. 8924558. Ithaca, NY: Cornell University, 1989.</ref> and later published in Bramble-Pasciak-Xu,<ref>Bramble, James H., Joseph E. Pasciak, and Jinchao Xu. "Parallel multilevel preconditioners." Mathematics of Computation 55, no. 191 (1990): 1–22.</ref> the BPX-preconditioner is one of the two major multigrid approaches (the other is the classic multigrid algorithm such as V-cycle) for solving large-scale algebraic systems that arise from the discretization of models in science and engineering described by partial differential equations. In view of the subspace correction framework,<ref>Xu, Jinchao. "Iterative methods by space decomposition and subspace correction." SIAM review 34, no. 4 (1992): 581-613.</ref> BPX preconditioner is a parallel subspace correction method whereas the classic V-cycle is a successive subspace correction method. The BPX-preconditioner is known to be naturally more parallel and in some applications more robust than the classic V-cycle multigrid method. The method has been widely used by researchers and practitioners since 1990.

Originally described in Xu's Ph.D. thesis<ref>Xu, Jinchao. Theory of multilevel methods. Vol. 8924558. Ithaca, NY: Cornell University, 1989.</ref>

and later published in Bramble-Pasciak-Xu,<ref>Bramble, James H., Joseph E. Pasciak, and Jinchao Xu. "Parallel multilevel preconditioners." Mathematics of Computation 55, no. 191 (1990): 1–22.</ref> the BPX-preconditioner is one of the two major multigrid

approaches (the other is the classic multigrid algorithm such as V-cycle) for solving large-scale algebraic systems that arise from the discretization of models in science and engineering described by partial differential equations. In view of the subspace correction framework,<ref>Xu, Jinchao. "Iterative methods by space decomposition and subspace correction." SIAM review 34, no. 4 (1992): 581-613.

</ref> BPX preconditioner is a parallel subspace correction method where as the classic V-cycle is a successive subspace correction method. The BPX-preconditioner is known to be naturally more parallel and in some applications more robust than the classic V-cycle multigrid method. The method has been widely used by researchers and practitioners since 1990.

==Generalized multigrid methods==

Line 206 ⟶ 202:

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.

Line 248 ⟶ 244:

== References ==

{{refbegin}}

* G. P. Astrachancev (1971), [https://www.sciencedirect.com/science/article/pii/0041555371901704 An iterative method of solving elliptic net problems]. USSR Comp. Math. Math. Phys. 11, 171–182.

* N{{cite journal | first = G. SP. [[Bakhvalov]]| last = Astrachancev | year = 1971 | url (1966),= [https://www.sciencedirect.com/science/article/pii/00415553669011820041555371901704 On| thetitle convergence= ofAn a relaxationiterative method withof naturalsolving constraintselliptic onnet theproblems elliptic| operator].journal = USSR Comp. Math. Math. Phys. 6,| 101–13.volume = 11 | issue = 2 | pages = 171–182 }}

* {{cite journal | first = N. S. | last = Bakhvalov | author-link = Nikolai Bakhvalov | year = 1966 | url = https://www.sciencedirect.com/science/article/pii/0041555366901182 | title = On the convergence of a relaxation method with natural constraints on the elliptic operator | journal = USSR Comp. Math. Math. Phys. | volume = 6 | issue = 5 | pages = 101–113 }}

* [[{{cite journal | first = Achi | last = Brandt]] (| author-link = Achi Brandt | date = April 1977), "[| url = https://www.jstor.org/stable/2006422 | title = Multi-Level Adaptive Solutions to Boundary-Value Problems]", ''| journal = Mathematics of Computation'', '''| volume = 31''': 333–90.| issue = 138 | pages = 333–390 }}

* {{cite book | first1 = William L. | last1 = Briggs, | first2 = Van Emden | last2 = Henson, and| first3 = Steve F. | last3 = McCormick (| year =2000), ''[| url = https://web.archive.org/web/20061006153457/http://www.llnl.gov/casc/people/henson/mgtut/welcome.html | title = A Multigrid Tutorial]'' (| edition = 2nd ed.),| ___location = Philadelphia: | publisher = [[Society for Industrial and Applied Mathematics]], {{ISBN| isbn = 0-89871-462-1}}.

* {{cite journal | first = R. P. | last = Fedorenko (| year = 1961), [| url = http://www.mathnet.ru/eng/zvmmf8014 | title = A relaxation method for solving elliptic difference equations]. | journal = USSR Comput. Math. Math. Phys. | volume = 1, p.&nbsp;| issue = 4 | page = 1092. }}

* R. P. Fedorenko (1964), The speed of convergence of one iterative process. USSR Comput. Math. Math. Phys. 4, p.&nbsp;227.

* {{cite journal | first = R. P. | last = Fedorenko | year = 1964 | title = The speed of convergence of one iterative process | journal = USSR Comput. Math. Math. Phys. | volume = 4 | page = 227 }}
* {{cite book | last1 = Press | first1 = W. H. | last2 = Teukolsky | first2 = S. A. | last3 = Vetterling | first3 = W. T. | last4 = Flannery | first4 = B. P. | year = 2007 | title = Numerical Recipes: The Art of Scientific Computing | edition = 3rd | publisher = Cambridge University Press | ___location = New York | isbn = 978-0-521-88068-8 | chapter = Section 20.6. Multigrid Methods for Boundary Value Problems | chapter-url = http://apps.nrbook.com/empanel/index.html#pg=1066 }}

{{refend}}

== External links ==

*[http://www.mgnet.org/ Repository for multigrid, multilevel, multiscale, aggregation, defect correction, and ___domain decomposition methods]

*[http://www.mgnet.org/mgnet/tutorials/xwb/xwb.html Multigrid tutorial]

*[https://computation.llnl.gov/project/linear_solvers/talks/AMG_TUT_PPT/sld001.htm Algebraic multigrid tutorial]

*[https://web.archive.org/web/20100527194456/https://computation.llnl.gov/casc/linear_solvers/present.html Links to AMG presentations]