BDDC
Encyclopedia
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 preconditioner
to the conjugate gradient method
. A specific version of BDDC is characterized by the choice of coarse degrees of freedom, which can be values at the corners of the subdomains, or averages over the edges or the faces of the interface between the subdomains. One application of the BDDC preconditioner then combines the solution of local problems on each subdomains with the solution of a global coarse problem with the coarse degrees of freedom as the unknowns. The local problems on different subdomains are completely independent of each other, so the method is suitable for parallel computing
. With a proper choice of the coarse degrees of freedom (corners in 2D, corners plus edges or corners plus faces in 3D) and with regular subdomain shapes, the condition number
of the method is bounded when increasing the number of subdomains, and it grows only very slowly with the number of elements per subdomain. Thus the number of iterations is bounded in the same way, and the method scales well with the problem size and the number of subdomains.
domain decomposition method by Farhat
et al.. The name of the method was coined by Mandel
and Dohrmann, because it can be understood as further development of the BDD (balancing domain decomposition
) method. The same method was also proposed independently by Fragakis and Papadrakakis under the name P-FETI-DP, and by Cros , which, however, was not recognized for some time. See for a proof that these are all actually the same method as BDDC. Mandel, Dohrmann, and Tezaur proved that the eigenvalues of BDDC and FETI-DP are identical, except for the eigenvalue equal to one, which may be present in BDDC but not for FETI-DP, and thus their number of iterations is practically the same. Much simpler proofs of this fact were obtained later by Li and Widlund
and by Brenner and Sung .
s and shells
. The difference is that in BDDC, the coarse problem is used in an additive fashion, while in BDD, it is used a multiplicatively.
, and it can be perhaps best explained in terms of the deformation of an elastic structure. The elasticity problem is to determine the deformation of a structure subject to prescribed displacements and forces applied to it. After applying the finite element method, we obtain a system of linear algebraic equations, where the unknowns are the displacements at the nodes of the elements and the right-hand side comes from the forces (and from nonzero prescribed displacements on the boundary, but, for simplicity, assume that these are zero).
A preconditioner takes a right hand side and delivers an approximate solution. So, suppose we have an elastic structure divided into nonoverlappling substructures, and, for simplicity, suppose the coarse degrees of freedom are only subdomain corners. Suppose forces applied to the structure are given.
The first step in the BDDC method is the interior correction, which consists of finding the deformation of each subdomain separately given the forces applied to the subdomain except at the interface of the subdomain with its neighbors. Since the interior of each subdomain moves independently and the interface remains at zero deformation, this causes kinks at the interface. The forces on the interface necessary to keep the kinks in balance are added to the forces already given on the interface. The interface forces are then distributed to the subdomain (either equally, or with weights in proportion to the stiffness of the material of the subdomains, so that stiffer subdomains get more force).
The second step, called subdomain correction, is finding the deformation for these interface forces on each subdomain separately subject to the condition of zero displacements on the subdomain corners. Note that the values of the subdomain correction across the interface in general differ.
At the same time as the subdomain correction, the coarse correction is computed, which consists of the displacement at all subdomain corners, interpolated between the corners on each subdomain separately by the condition that the subdomain assumes the same shape as it would with no forces applied to it at all. Then the interface forces, same as for the subdomain correction, are applied to find the values of the coarse correction at subdomain corners. Thus, the interface forces are averaged and the coarse solution is found by the Galerkin method
. Again, the values of the coarse correction on subdomain interfaces is in general discontinuous across the interface.
Finally, the subdomain corrections and the coarse correction are added and the sum is averaged across the subdomain interfaces, with the same weights as were used to distribute the forces to the subdomain earlier. This gives the value of the output of BDDC on the interfaces between the subdomains. The values of the output of BDDC in the interior of the subdomains are then obtained by repeating the interior correction.
In a practical implementation, the right-hand-side and the initial approximation for the iterations are preprocessed so that all forces inside the subdomains are zero. This is done by one application of the interior correction as above. Then the forces inside the subdomains stay zero during the conjugate gradients iterations, and so the first interior correction in each application of BDDC can be omitted.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, BDDC (balancing domain decomposition by constraints) is a 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 :...
for solving large symmetric, positive definite systems of linear equations that arise 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...
. BDDC is used as a preconditioner
Preconditioner
In mathematics, preconditioning is a procedure of an application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solution. Preconditioning is typically related to reducing a condition number of the problem...
to the conjugate gradient method
Conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. The conjugate gradient method is an iterative method, so it can be applied to sparse systems that are too...
. A specific version of BDDC is characterized by the choice of coarse degrees of freedom, which can be values at the corners of the subdomains, or averages over the edges or the faces of the interface between the subdomains. One application of the BDDC preconditioner then combines the solution of local problems on each subdomains with the solution of a global coarse problem with the coarse degrees of freedom as the unknowns. The local problems on different subdomains are completely independent of each other, so the method is suitable for parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
. With a proper choice of the coarse degrees of freedom (corners in 2D, corners plus edges or corners plus faces in 3D) and with regular subdomain shapes, the condition number
Condition number
In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument...
of the method is bounded when increasing the number of subdomains, and it grows only very slowly with the number of elements per subdomain. Thus the number of iterations is bounded in the same way, and the method scales well with the problem size and the number of subdomains.
History
BDDC was introduced by Dohrmann as a simpler primal alternative to the FETI-DPFETI-DP
The FETI-DP method is a domain decomposition method that enforces equality of the solution at subdomain interfaces by Lagrange multipliers except at subdomain corners, which remain primal variables.The first mathematical analysis of the method was provided by Mandel and Tezaur...
domain decomposition method by Farhat
Charbel Farhat
Charbel Farhat is the Vivian Church Hoff Professor of Aircraft Structures in the School of Engineering at Stanford University, where he is also Chairman of the Department of Aeronautics and Astronautics, Professor of Mechanical Engineering, Professor in the Institute for Computational and...
et al.. The name of the method was coined by Mandel
Jan Mandel
Jan Mandel is a Czech-American mathematician. He received his PhD from the Faculty of Mathematics and Physics, Charles University in Prague and was a Senior Research Scientist there. Since 1986, he is professor of Mathematics at the University of Colorado Denver.He has worked in the field of...
and Dohrmann, because it can be understood as further development of the BDD (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...
) method. The same method was also proposed independently by Fragakis and Papadrakakis under the name P-FETI-DP, and by Cros , which, however, was not recognized for some time. See for a proof that these are all actually the same method as BDDC. Mandel, Dohrmann, and Tezaur proved that the eigenvalues of BDDC and FETI-DP are identical, except for the eigenvalue equal to one, which may be present in BDDC but not for FETI-DP, and thus their number of iterations is practically the same. Much simpler proofs of this fact were obtained later by Li and Widlund
Olof B. Widlund
Olof B. Widlund, born 1938, is a Swedish-American mathematician. He is well known for his leading role in and fundamental contributions to domain decomposition methods. He received his Ph.D...
and by Brenner and Sung .
Coarse space
The coarse space of BDDC consists of energy minimal functions with the given values of the coarse degrees of freedom. This is the same coarse space as used for corners in a version of BDD for plateBending
In engineering mechanics, bending characterizes the behavior of a slender structural element subjected to an external load applied perpendicularly to a longitudinal axis of the element. The structural element is assumed to be such that at least one of its dimensions is a small fraction, typically...
s and shells
Thin-shell structure
Thin-shell structures are light weight constructions using shell elements. These elements are typically curved and are assembled to large structures...
. The difference is that in BDDC, the coarse problem is used in an additive fashion, while in BDD, it is used a multiplicatively.
A mechanical description
The BDDC method is often used to solve problems from linear elasticityLinear elasticity
Linear elasticity is the mathematical study of how solid objects deform and become internally stressed due to prescribed loading conditions. Linear elasticity models materials as continua. Linear elasticity is a simplification of the more general nonlinear theory of elasticity and is a branch of...
, and it can be perhaps best explained in terms of the deformation of an elastic structure. The elasticity problem is to determine the deformation of a structure subject to prescribed displacements and forces applied to it. After applying the finite element method, we obtain a system of linear algebraic equations, where the unknowns are the displacements at the nodes of the elements and the right-hand side comes from the forces (and from nonzero prescribed displacements on the boundary, but, for simplicity, assume that these are zero).
A preconditioner takes a right hand side and delivers an approximate solution. So, suppose we have an elastic structure divided into nonoverlappling substructures, and, for simplicity, suppose the coarse degrees of freedom are only subdomain corners. Suppose forces applied to the structure are given.
The first step in the BDDC method is the interior correction, which consists of finding the deformation of each subdomain separately given the forces applied to the subdomain except at the interface of the subdomain with its neighbors. Since the interior of each subdomain moves independently and the interface remains at zero deformation, this causes kinks at the interface. The forces on the interface necessary to keep the kinks in balance are added to the forces already given on the interface. The interface forces are then distributed to the subdomain (either equally, or with weights in proportion to the stiffness of the material of the subdomains, so that stiffer subdomains get more force).
The second step, called subdomain correction, is finding the deformation for these interface forces on each subdomain separately subject to the condition of zero displacements on the subdomain corners. Note that the values of the subdomain correction across the interface in general differ.
At the same time as the subdomain correction, the coarse correction is computed, which consists of the displacement at all subdomain corners, interpolated between the corners on each subdomain separately by the condition that the subdomain assumes the same shape as it would with no forces applied to it at all. Then the interface forces, same as for the subdomain correction, are applied to find the values of the coarse correction at subdomain corners. Thus, the interface forces are averaged and the coarse solution is found by the Galerkin method
Galerkin method
In mathematics, in the area of numerical analysis, Galerkin methods are a class of methods for converting a continuous operator problem to a discrete problem. In principle, it is the equivalent of applying the method of variation of parameters to a function space, by converting the equation to a...
. Again, the values of the coarse correction on subdomain interfaces is in general discontinuous across the interface.
Finally, the subdomain corrections and the coarse correction are added and the sum is averaged across the subdomain interfaces, with the same weights as were used to distribute the forces to the subdomain earlier. This gives the value of the output of BDDC on the interfaces between the subdomains. The values of the output of BDDC in the interior of the subdomains are then obtained by repeating the interior correction.
In a practical implementation, the right-hand-side and the initial approximation for the iterations are preprocessed so that all forces inside the subdomains are zero. This is done by one application of the interior correction as above. Then the forces inside the subdomains stay zero during the conjugate gradients iterations, and so the first interior correction in each application of BDDC can be omitted.
External links
- Authors' comments to the "fast breaking paperInstitute for Scientific InformationThe Institute for Scientific Information was founded by Eugene Garfield in 1960. It was acquired by Thomson Scientific & Healthcare in 1992, became known as Thomson ISI and now is part of the Healthcare & Science business of the multi-billion dollar Thomson Reuters Corporation.ISI offered...
" , ESI Special Topics, June 2007 - Authors' comments to the "fast breaking paper" , ESI Special Topics, June 2007