Multigrid method: Difference between revisions

Revision as of 07:07, 19 January 2021

Revision as of 19:01, 17 March 2021

Line 181:

==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. http://emis.ams.org/journals/ETNA/vol.15.2003/pp38-55.dir/pp38-55.pdf</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. https://doi.org/{{DOI | 10.1016/j.procs.2015.05.241}}</ref> to be robust if the preconditioner is not SPD.

==Bramble–Pasciak–Xu preconditioner==