Multigrid method: Difference between revisions

Revision as of 00:43, 11 January 2025

Latest revision as of 13:57, 22 July 2025

(3 intermediate revisions by one other user 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 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 ==