Multigrid method: Difference between revisions

Revision as of 09:27, 23 September 2021

Revision as of 21:48, 27 January 2022

Line 180:

==Multigrid preconditioning==

A multigrid method with an intentionally reduced tolerance can be used as an efficient [[preconditioning|preconditioner]] for an external iterative solver, e.g.,<ref>Andrew V Knyazev, Klaus Neymeyr. [http://etna.mcs.kent.edu/volumes/2001-2010/vol15/abstract.php?vol=15&pages=38-55 Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method]. Electronic Transactions on Numerical Analysis, 15, 38–55, 2003. </ref> The solution may still be obtained in <math>O(N)</math> time as well as in the case where the multigrid method is used as a solver. Multigrid preconditioning is used in practice even for linear systems, typically with one cycle per iteration, e.g., in [[Hypre]]. Its main advantage versus a purely multigrid solver is particularly clear for nonlinear problems, e.g., [[eigenvalue]] problems.

If the matrix of the original equation or an eigenvalue problem is symmetric positive definite (SPD), the preconditioner is commonly constructed to be SPD as well, so that the standard [[conjugate gradient]] (CG) [[iterative methods]] can still be used. Such imposed SPD constraints may complicate the construction of the preconditioner, e.g., requiring coordinated pre- and post-smoothing. However, [[preconditioning|preconditioned]] [[steepest descent]] and [[Conjugate gradient method#The flexible preconditioned conjugate gradient method|flexible CG methods]] for SPD linear systems and [[LOBPCG]] for symmetric eigenvalue problems are all shown<ref>Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. [https://doi.org/10.1016/j.procs.2015.05.241 Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods]. Procedia Computer Science, Volume 51, Pages 276–285, Elsevier, 2015. {{DOI | 10.1016/j.procs.2015.05.241}}</ref> to be robust if the preconditioner is not SPD.

Line 194:

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=Vol. 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 }}</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 }}</ref> The idea is to increase resolution of the grid only in regions of the solution where it is needed.