|
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. ==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. 〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「BDDC」の詳細全文を読む スポンサード リンク
|