In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, the balancing domain decomposition method (BDD) is an
iterative method
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
to find the solution of a
symmetric positive definite system of
linear
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a '' function'' (or '' mapping'');
* linearity of a '' polynomial''.
An example of a linear function is the function defined by f(x) ...
algebraic equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form P = 0, where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers.
For example, x^5-3x+1=0 is an algebraic equati ...
s arising from the
finite element method.
[J. Mandel, ''Balancing domain decomposition'', Comm. Numer. Methods Engrg., 9 (1993), pp. 233–241.
] 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
A petroleum reservoir or oil and gas reservoir is a subsurface accumulation of hydrocarbons contained in Porosity, porous or fractured rock formations. Such reservoirs form when kerogen (ancient plant matter) is created in surrounding rock by t ...
simulation
A simulation is an imitative representation of a process or system that could exist in the real world. In this broad sense, simulation can often be used interchangeably with model. Sometimes a clear distinction between the two terms is made, in ...
by
mixed finite elements.
[L. C. Cowsar, J. Mandel, and M. F. Wheeler, ''Balancing domain decomposition for mixed finite elements'', Math. Comp., 64 (1995), pp. 989–1015.
] 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,
[P. Le Tallec, J. Mandel, and M. Vidrascu, ''A Neumann–Neumann domain decomposition algorithm for solving plate and shell problems'', SIAM Journal on Numerical Analysis, 35 (1998), pp. 836–867.
] which makes it however more expensive. The
BDDC
In numerical analysis, BDDC (balancing domain decomposition by constraints) is a domain decomposition method for solving large symmetric matrix, symmetric, positive definite matrix, positive definite systems of linear equations that arise from the ...
method uses the same corner basis functions as,
but in an additive rather than multiplicative fashion.
[J. Mandel and C. R. Dohrmann, ''Convergence of a balancing domain decomposition by constraints and energy minimization'', Numer. Linear Algebra Appl., 10 (2003), pp. 639–659.
] 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
[M. Bhardwaj, D. Day, C. Farhat, M. Lesoinne, K. Pierson, and D. Rixen, ''Application of the FETI method to ASCI problems – scalability results on 1000 processors and discussion of highly heterogeneous problems'', International Journal for Numerical Methods in Engineering, 47 (2000), pp. 513–535.
] has the same
eigenvalues and thus essentially the same performance as BDD.
[Y. Fragakis, ''Force and displacement duality in Domain Decomposition Methods for Solid and Structural Mechanics''. To appear in Comput. Methods Appl. Mech. Engrg., 2007.
][B. Sousedík and J. Mandel, ''On the equivalence of primal and dual substructuring preconditioners''. arXiv:math/0802.4328, 2008.]
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 is a member of the
Neumann–Neumann class of methods, so named 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.
References
External links
BDD reference implementation at mgnet.orgDomain Decomposition – Theory, publications, methods, algorithms.
{{DEFAULTSORT:Balancing Domain Decomposition
Domain decomposition methods