Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

MULTISCALE MODEL. SIMUL. c© 2015 Society for Industrial and Applied Mathematics

Vol. 13, No. 2, pp. 571–593

A BDDC ALGORITHM WITH ENRICHED COARSE SPACES FOR

TWO-DIMENSIONAL ELLIPTIC PROBLEMS WITH OSCILLATORY

AND HIGH CONTRAST COEFFICIENTS∗

HYEA HYUN KIM† AND ERIC T. CHUNG‡

Abstract. A balancing domain decomposition by constraints (BDDC) algorithm with enriched coarse spaces is developed and analyzed for two-dimensional elliptic problems with oscillatory and high contrast coefficients. To obtain a robust algorithm based on the classical BDDC framework for conforming finite element methods, a set of enriched primal unknowns is constructed. The enriched component of the primal unknowns is chosen to reflect the local structures of the coefficient by solving two types of generalized eigenvalue problems. These problems are solved locally for every two adjacent subdomains, so that the computations of the enriched primal unknowns are very efficient. Given a tolerance, dominant eigenfunctions with eigenvalues larger than this tolerance are precomputed and used to form coarse basis functions. The resulting condition number by using this enriched coarse space is proved to be bounded above by this tolerance and the maximum number of edges per subdomain, independent of the contrast of the given coefficient. Furthermore, numerical results are presented for various model problems and various choices of primal unknowns to show the performance of the proposed algorithm.

Key words. BDDC, enriched coarse space, high contrast

AMS subject classifications. 65F10, 65N30, 65N55

DOI. 10.1137/140970598 1. Introduction. A balancing domain decomposition by constraints (BDDC) algorithm with adaptively enriched primal unknowns is developed and analyzed for a class of two-dimensional elliptic problems with oscillatory and high contrast coefficients. It is well known that the standard BDDC algorithm [7, 21] requires a strong assumption on coefficients of the model problem related to the subdomain partition to achieve a good performance. In the works by Pechstein and Scheichl [29, 27, 28] and Pechstein [26], a bound for the condition number of finite element tearing and interconnecting (FETI) algorithms has been analyzed, based on a weighted-Poincare´ inequality [30]. However, the condition number bound depends on the coefficient variations near subdomain interfaces. A similar result is also proved for the dual-primal finite element tearing and interconnecting (FETI-DP) and BDDC algorithms for the linear elasticity problem; see the results of Gippert, Klawonn, and Rheinbach [13]. To enhance the robustness of domain decomposition algorithms for problems with highly varying coefficients, additional primal unknowns are necessary. In [11, 12, 32, 10], the use of such additional primal unknowns is introduced and analyzed for two-level

Schwarz methods. The use of additional primal unknowns for BDDC and FETI algorithms has also been considered in [22, 23, 16, 24, 33, 34, 18, 17].

In Klawonn et al. [16] and Klawonn, Radtke, and Rheinbach [18, 17], an adaptive ∗Received by the editors May 27, 2014; accepted for publication (in revised form) April 15, 2015; published electronically May 27, 2015. http://www.siam.org/journals/mms/13-2/97059.html †Department of Applied Mathematics, Kyung Hee University, Yongin, 446-701, Korea (hhkim@ khu.ac.kr, hyeahyun@gmail.com). This author’s work was supported by the National Research Foundation of Korea (NRF) under a grant funded by the Korean government (NRF-2014R1A1A3052427). ‡Department of Mathematics, The Chinese University of Hong Kong (CUHK), Hong Kong SAR (tschung@math.cuhk.edu.hk). This author’s work was supported by the Hong Kong RGC General

Research Fund (project 400813). 571

D ow nl oa de d 09 /2 6/ 15 to 1 28 .1 78 .1 31 .1 13 . R ed ist rib ut io n su bje ct to

SIA

M lic en se or co py rig ht; se e h ttp ://w ww .si am .or g/j ou rna ls/ ojs a.p hp

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 572 HYEA HYUN KIM AND ERIC T. CHUNG coarse space is introduced for FETI-DP and BDDC methods. The space is obtained by solving a generalized eigenvalue problem. The goal of their approach is to minimize the constant arising in the Poincare´ inequality, which is essential in the proof of condition number bounds. Thus, in the regions where these Poincare´ constants are large, generalized eigenvalue problems are solved and certain dominant eigenvectors are included in the coarse space. One key feature is that the generalized eigenvalue problems are defined with respect to edges of subdomains, using the edge Schur complements and mass matrices. In addition, an estimate for the condition number is obtained.

However, the bound depends on a certain parameter related to an assumption on the coefficient variation near subdomain interfaces.

In Spillane et al. [33], a class of coarse spaces is also introduced for FETI algorithms. To construct this coarse space, an eigenvalue problem is solved for each subdomain, and dominant eigenfunctions are used to form coarse basis functions.

Contrary to [16], their eigenvalue problem is defined using the subdomain stiffness matrix and a global FETI Dirichlet preconditioner for the Lagrange multiplier. Thus, the computations of eigenvectors are more expensive, as they involve some global calculations. Similar to [16], the coarse component in the resulting preconditioner is implemented via deflation. We remark that through the use of a change of basis, the continuity of primal unknowns can be enforced directly by letting those unknowns be single-valued, in the same way that the continuity of vertex unknowns is enforced in the standard BDDC algorithm. We refer the reader to [18], where a similar idea was first applied to incorporate the local eigenvectors to the coarse problem in the BDDC algorithm.

Our work is motivated by the constraint and weight selection algorithms for