Multigrid method - Citizendia

Multigrid (MG) methods in numerical analysis are a group of algorithms for solving differential equations using a hierarchy of discretizations. Numerical analysis is the study of Algorithms for the problems of continuous mathematics (as distinguished from Discrete mathematics) In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation A differential equation is a mathematical Equation for an unknown function of one or several variables that relates the values of the @@@ main@@@ - title Hierarchy@@@ keywords structure; sociology; information@@@ review@@@ - In Mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts The idea is similar to extrapolation between coarser and finer grids. In Mathematics, extrapolation is the process of constructing new data points outside a Discrete set of known data points The typical application for multigrid is in the numerical solution of elliptic partial differential equations in two or more dimensions. In Mathematics, an elliptic operator is one of the major types of Differential operator. In Mathematics, partial differential equations ( PDE) are a type of Differential equation, i

MG can be applied in combination with any of the common discretization techniques. In these cases, multigrid is among the fastest solution techniques known today. In contrast to other methods, multigrid is general in that it can treat arbitrary regions and boundary conditions. In Mathematics, in the field of Differential equations a boundary value problem is a Differential equation together with a set of additional restraints It does not depend on the separability of the equations or other special properties of the equation. MG is also directly applicable to more-complicated non-symmetric and nonlinear systems of equations, like the Lamé system of elasticity or the Navier-Stokes equations. A material is said to be elastic if it deforms under stress (e The Navier–Stokes equations, named after Claude-Louis Navier and George Gabriel Stokes, describe the motion of viscous Fluid substances such

Multigrid can be generalized in many different ways. It can be applied naturally in a time-stepping solution of parabolic equations, or it can be applied directly to time-dependent partial differential equations. A parabolic partial differential equation is a type of second-order Partial differential equation, describing a wide family of problems in science including Heat diffusion In Mathematics, partial differential equations ( PDE) are a type of Differential equation, i Research on multilevel techniques for hyperbolic equations is under way. In Mathematics, a hyperbolic partial differential equation is usually a second-order Partial differential equation (PDE of the form A u_{xx} Multigrid can also be applied to integral equations, or for problems in statistical physics. In Mathematics, an integral equation is an equation in which an unknown function appears under an Integral sign Statistical physics is one of the fundamental theories of Physics, and uses methods of Statistics in solving physical problems

Other extensions of multigrid include techniques where no PDE and no geometrical problem background is used to construct the multilevel hierarchy. Such algebraic multigrid methods (AMG) construct their hierarchy of operators directly from the system matrix and thus become true black-box solvers for sparse matrices. In the mathematical subfield of Numerical analysis a sparse matrix is a matrix populated primarily with zeros

The finite element method becomes multigrid by choosing linear wavelets as the basis. The finite element method (FEM (sometimes referred to as finite element analysis) is a numerical technique for finding approximate solutions of Partial differential A wavelet is a mathematical function used to divide a given function or continuous-time signal into different frequency components and study each component with a resolution

1 Algorithm
2 Convergence rate
3 See also
4 References
5 External links

Algorithm

There are many variations of multigrid algorithms, but the common features are that a hierarchy of discretisations (grids) is considered. The important steps are:

Smoothing – reducing high frequency errors, for example using a few iterations of the Gauss–Seidel method. The Gauss–Seidel method is a technique used to solve a Linear system of equations.
Restriction – downsampling the residual error to a coarser grid. Loosely speaking a residual is the error in a result To be precise suppose we want to find x such that f(x=b
Prolongation – interpolating a correction computed on a coarser grid into a finer grid.

Convergence rate

This approach has the advantage over other methods that it often scales linearly with the number of discrete nodes used. That is: 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 $i$ with a given grid point density $N i$ . Assume furthermore that a solution on any grid $N i$ may be obtained with a given effort $W i = ρ K N i$ from a solution on a coarser grid $i + 1$ . Here, $ρ = N j + 1 / N j < 1$ is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and $K$ 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 $k$ :

W k = W k + 1 + ρ K N k

And in particular, we find for the finest grid $N 1$ that

W 1 = W 2 + ρ K N 1

Combining these two expressions (and using $N k = ρ k - 1 N 1$ ) gives

$W_1 = K N_1 \sum_{p=0}^n \rho^p$

Using the geometric series, we then find (for finite $n$ )

$W_1 < K N_1 \frac{1}{1 - \rho}$

that is, a solution may be obtained in $O (N)$ time. In Mathematics, a geometric series is a series with a constant ratio between successive terms.

References

Achi Brandt, Multi-Level Adaptive Solutions to Boundary-Value Problems, Math. Numerical analysis is the study of Algorithms for the problems of continuous mathematics (as distinguished from Discrete mathematics) In Mathematics, partial differential equations ( PDE) are a type of Differential equation, i The finite element method (FEM (sometimes referred to as finite element analysis) is a numerical technique for finding approximate solutions of Partial differential A finite difference is a mathematical expression of the form f ( x + b) &minus f ( x + a) Spectral methods are a class of techniques used in Applied mathematics and Scientific computing to numerically solve certain Partial differential equations In Mathematics, Numerical analysis, and numerical Partial differential equations domain decomposition methods solve a Boundary value problem Achi Brandt (אחי ברנדט born 1938 in Givat Brenner, Israel) is an Israeli Mathematician, noted for his pioneering contributions to Multigrid Comp, 1977(31), 333-390 (jstor link).
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

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Algorithm

Convergence rate

See also

References

External links