BDDC

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

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

History

BDDC was introduced by Dohrmann C. R. Dohrmann, "A preconditioner for substructuring based on constrained energy minimization", SIAM J. Sci. Comput., 25 (2003), pp. 246--258.

] as a simpler primal alternative to the FETI-DP domain decomposition method by Farhat et al. 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.

] 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).

] . The name of the method was coined by Mandel and Dohrmann, 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.

] because it can be understood as further development of the BDD (balancing domain decomposition) method. J. Mandel, "Balancing domain decomposition", Comm. Numer. Methods Engrg., 9 (1993), pp. 233--241.

] The same method was also proposed independently by Fragakis and Papadrakakis 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.

] under the name P-FETI-DP, and by Cros 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.

] , which, however, was not recognized for some time. See J. Mandel and B. Sousedík, "BDDC and FETI-DP under minimalist assumptions", Computing, 81 (2007), pp. 269--280.] for a proof that these are all actually the same method as BDDC. Mandel, Dohrmann, and Tezaur 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.

] 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 J. Li and O. B. Widlund, "FETI-DP, BDDC, and block Cholesky methods", Internat. J. Numer. Methods Engrg., 66 (2006), pp. 250--271.

] and by Brenner and Sung 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.

] .

External links

* [http://www.esi-topics.com/fbp/2007/june07-Mandel_Dohrmann_Tezaur.html Authors' comments] to the "Fast Breaking Highly Cited paper" , ESI Special Topics, June 2007

* [http://www.esi-topics.com/fbp/2007/june07-Widlund_Li.html Authors' comments] to the "Fast Breaking Highly Cited paper" , ESI Special Topics, June 2007

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • FETI-DP — The FETI DP method is a domain decomposition method by Charbel Farhat and others, 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 ,… …   Wikipedia

  • Domain decomposition methods — Domain dec …   Wikipedia

  • Port Hueneme, California — Infobox Settlement official name = Port Hueneme, California other name = native name = nickname = settlement type = City motto = imagesize = image caption = flag size = image seal size = image shield = shield size = image blank emblem = blank… …   Wikipedia

  • Bristol, Connecticut —   City   Flag …   Wikipedia

  • Spectral method — Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain Dynamical Systems, often involving the use of the Fast Fourier Transform. Where applicable, spectral methods have… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Numerical partial differential equations — is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs). Numerical techniques for solving PDEs include the following: The finite difference method, in which functions are represented by… …   Wikipedia

  • Multigrid method — Multigrid (MG) methods in numerical analysis are a group of algorithms for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in (but not… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Crank–Nicolson method — In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations.[1] It is a second order method in time, implicit in time, and is numerically …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”