Coarse space (numerical analysis)
Encyclopedia
In numerical analysis
, coarse problem is an auxiliary system of equations used in an iterative method
for the solution of a given larger system of equations. A coarse problem is basically a version of the same problem at a lower resolution, retaining its essential characteristics, but with fewer variables. The purpose of the coarse problem is to propagate information throughout the whole problem globally.
In multigrid method
s for partial differential equation
s, the coarse problem is typically obtained as a discretization of the same equation on a coarser grid (usually, in finite difference method
s) or by a Galerkin approximation on a subspace
, called a coarse space. In finite element method
s, the Galerkin approximation is typically used, with the coarse space generated by larger elements on the same domain
. Typically, the coarse problem corresponds to a grid that is twice or three times coarser.
In domain decomposition method
s, the construction of a coarse problem follows the same principles as in multigrid methods, but the coarser problem has much fewer unknowns, generally only one or just a few unknowns per subdomain or substructure, and the coarse space can be of a quite different type that the original finite element space, e.g. piecewise constants with averaging in balancing domain decomposition
or built from energy minimal functions in BDDC
. The construction of the coarse problem in FETI
is unusual in that it is not obtained as a Galerkin approximation of the original problem, however.
In Algebraic Multigrid Methods and in iterative aggregation methods in mathematical economics
and Markov chain
s, the coarse problem is generally obtained by the Galerkin approximation on a subspace. In mathematical economics, the coarse problem may be obtained by the aggregation of products or industries into a coarse description with fewer variables. In Markov chains, a coarse Markov chain may be obtained by aggregating states.
The speed of convergence of multigrid and domain decomposition methods for elliptic partial differential equations without a coarse problem deteriorates with decreasing mesh step (or decreasing element size, or increasing number of subdomains or substructures), thus making a coarse problem necessary for a scalable algorithm.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, coarse problem is an auxiliary system of equations used in an iterative method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
for the solution of a given larger system of equations. A coarse problem is basically a version of the same problem at a lower resolution, retaining its essential characteristics, but with fewer variables. The purpose of the coarse problem is to propagate information throughout the whole problem globally.
In multigrid method
Multigrid method
Multigrid methods in numerical analysis are a group of algorithms for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhibiting multiple scales of behavior...
s for 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, the coarse problem is typically obtained as a discretization of the same equation on a coarser grid (usually, in finite difference method
Finite difference method
In mathematics, finite-difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives.- Derivation from Taylor's polynomial :...
s) or by a Galerkin approximation on a subspace
Subspace
-In mathematics:* Euclidean subspace, in linear algebra, a set of vectors in n-dimensional Euclidean space that is closed under addition and scalar multiplication...
, called a coarse space. In 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...
s, the Galerkin approximation is typically used, with the coarse space generated by larger elements on the same domain
Domain decomposition methods
]In mathematics, numerical analysis, and numerical partial differential equations, domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains...
. Typically, the coarse problem corresponds to a grid that is twice or three times coarser.
In domain decomposition method
Domain decomposition method
In mathematics, the additive Schwarz method, named after Hermann Schwarz, solves a boundary value problem for a partial differential equation approximately by splitting it into boundary value problems on smaller domains and adding the results.- Overview :...
s, the construction of a coarse problem follows the same principles as in multigrid methods, but the coarser problem has much fewer unknowns, generally only one or just a few unknowns per subdomain or substructure, and the coarse space can be of a quite different type that the original finite element space, e.g. piecewise constants with averaging in balancing domain decomposition
Balancing domain decomposition
In numerical analysis, the balancing domain decomposition method is an iterative method to find the solution of a symmetric positive definite system of linear algebraic equations arising from the finite element method . In each iteration, it combines the solution of local problems on...
or built from energy minimal functions in BDDC
BDDC
In numerical analysis, BDDC is a domain decomposition method for solving large symmetric, positive definite systems of linear equations that arise from the finite element method. BDDC is used as a preconditioner to the conjugate gradient method...
. The construction of the coarse problem in FETI
FETI
In mathematics, in particular numerical analysis, the FETI method is an iterative substructuring method for solving systems of linear equations from the finite element method for the solution of elliptic partial differential equations, in particular in computational mechanics In each iteration,...
is unusual in that it is not obtained as a Galerkin approximation of the original problem, however.
In Algebraic Multigrid Methods and in iterative aggregation methods in mathematical economics
Mathematical economics
Mathematical economics is the application of mathematical methods to represent economic theories and analyze problems posed in economics. It allows formulation and derivation of key relationships in a theory with clarity, generality, rigor, and simplicity...
and Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
s, the coarse problem is generally obtained by the Galerkin approximation on a subspace. In mathematical economics, the coarse problem may be obtained by the aggregation of products or industries into a coarse description with fewer variables. In Markov chains, a coarse Markov chain may be obtained by aggregating states.
The speed of convergence of multigrid and domain decomposition methods for elliptic partial differential equations without a coarse problem deteriorates with decreasing mesh step (or decreasing element size, or increasing number of subdomains or substructures), thus making a coarse problem necessary for a scalable algorithm.