Multigrid method
Encyclopedia
Multigrid methods in numerical analysis
are a group of algorithm
s for solving differential equations using a hierarchy
of discretization
s. They are an example of a class of techniques called multiresolution methods
, very useful in (but not limited to) problems exhibiting multiple scales
of behavior. For example, many basic relaxation method
s exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid.
MG methods can be used as solvers as well as preconditioner
s.
The main idea of multigrid is to accelerate the convergence of a basic iterative method by global correction from time to time, accomplished by solving a coarse problem. This principle is similar to interpolation
between coarser and finer grids. The typical application for multigrid is in the numerical solution of elliptic
partial differential equation
s in two or more dimensions.
Multigrid methods can be applied in combination with any of the common discretization techniques. For example, the finite element method
may be recast as a multigrid method. In these cases, multigrid methods are among the fastest solution techniques known today. In contrast to other methods, multigrid methods are general in that they can treat arbitrary regions and boundary conditions. They do not depend on the separability of the equations
or other special properties of the equation. They are also directly applicable to more-complicated non-symmetric and nonlinear systems of equations, like the Lamé system of elasticity
or the Navier-Stokes equations
.
Assume that one has a differential equation which can be solved approximately (with a given accuracy) on a grid
with a given grid point
density
. Assume furthermore that a solution on any grid 
may be obtained with a given
effort
from a solution on a coarser grid 
. Here, 
is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and 
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
:
And in particular, we find for the finest grid
that
Combining these two expressions (and using
) gives
Using the geometric series, we then find (for finite
)
that is, a solution may be obtained in
time.
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. Its main advantage versus a purely multigrid solver is particularly clear for nonlinear problems, e.g., eigenvalue problems.
s, or they can be applied directly to time-dependent partial differential equation
s. Research on multilevel techniques for hyperbolic partial differential equation
s is underway. Multigrid methods can also be applied to integral equation
s, or for problems in statistical physics
.
Other extensions of multigrid methods include techniques where no partial differential equation nor 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 the levels of the hierarchy are simply subsets of unknowns without any geometric interpretation. Thus, AMG methods become true black-box solvers for sparse matrices. However, AMG is regarded as advantageous mainly where geometric multigrid is too difficult to apply.
Another set of multiresolution methods is based upon wavelets. These wavelet methods can be combined with multigrid methods. For example, one use of wavelets is to reformulate the finite element approach in terms of a multilevel method.
Adaptive multigrid exhibits adaptive mesh refinement
, that is, it adjusts the grid as the computation proceeds, in a manner dependent upon the computation itself. The idea is to increase resolution of the grid only in regions of the solution where it is needed.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
are a group of algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s for solving differential equations using a hierarchy
Hierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...
of discretization
Discretization
In mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical evaluation and implementation on digital computers...
s. They are an example of a class of techniques called multiresolution methods
Multiresolution analysis
A multiresolution analysis or multiscale approximation is the design method of most of the practically relevant discrete wavelet transforms and the justification for the algorithm of the fast wavelet transform...
, very useful in (but not limited to) problems exhibiting multiple scales
Multiscale modeling
In engineering, mathematics, physics, meteorology and computer science, multiscale modeling is the field of solving physical problems which have important features at multiple scales, particularly multiple spatial and temporal scales. Important problems include scale linking...
of behavior. For example, many basic relaxation method
Relaxation method
In numerical mathematics, relaxation methods are iterative methods for solving systems of equations, including nonlinear systems.Relaxation methods were developed for solving large sparse linear systems, which arose as finite-difference discretizations of differential equations...
s exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid.
MG methods can be used as solvers as well as preconditioner
Preconditioner
In mathematics, preconditioning is a procedure of an application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solution. Preconditioning is typically related to reducing a condition number of the problem...
s.
The main idea of multigrid is to accelerate the convergence of a basic iterative method by global correction from time to time, accomplished by solving a coarse problem. This principle is similar to interpolation
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
between coarser and finer grids. The typical application for multigrid is in the numerical solution of elliptic
Elliptic operator
In the theory of partial differential equations, elliptic operators are differential operators that generalize the Laplace operator. They are defined by the condition that the coefficients of the highest-order derivatives be positive, which implies the key property that the principal symbol is...
partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s in two or more dimensions.
Multigrid methods can be applied in combination with any of the common discretization techniques. For example, the finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
may be recast as a multigrid method. In these cases, multigrid methods are among the fastest solution techniques known today. In contrast to other methods, multigrid methods are general in that they can treat arbitrary regions and boundary conditions. They do not depend on the separability of the equations
Separable partial differential equation
A separable partial differential equation is one that can be broken into a set of separate equations of lower dimensionality by a method of separation of variables. This generally relies upon the problem having some special form or symmetry...
or other special properties of the equation. They are also directly applicable to more-complicated non-symmetric and nonlinear systems of equations, like the Lamé system of elasticity
Elasticity (physics)
In physics, elasticity is the physical property of a material that returns to its original shape after the stress that made it deform or distort is removed. The relative amount of deformation is called the strain....
or the Navier-Stokes equations
Navier-Stokes equations
In physics, the Navier–Stokes equations, named after Claude-Louis Navier and George Gabriel Stokes, describe the motion of fluid substances. These equations arise from applying Newton's second law to fluid motion, together with the assumption that the fluid stress is the sum of a diffusing viscous...
.
Algorithm
There are many variations of multigrid algorithms, but the common features are that a hierarchy of discretizations (grids) is considered. The important steps are:- Smoothing – reducing high frequency errors, for example using a few iterations of the Gauss–Seidel method.
- Restriction – downsampling the residual error to a coarser grid.
- Interpolation or Prolongation – interpolating a correction computed on a coarser grid into a finer grid.
Computational cost
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
with a given grid pointdensity
. Assume furthermore that a solution on any grid may be obtained with a giveneffort
from a solution on a coarser grid . Here, is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and 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
:And in particular, we find for the finest grid
thatCombining these two expressions (and using
) givesUsing the geometric series, we then find (for finite
)that is, a solution may be obtained in
time.Multigrid preconditioning
A multigrid method with an intentionally reduced tolerance can be used as an efficient preconditioner for an external iterative solver. The solution may still be obtained in 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. Its main advantage versus a purely multigrid solver is particularly clear for nonlinear problems, e.g., eigenvalue problems.Generalized multigrid methods
Multigrid methods can be generalized in many different ways. They can be applied naturally in a time-stepping solution of parabolic partial differential equationParabolic partial differential equation
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, ocean acoustic propagation, in physical or mathematical systems with a time variable, and which behave essentially like heat...
s, or they can be applied directly to time-dependent partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s. Research on multilevel techniques for hyperbolic partial differential equation
Hyperbolic partial differential equation
In mathematics, a hyperbolic partial differential equation of order n is a partial differential equation that, roughly speaking, has a well-posed initial value problem for the first n−1 derivatives. More precisely, the Cauchy problem can be locally solved for arbitrary initial data along...
s is underway. Multigrid methods can also be applied to integral equation
Integral equation
In mathematics, an integral equation is an equation in which an unknown function appears under an integral sign. There is a close connection between differential and integral equations, and some problems may be formulated either way...
s, or for problems in statistical physics
Statistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
.
Other extensions of multigrid methods include techniques where no partial differential equation nor 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 the levels of the hierarchy are simply subsets of unknowns without any geometric interpretation. Thus, AMG methods become true black-box solvers for sparse matrices. However, AMG is regarded as advantageous mainly where geometric multigrid is too difficult to apply.
Another set of multiresolution methods is based upon wavelets. These wavelet methods can be combined with multigrid methods. For example, one use of wavelets is to reformulate the finite element approach in terms of a multilevel method.
Adaptive multigrid exhibits adaptive mesh refinement
Adaptive mesh refinement
In numerical analysis, adaptive mesh refinement is a method of adaptive meshing. Central to any Eulerian method is the manner in which it discretizes the continuous domain of interest into a grid of many individual elements...
, that is, it adjusts the grid as the computation proceeds, in a manner dependent upon the computation itself. The idea is to increase resolution of the grid only in regions of the solution where it is needed.