Multigrid method: Difference between revisions

Revision as of 09:08, 25 September 2019

Revision as of 05:15, 16 October 2019

Line 14:

* '''Correction''' – Adding prolongated coarser grid solution onto the finer grid.

There are many choices of multigrid methods with varying trade-offs between speed of solving a single iteration and the rate of convergence with said iteration. The 3 main types are V-Cycle, F-Cycle, and W-Cycle. For a [[Discrete Poisson equation#On a two-dimensional rectangular grid|discrete 2D problem]], F-Cycle takes 83% more time to compute than a V-Cycle iteration while a W-Cycle iteration takes 125% more. If the problem is setup in a 3D ___domain, then a F-Cycle iteration and a W-Cycle iteration take about 64% and 75% more time respectively than a V-Cycle iteration ignoring [[Overhead (computing)|overheads]]. Typically, W-Cycle produces similar convergence to F-Cycle. However, in cases of [[Convection–diffusion equation|convection-diffusion]] problems with high [[Péclet number|Péclet numbers]], W-Cycle can show superiority in its rate of convergence per iteration over F-Cycle. The choice of smoothing operators are extremely diverse as they include [[krylov subspace]] methods and can be [[Preconditioner|preconditioned]].

Any geometric multigrid cycle iteration is performed on a hierarchy of grids and hence it can be coded using recursion. Since the function calls itself with smaller sized (coarser) parameters, the coarsest grid is where the recursion stops. In cases where the system has a high [[condition number]], the correction procedure is modified such that only a fraction of the prolongated coarser grid solution is added onto the finer grid.

{| class="wikitable"

Line 223:

The well known [[Parareal]] parallel-in-time integration method can also be reformulated as a two-level multigrid in time.

== Multigrid for nearly singular problems ==

Nearly singular problems arise in a number of important physical and engineering applications. Simple, but important example of nearly singular problems can be found at the displacement formulation of [[Linear_elasticity|linear elasticity]] for nearly incompressible materials. Typically, the major problem to solve such nearly singular systems boils down to treat the nearly singular operator given by <math>A + \epsilon M</math> robustly with respect to the positive, but small parameter <math>\epsilon</math>. Here <math>A</math> is symmetric [[Positive semidefinite matrix|semidefinite]] operator with large [[Kernel_(linear_algebra)|null space]], while <math>M</math> is a symmetric [[Definiteness of a matrix|positive definite]] operator. There were many works to attempt to design a robust and fast multigrid method for such nearly singular problems. A general guide has been provided as a design principle to achieve parameters (e.g., mesh size and physical parameters such as [[Poisson's ratio]] that appear in the nearly singular operator) independent convergence rate of the multigrid method applied to such nearly singular systems<ref>Young-Ju Lee, Jinbiao Wu, Jinchao Xu and Ludmil Zikatanov, Robust Subspace Correction Methods for Nearly Singular Systems, Mathematical Models and Methods in Applied Sciences, Vol. 17, No 11, pp. 1937-1963 (2007)</ref>, i.e., in each grid, a space decomposition based on which the smoothing is applied, has to be constructed so that the null space of the singular part of the nearly singular operator has to be included in the sum of the local null spaces, the intersection of the null space and the local spaces resulting from the space decompositions.

==Notes==