Balancing domain decomposition
Encyclopedia
In numerical analysis
, the balancing domain decomposition method (BDD) 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 non-overlapping subdomains with a coarse problem created from the subdomain nullspaces
. BDD requires only solution of subdomain problems rather than access to the matrices of those problems, so it is applicable to situations where only the solution operators are available, such as in oil reservoir
simulation
by mixed finite elements . In its original formulation, BDD performs well only for 2nd order problems, such elasticity
in 2D and 3D. For 4th order problems, such as plate bending, it needs to be modified by adding to the coarse problem special basis functions that enforce continuity of the solution at subdomain corners , which makes it however more expensive. The BDDC
method uses the same corner basis functions as , but in an additive rather than mutiplicative fashion . The dual counterpart to BDD is FETI
, which enforces the equality of the solution between the subdomain by Lagrange multipliers. The base versions of BDD and FETI are not mathematically equivalent, though a special version of FETI designed to be robust for hard problems has the same eigenvalues and thus essentially the same performance as BDD.
The operator of the system solved by BDD is the same as obtained by eliminating the unknowns in the interiors of the subdomain, thus reducing the problem to the Schur complement
on the subdomain interface. Since the BDD preconditioner involves the solution of Neumann problems on all subdomain, it belongs to class of Neumann–Neumann methods, named so because they solve a Neumann problem on both sides of the interface between subdomains.
In the simplest case, the coarse space of BDD consists of functions constant on each subdomain and averaged on the interfaces. More generally, on each subdomain, the coarse space needs to only contain the nullspace of the problem as a subspace.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, the balancing domain decomposition method (BDD) is 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...
to find the solution of a symmetric positive definite system of linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
algebraic equations arising from 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...
. In each iteration, it combines the solution of local problems on non-overlapping subdomains with a coarse problem created from the subdomain nullspaces
Null space
In linear algebra, the kernel or null space of a matrix A is the set of all vectors x for which Ax = 0. The kernel of a matrix with n columns is a linear subspace of n-dimensional Euclidean space...
. BDD requires only solution of subdomain problems rather than access to the matrices of those problems, so it is applicable to situations where only the solution operators are available, such as in oil reservoir
Oil reservoir
A petroleum reservoir, or oil and gas reservoir, is a subsurface pool of hydrocarbons contained in porous or fractured rock formations. The naturally occurring hydrocarbons, such as crude oil or natural gas, are trapped by overlying rock formations with lower permeability...
simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
by mixed finite elements . In its original formulation, BDD performs well only for 2nd order problems, such 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....
in 2D and 3D. For 4th order problems, such as plate bending, it needs to be modified by adding to the coarse problem special basis functions that enforce continuity of the solution at subdomain corners , which makes it however more expensive. The 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...
method uses the same corner basis functions as , but in an additive rather than mutiplicative fashion . The dual counterpart to BDD is 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,...
, which enforces the equality of the solution between the subdomain by Lagrange multipliers. The base versions of BDD and FETI are not mathematically equivalent, though a special version of FETI designed to be robust for hard problems has the same eigenvalues and thus essentially the same performance as BDD.
The operator of the system solved by BDD is the same as obtained by eliminating the unknowns in the interiors of the subdomain, thus reducing the problem to the Schur complement
Schur complement
In linear algebra and the theory of matrices,the Schur complement of a matrix block is defined as follows.Suppose A, B, C, D are respectivelyp×p, p×q, q×p...
on the subdomain interface. Since the BDD preconditioner involves the solution of Neumann problems on all subdomain, it belongs to class of Neumann–Neumann methods, named so because they solve a Neumann problem on both sides of the interface between subdomains.
In the simplest case, the coarse space of BDD consists of functions constant on each subdomain and averaged on the interfaces. More generally, on each subdomain, the coarse space needs to only contain the nullspace of the problem as a subspace.