BDDC

Last updated

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.

Contents

History

BDDC was introduced by different authors and different approaches at about the same time, i.e., by Cros, [1] Dohrmann, [2] and Fragakis and Papadrakakis, [3] as a primal alternative to the FETI-DP domain decomposition method by Farhat et al. [4] [5] See [6] for a proof that these are all actually the same method as BDDC. The name of the method was coined by Mandel and Dohrmann, [7] because it can be understood as further development of the BDD (balancing domain decomposition) method. [8] Mandel, Dohrmann, and Tezaur [9] 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 [10] and by Brenner and Sung. [11]

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 plates and shells. [12] 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 elasticity, 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 nonoverlapping 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.

Related Research Articles

Numerical methods for partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

In numerical analysis, a multigrid method is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhibiting multiple scales of behavior. For example, many basic relaxation methods exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid. MG methods can be used as solvers as well as preconditioners.

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, FETI requires the solution of a Neumann problem in each substructure and the solution of a coarse problem. The simplest version of FETI with no preconditioner in the substructure is scalable with the number of substructures but the condition number grows polynomially with the number of elements per substructure. FETI with a preconditioner consisting of the solution of a Dirichlet problem in each substructure is scalable with the number of substructures and its condition number grows only polylogarithmically with the number of elements per substructure. The coarse space in FETI consists of the nullspace on each substructure.

Parallel mesh generation in numerical analysis is a new research area between the boundaries of two scientific computing disciplines: computational geometry and parallel computing. Parallel mesh generation methods decompose the original mesh generation problem into smaller subproblems which are solved (meshed) in parallel using multiple processors or threads. The existing parallel mesh generation methods can be classified in terms of two basic attributes:

  1. the sequential technique used for meshing the individual subproblems and
  2. the degree of coupling between the subproblems.
<span class="mw-page-title-main">Domain decomposition methods</span>

In mathematics, numerical analysis, and numerical partial differential equations, domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains. A coarse problem with one or few unknowns per subdomain is used to further coordinate the solution between the subdomains globally. The problems on the subdomains are independent, which makes domain decomposition methods suitable for parallel computing. Domain decomposition methods are typically used as preconditioners for Krylov space iterative methods, such as the conjugate gradient method, GMRES, and LOBPCG.

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. The method was further improved by enforcing the equality of averages across the edges or faces on subdomain interfaces which is important for parallel scalability for 3D problems. FETI-DP is a simplification and a better performing version of FETI. The eigenvalues of FETI-DP are same as those of BDDC, except for the eigenvalue equal to one, and so the performance of FETI-DP and BDDC is essentially same.

<span class="mw-page-title-main">Schwarz alternating method</span> Iterative method in conformal mapping

In mathematics, the Schwarz alternating method or alternating process is an iterative method introduced in 1869–1870 by Hermann Schwarz in the theory of conformal mapping. Given two overlapping regions in the complex plane in each of which the Dirichlet problem could be solved, Schwarz described an iterative method for solving the Dirichlet problem in their union, provided their intersection was suitably well behaved. This was one of several constructive techniques of conformal mapping developed by Schwarz as a contribution to the problem of uniformization, posed by Riemann in the 1850s and first resolved rigorously by Koebe and Poincaré in 1907. It furnished a scheme for uniformizing the union of two regions knowing how to uniformize each of them separately, provided their intersection was topologically a disk or an annulus. From 1870 onwards Carl Neumann also contributed to this theory.

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 multiplicative 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.

In mathematics, Neumann–Neumann methods are domain decomposition preconditioners named so because they solve a Neumann problem on each subdomain on both sides of the interface between the subdomains. Just like all domain decomposition methods, so that the number of iterations does not grow with the number of subdomains, Neumann–Neumann methods require the solution of a coarse problem to provide global communication. The balancing domain decomposition is a Neumann–Neumann method with a special kind of coarse problem.

In mathematics, the Neumann–Dirichlet method is a domain decomposition preconditioner which involves solving Neumann boundary value problem on one subdomain and Dirichlet boundary value problem on another, adjacent across the interface between the subdomains. On a problem with many subdomains organized in a rectangular mesh, the subdomains are assigned Neumann or Dirichlet problems in a checkerboard fashion.

In numerical analysis, mortar methods are discretization methods for partial differential equations, which use separate finite element discretization on nonoverlapping subdomains. The meshes on the subdomains do not match on the interface, and the equality of the solution is enforced by Lagrange multipliers, judiciously chosen to preserve the accuracy of the solution. Mortar discretizations lend themselves naturally to the solution by iterative domain decomposition methods such as FETI and balancing domain decomposition In the engineering practice in the finite element method, continuity of solutions between non-matching subdomains is implemented by multiple-point constraints.

In numerical analysis, the Schur complement method, named after Issai Schur, is the basic and the earliest version of non-overlapping domain decomposition method, also called iterative substructuring. A finite element problem is split into non-overlapping subdomains, and the unknowns in the interiors of the subdomains are eliminated. The remaining Schur complement system on the unknowns associated with subdomain interfaces is solved by the conjugate gradient method.

In mathematics, the abstract additive Schwarz method, named after Hermann Schwarz, is an abstract version of the additive Schwarz method for boundary value problems on partial differential equations, formulated only in terms of linear algebra without reference to domains, subdomains, etc. Many if not all domain decomposition methods can be cast as abstract additive Schwarz method, which is often the first and most convenient approach to their analysis.

In numerical analysis, coarse problem is an auxiliary system of equations used in an iterative method for the solution of a given larger system of equations. A coarse problem is basically a version of the same problem at a lower resolution, retaining its essential characteristics, but with fewer variables. The purpose of the coarse problem is to propagate information throughout the whole problem globally.

In mathematics, a Poincaré–Steklov operator maps the values of one boundary condition of the solution of an elliptic partial differential equation in a domain to the values of another boundary condition. Usually, either of the boundary conditions determines the solution. Thus, a Poincaré–Steklov operator encapsulates the boundary response of the system modelled by the partial differential equation. When the partial differential equation is discretized, for example by finite elements or finite differences, the discretization of the Poincaré–Steklov operator is the Schur complement obtained by eliminating all degrees of freedom inside the domain.

<span class="mw-page-title-main">Andrei Knyazev (mathematician)</span> American mathematician

Andrew Knyazev is an American mathematician. He graduated from the Faculty of Computational Mathematics and Cybernetics of Moscow State University under the supervision of Evgenii Georgievich D'yakonov in 1981 and obtained his PhD in Numerical Mathematics at the Russian Academy of Sciences under the supervision of Vyacheslav Ivanovich Lebedev in 1985. He worked at the Kurchatov Institute between 1981–1983, and then to 1992 at the Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences, headed by Gury Marchuk.

<span class="mw-page-title-main">João Arménio Correia Martins</span> Portuguese engineer (1951–2008)

João Arménio Correia Martins was born on November 11, 1951, at the southern town of Olhão in Portugal. He attended high school at the Liceu Nacional de Faro which he completed in 1969. Afterwards João Martins moved to Lisbon where he was graduate student of Civil Engineering at Instituto Superior Técnico (IST) until 1976. He was a research assistant and assistant instructor at IST until 1981. Subsequently, he entered the graduate school in the College of Engineering, Department of Aerospace Engineering and Engineering Mechanics of The University of Texas at Austin, USA. There he obtained a MSc in 1983 with a thesis titled A Numerical Analysis of a Class of Problems in Elastodynamics with Friction Effects and a PhD in 1986 with a thesis titled Dynamic Frictional Contact Problems Involving Metallic Bodies, both supervised by Prof. John Tinsley Oden. He returned to Portugal in 1986 and became assistant professor at IST. In 1989 he became associate professor and in 1996 he earned the academic degree of “agregado” from Universidade Técnica de Lisboa. Later, in 2005, he became full professor in the Department of Civil Engineering and Architecture of IST.

Eldon Robert Hansen is an American mathematician and author who has published in global optimization theory and interval arithmetic.

Dynamic Substructuring (DS) is an engineering tool used to model and analyse the dynamics of mechanical systems by means of its components or substructures. Using the dynamic substructuring approach one is able to analyse the dynamic behaviour of substructures separately and to later on calculate the assembled dynamics using coupling procedures. Dynamic substructuring has several advantages over the analysis of the fully assembled system:

References

  1. ↑ J.-M. Cros, A preconditioner for the Schur complement domain decomposition method, in Domain Decomposition Methods in Science and Engineering, I. Herrera, D. E. Keyes, and O. B. Widlund, eds., National Autonomous University of Mexico (UNAM), México, 2003, pp. 373–380. 14th International Conference on Domain Decomposition Methods, Cocoyoc, Mexico, January 6–12, 2002.
  2. ↑ C. R. Dohrmann, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25 (2003), pp. 246–258.
  3. ↑ Y. Fragakis and M. Papadrakakis, The mosaic of high performance domain decomposition methods for structural mechanics: Formulation, interrelation and numerical efficiency of primal and dual methods, Comput. Methods Appl. Mech. Engrg., 192 (2003), pp. 3799–3830.
  4. ↑ C. Farhat, M. Lesoinne, P. LeTallec, K. Pierson, and D. Rixen, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the two-level FETI method, Internat. J. Numer. Methods Engrg., 50 (2001), pp. 1523–1544.
  5. ↑ C. Farhat, M. Lesoinne, and K. Pierson, A scalable dual-primal domain decomposition method, Numer. Linear Algebra Appl., 7 (2000), pp. 687–714. Preconditioning techniques for large sparse matrix problems in industrial applications (Minneapolis, MN, 1999).
  6. ↑ J. Mandel and B. Sousedík, BDDC and FETI-DP under minimalist assumptions, Computing, 81 (2007), pp. 269–280.
  7. ↑ 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.
  8. ↑ J. Mandel, Balancing domain decomposition, Comm. Numer. Methods Engrg., 9 (1993), pp. 233–241.
  9. ↑ J. Mandel, C. R. Dohrmann, and R. Tezaur, An algebraic theory for primal and dual substructuring methods by constraints, Appl. Numer. Math., 54 (2005), pp. 167–193.
  10. ↑ J. Li and O. B. Widlund, FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg., 66 (2006), pp. 250–271.
  11. ↑ S. C. Brenner and L.-Y. Sung, BDDC and FETI-DP without matrices or vectors, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1429–1435.
  12. ↑ Le Tallec, Patrick; Mandel, Jan; Vidrascu, Marina, A Neumann-Neumann domain decomposition algorithm for solving plate and shell problems. SIAM J. Numer. Anal. 35 (1998), no. 2, 836–867
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.