In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...
, the balancing domain decomposition method (BDD) is an
iterative method
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
to find the solution of a
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
positive definite system of
linear
Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
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 many authors, the term ''algebraic equation ...
s arising from the
finite element method
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
.
[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 simulation
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the ...
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
Bending of plates, or plate bending, refers to the deflection of a plate perpendicular to the plane of the plate under the action of external forces and moments. The amount of deflection can be determined by solving the differential equations o ...
, 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, positive definite systems of linear equations that arise from the finite element method. BDDC is used as a p ...
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
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denot ...
s 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 In linear algebra and the theory of matrices, the Schur complement of a block matrix is defined as follows.
Suppose ''p'', ''q'' are nonnegative integers, and suppose ''A'', ''B'', ''C'', ''D'' are respectively ''p'' × ''p'', ''p'' × ''q'', ''q'' ...
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