Multi-grid method

In numerical mathematics, multi-grid methods form a class of efficient algorithms for the approximate solution of systems of equations that originate from the discretization of partial differential equations . Elliptical problems such as Poisson's equation can thus be solved from the order with a computational effort in the case of unknowns . The order of convergence is not dependent on the fineness of the grids, in contrast to most other numerical methods, which become slower as the discretization fineness becomes smaller. Multi-grid methods are “optimal” in this regard. The essential alternative to multigrid methods are preconditioned Krylow subspace methods . ${\displaystyle n}$ ${\displaystyle O(n)}$

description

The basic idea is to approximate the unknown error to a given approximation on a fine grid, on a coarser grid. Since there are fewer unknowns on the coarser grid, this can be done cheaply. Recursive application to a hierarchy of increasingly coarse grids provides a multi-grid structure.

The use of the coarse grids accelerates the propagation of information over the discretization area. The combination of coarse grid correction and smoother results in a fast, mesh-size-independent convergence rate .

Systems of linear equations

First of all, a system of linear equations with a regular square matrix is given on each grid . A smoother is then applied first to the approximation on a fine grid , which attenuates high-frequency error components, resulting in a smooth error. What a useful smoother is depends on which partial differential equation is to be solved. For many, Gauss-Seidel - or Jacobi - relaxation are suitable. The corresponding residue is restricted to the next coarser grid: . The restriction is a mapping from the fine to the next coarser grid. Since low-frequency error fractions on fine grids correspond to high-frequency error fractions on coarser grids, the residual equation for the error results in a problem with a similar structure to the original problem, but with a smaller dimension. ${\displaystyle A_{l}x=b_{l}}$ ${\displaystyle A_{l}\in \mathbb {R} ^{n\times n}}$ ${\displaystyle x_{l}^{k}}$ ${\displaystyle S_{l}}$ ${\displaystyle r_{l}=b_{l}-A_{l}S_{l}x_{l}^{k}}$ ${\displaystyle r_{l-1}=Rr_{l}}$ ${\displaystyle R}$ ${\displaystyle A_{l-1}e=r_{l-1}}$ ${\displaystyle e}$

V cycle

W cycle

This is repeated recursively up to the coarsest grid ( V cycle ), where the system of equations can be solved directly. The calculated error is then successively by prolongation P rückprolongiert to the finer mesh and smoothed. Finally, the original approximation of the solution is corrected with the error approximation on the finest grid. An iteration of the multi-grid method then looks like this:

${\displaystyle MG(x_{l},b_{l},l)}$

if , (solve exactly on the coarsest grid) ${\displaystyle (l=0)}$ ${\displaystyle x_{l}=A_{l}^{-1}b_{l}}$

else

${\displaystyle x_{l}=S_{l}^{\nu _{1}}(x_{l},b_{l})}$ (Pre-smoothing)

${\displaystyle r_{l-1}=R_{l-1,l}(b_{l}-A_{l}x_{l})}$ (Restriction)

${\displaystyle v_{l-1}=0}$

For (calculation of the coarse grid correction) ${\displaystyle (j=0;\;j<\gamma ;\;j++)}$ ${\displaystyle MG(v_{l-1},r_{l-1},l-1)}$

${\displaystyle x_{l}=x_{l}+P_{l,l-1}v_{l-1}}$ (Prolongation of the coarse grid correction)

${\displaystyle x_{l}=S_{l}^{\nu _{2}}(x_{l},b_{l})}$ (Post-smoothing)

end if

End

This works for a linear problem with a solution , since the error of the approximate solution can then be calculated using the residual equation. ${\displaystyle Ax=b}$ ${\displaystyle x^{*}}$ ${\displaystyle e=x^{k}-x^{*}}$ ${\displaystyle x^{k}}$ ${\displaystyle Ae=r=Ax^{k}-b}$

Multi-grid methods can reduce the norm of the error for the Poisson problem in a V cycle by more than a factor of 10, and are therefore extremely effective here.

Full Approximation Scheme

The above procedure cannot be transferred directly to a non-linear problem , since the residual equation does not have to be solvable. Therefore one solves instead on the rough grid what would be equivalent in the linear case. It then arises ${\displaystyle L(u)=f}$ ${\displaystyle L(e)=r}$ ${\displaystyle L(u+e)=L(u)+r}$

${\displaystyle MG({\tilde {u}}_{l},u_{l},f_{l},l)}$

if , ${\displaystyle (l=0)}$ ${\displaystyle u_{l}=L_{l}^{-1}f_{l}}$

else

${\displaystyle u_{l}=S_{l}^{\nu _{1}}(u_{l},f_{l})}$

${\displaystyle r_{l}=f_{l}-L_{l}u_{l}}$

Choose and ${\displaystyle {\tilde {u}}_{l-1}}$ ${\displaystyle s_{l-1}}$

${\displaystyle f_{l-1}=L_{l-1}({\tilde {u}}_{l-1})+s_{l-1}R_{l-1,l}r_{l}}$

For ${\displaystyle (j=0;\;j<\gamma ;\;j++)}$ ${\displaystyle MG({\tilde {u}}_{l-1},u_{l-1},f_{l-1},l-1)}$

${\displaystyle u_{l}=u_{l}+(1/s_{l-1})P_{l-1,l}(u_{l-1}-{\tilde {u}}_{l-1})}$

${\displaystyle u_{l}=S_{l}^{\nu _{2}}(u_{l},f_{l})}$

end if

End

${\displaystyle {\tilde {u}}_{l}}$describes an approximation to the solution and is chosen so small that the corresponding nonlinear system of equations can be solved. corresponds to the Full Approximation Scheme (FAS) by Achi Brandt (1977). A variant of this process is used in numerical fluid mechanics . ${\displaystyle s_{l}}$ ${\displaystyle s=1}$

history

The earliest work on multigrid methods comes from the Soviet mathematicians Radi Petrowitsch Fedorenko and Nikolai Sergejewitsch Bachwalow (Bakhvalov) from the early 1960s. They became known mainly through the work of Wolfgang Hackbusch in the late 1970s, who also achieved important convergence results. Another multi-grid pioneer is Achi Brandt: he claims that every partial differential equation can be solved efficiently and quickly using multi-grid methods. Brandt introduced the FAS method, which Antony Jameson and others took up for the field of computational fluid mechanics.

Related procedures

With complex geometries, multi-grid processes quickly reach their limits. As an alternative, algebraic multigrid methods have been developed that are based purely on modifications of the equation systems and do not use any special geometric properties such as changes in the grid width. In general, multilevel processes are inspired by multigrid.

For problems with large scale differences (e.g. turbulent flows : eddies in the range of micrometers, normal geometries in the range of meters ), there have recently been (around since 1995) approaches to solve the physical processes on the different scales using different numerical approaches. This is also known as the multi-scale approach and is closely related to the multi-grid method.

In signal processing there is the Gauss-Laplace pyramid for a multigrid technique .

literature

• William L. Briggs, Van Emden Henson, and Steve F. McCormick, A Multigrid Tutorial, Second Edition , SIAM, 2000 ( book home page ), ISBN 0-89871-462-1
• Wolfgang Hackbusch: Multigrid Methods and Applications , Springer, 1985
• Pieter Wesseling : An Introduction to Multigrid Methods , Corrected Reprint. Philadelphia: RT Edwards, Inc., 2004. ISBN 1-930217-08-0
• Schwetlick, H. and Kretschmar, H .: Numerical methods for natural scientists and engineers . Fachbuchverlag Leipzig, 1991, p. 354 .

Web links

• Frank Liebau: Multi-grid method
• T. Rung, L. Xue, J. Yan, M. Schatz, F. Thiele: Numerical methods of thermo- and fluid dynamics (section multigrid methods)

Individual evidence

1. ↑ Fedorenko On the history of the Multigrid method