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 ''n''-th approximation is derived fr ...
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 definiti ...
positive definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular:
* Positive-definite bilinear form
* Positive-definite f ...
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 r ...
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
A petroleum reservoir or oil and gas reservoir is a subsurface accumulation of hydrocarbons contained in porous or fractured rock formations.
Such reservoirs form when kerogen (ancient plant matter) is created in surrounding rock by the presence ...
simulation
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of Conceptual model, models; the model represents the key characteristics or behaviors of the selected system or proc ...
by
mixed finite elements
Mixed is the past tense of ''mix''.
Mixed may refer to:
* Mixed (United Kingdom ethnicity category), an ethnicity category that has been used by the United Kingdom's Office for National Statistics since the 1991 Census
* ''Mixed'' (album), a c ...
.
[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
Elasticity often refers to:
*Elasticity (physics), continuum mechanics of bodies that deform reversibly under stress
Elasticity may also refer to:
Information technology
* Elasticity (data store), the flexibility of the data model and the cl ...
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 of ...
, 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 prec ...
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 denoted b ...
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 problem
In mathematics, the Neumann (or second-type) boundary condition is a type of boundary condition, named after Carl Neumann.
When imposed on an ordinary or a partial differential equation, the condition specifies the values of the derivative appli ...
s 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
In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kernel of ...
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