BDDC Deluxe for Isogeometric Analysis

Abstract

The main goal of this paper is to design, analyze, and test a BDDC (Balancing Domain Decomposition by Constraints, see [12, 23]) preconditioner for Isogeometric Analysis (IGA), based on a novel type of interface averaging, which we will denote by deluxe scaling, with either full or reduced set of primal constraints. IGA is an innovative numerical methodology, introduced in [17] and first analyzed in [1], where the geometry description of the PDE domain is adopted from a Computer Aided Design (CAD) parametrization usually based on Non-Uniform Rational B-Splines (NURBS) and the same NURBS basis functions are also used as the PDEs discrete basis, following an isoparametric paradigm; see the monograph [10]. Recent works on IGA preconditioners have focused on overlapping Schwarz preconditioners [3, 5, 7, 9], multigrid methods [16], and non-overlapping preconditioners [4, 8, 20].

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The main goal of this paper is to design, analyze, and test a BDDC (Balancing Domain Decomposition by Constraints, see [12, 23]) preconditioner for Isogeometric Analysis (IGA), based on a novel type of interface averaging, which we will denote by deluxe scaling, with either full or reduced set of primal constraints. IGA is an innovative numerical methodology, introduced in [17] and first analyzed in [1], where the geometry description of the PDE domain is adopted from a Computer Aided Design (CAD) parametrization usually based on Non-Uniform Rational B-Splines (NURBS) and the same NURBS basis functions are also used as the PDEs discrete basis, following an isoparametric paradigm; see the monograph [10]. Recent works on IGA preconditioners have focused on overlapping Schwarz preconditioners [3, 5, 7, 9], multigrid methods [16], and non-overlapping preconditioners [4, 8, 20].

Deluxe scaling was recently introduced by Dohrmann and Widlund in a study of H(curl) problems; see [14, 15, 29] and also [25] for its application to problems in H(div) and [21] for Reissner–Mindlin plates. In our previous work on isogeometric BDDC [4], standard BDDC scalings were employed with averaging weights built directly from sone representative values of the elliptic coefficients in each subdomain (ρ-scaling) or from the values of the diagonal elements of local and global stiffness matrices (stiffness scaling). The novel deluxe scaling, originally developed to deal with elliptic problems with more than one variable coefficient, is instead based on solving local problems built from local Schur complements associated with sets of what are known as the dual variables. This new scaling turns out to be much more powerful than the standard ρ- and stiffness scalings in the present context, even for scalar elliptic problems with one variable coefficient. A novel adaptive strategy to select a reduced set of vertex primal constraints is also studied. The main result of our h-analysis shows that the condition number of the resulting deluxe BDDC preconditioner satisfies the same quasi-optimal polylogarithmic bound in the ratio H∕h of subdomain to element diameters, as in [4], and that this bound is independent of the number of subdomains and jumps of the coefficients of the elliptic problem across subdomain interfaces. Moreover, our preliminary 2D numerical experiments with deluxe scaling show a remarkable improvement, in particular for increasing polynomial degree p of the isogeometric elements. Numerical tests in 3D can be found in [6].

2 Isogeometric Discretization of Scalar Elliptic Problems

We consider the model elliptic problem on a bounded and connected CAD domain $\varOmega \subset \mathbb{R}^{d}$, d = 2, 3,

$$\displaystyle{ -\nabla \cdot (\rho \nabla u) = f\text{ in }\varOmega,\quad u = 0\text{ on }\partial \varOmega, }$$

(1)

where ρ is a scalar field satisfying $0 <\rho _{min} \leq \rho (x) \leq \rho _{max},\ \forall x \in \varOmega$. For simplicity, we describe our problem and preconditioner in the 2D single-patch case. Comments on the 3D extension can be found at the end of Sect. 3, and comments on the multi-patch extension can be found in [6]. We discretize (1) with IGA based on B-splines and NURBS basis functions. The bivariate B-spline discrete space is defined by

$$\displaystyle{ \hat{\mathcal{S}}_{h}:= \text{span}\{B_{i,j}^{p,q}(\xi,\eta ),\ i = 1,\ldots,n,\,j = 1,\ldots,m\}, }$$

(2)

where the bivariate B-spline basis functions $B_{i,j}^{p,q}(\xi,\eta ) = N_{i}^{p}(\xi )\:M_{j}^{q}(\eta )$ are defined by tensor products of 1D B-splines functions $N_{i}^{p}(\xi )$ and $M_{j}^{q}(\eta )$ of degree p and q, respectively (in our numerical experiments, we will only consider the case p = q). Analogously, the NURBS space is the span of NURBS basis functions defined in 1D by

$$\displaystyle{ R_{i}^{p}(\xi ):= \frac{N_{i}^{p}(\xi )\omega _{ i}} {\sum _{\hat{\imath }=1}^{n}N_{\hat{\imath }}^{p}(\xi )\omega _{\,\hat{\imath }}} = \frac{N_{i}^{p}(\xi )\omega _{i}} {w(\xi )}, }$$

(3)

with the weight function $w(\xi ):=\sum _{ \hat{\imath }=1}^{n}N_{\hat{\imath }}^{p}(\xi )\omega _{\,\hat{\imath }} \in \hat{\mathcal{S}}_{h}$, and in 2D by

$$\displaystyle{ R_{i,j}^{p,q}(\xi,\eta ):= \frac{B_{i,j}^{p,q}(\xi,\eta )\omega _{ i,j}} {\sum _{\hat{\imath }=1}^{n}\sum _{\hat{j}=1}^{m}B_{\hat{\imath },\hat{j}}^{p,q}(\xi,\eta )\omega _{\,\hat{\imath },\hat{j}}} = \frac{B_{i,j}^{p,q}(\xi,\eta )\omega _{i,j}} {w(\xi,\eta )}, }$$

(4)

where $w(\xi,\eta )$ is the weight function and $\omega _{i,j} = (\mathbf{C}_{i,j}^{\omega })_{3}$ the positive weights associated with a n × m net of control points C _i, j . The discrete space of NURBS functions on the domain Ω is defined as the span of the push-forward of the NURBS basis functions (4) (see, e.g., [17])

$$\displaystyle{ \mathcal{N}_{h}:= \text{span}\{R_{i,j}^{p,q} \circ \mathbf{F}^{-1},\text{ with }i = 1,\ldots,n;j = 1,\ldots,m\}, }$$

(5)

with $\mathbf{F}:\hat{\varOmega }\rightarrow \varOmega$ the geometrical map between parameter and physical spaces defined by $\mathbf{F}(\xi,\eta ) =\sum _{ i=1}^{n}\sum _{j=1}^{m}R_{i,j}^{p,q}(\xi,\eta )\mathbf{C}_{i,j}$.

For simplicity, we will consider the case with a Dirichlet boundary condition imposed on all of ∂ Ω; we can then define the spline space in the parameter space and the NURBS space in physical space, respectively, as

$$\displaystyle{\hat{V }_{h}:= [\hat{\mathcal{S}}_{h} \cap H_{0}^{1}(\hat{\varOmega })]^{2} = [\text{span}\{B_{ i,j}^{p,q}(\xi,\eta ),\ i = 2,\ldots,n - 1,\,j = 2,\ldots,m - 1\}]^{2},}$$

$$\displaystyle{ V _{h}:= [\mathcal{N}_{h}\cap H_{0}^{1}(\varOmega )]^{2} = [\text{span}\{R_{ i,j}^{p,q}\circ \mathbf{F}^{-1},\text{ with }i = 2,\ldots,n-1;\ j = 2,\ldots,m-1\}]^{2}. }$$

The IGA formulation of problem (1) then reads:

$$\displaystyle{ \left \{\begin{array}{rl} &\mbox{ Find $u_{h} \in V _{h}$ such that:} \\ &a(u_{h},v_{h}) =<f,v_{h}> \qquad \forall v \in V _{h},\end{array} \right. }$$

(6)

with the bilinear form $a(u_{h},v_{h}) =\int _{\varOmega }\rho \nabla u_{h}\nabla v_{h}dx$.

3 BDDC Preconditioners

When using iterative substructuring methods, such as BDDC, we first reduce the problem to one on the interface by implicitly eliminating the interior degrees of freedom, a process known as static condensation; see, e.g., Toselli and Widlund [28, Ch. 4].

Knots and Subdomain Decomposition A decomposition is first built for the underlying space of spline functions in the parametric space, and is then easily extended to the NURBS space in the physical domain. From the full set of knots, $\{\xi _{1} = 0,\ldots,\xi _{n+p+1} = 1\},$ we select a subset $\{\xi _{i_{k}},k = 1,\ldots,N + 1\}$ of non-repeated knots with $\xi _{i_{1}} = 0,\xi _{i_{N+1}} = 1$. The interface knots are given by $\xi _{i_{k}}$ for k = 2, . . , N and they define a decomposition of the closure of the reference interval into subdomains

$$\displaystyle{\overline{\big(\hat{I}\big)} = [0,1] = \overline{\Big(\bigcup _{k=1,..,N}\hat{I}_{k}\Big)},\ \mbox{ with }\ \hat{I}_{k} = (\xi _{i_{k}},\xi _{i_{k+1}}),}$$

that we assume to have similar lengths $H_{k}:= \text{diam}(\hat{I}_{k}) \approx H$. In more dimensions, we just use tensor products. Thus, in two dimension, we define the subdomains by

$$\displaystyle{ \hat{I}_{k} = (\xi _{i_{k}},\xi _{i_{k+1}}),\quad \hat{I}_{l} = (\eta _{j_{l}},\eta _{j_{l+1}}),\quad \hat{\varOmega }_{kl} =\hat{ I}_{k} \times \hat{ I}_{l},\quad 1 \leq k \leq N_{1},\ 1 \leq l \leq N_{2}. }$$

(7)

For simplicity, we reindex the subdomains using only one index to obtain the decomposition of our domain $\overline{\hat{\varOmega }} =\bigcup _{k=1,..,K}\overline{\hat{\varOmega }}_{k},$ into $K = N_{1}N_{2}$ subdomains. Throughout this paper, we assume that both the subdomains and elements defined by the coarse and full sets of knot vectors are shape regular and with quasi-uniform characteristic diameters H and h, respectively.

The Schur Complement System As in classical iterative substructuring, we reduce the problem to one on the interface $\varGamma:=\Big (\bigcup _{k=1}^{K}\partial \hat{\varOmega }_{k}\Big)\setminus \partial \hat{\varOmega }$ by static condensation, i.e., by eliminating the interior degrees of freedom associated with the basis functions with support in each subdomain. The resulting Schur complement for $\hat{\varOmega }_{k}$ and its local interface $\varGamma _{k}:= \partial \hat{\varOmega }_{k}\setminus \partial \hat{\varOmega }$ will be denoted by S ^(k). In the sequel, we will use the following sets of indices:

$$\displaystyle\begin{array}{rcl} \varTheta _{\varOmega }& =& \{(i,j) \in \mathbb{N}^{2}:\ 2 \leq i \leq n - 1,2 \leq j \leq m - 1\}, {}\\ \varTheta _{\varGamma }& =& \{(i,j) \in \varTheta _{\varOmega }:\ \mbox{ supp}(B_{i,j}^{p,q}) \cap \varGamma \neq \emptyset \}. {}\\ \end{array}$$

We note that $\varTheta _{\varGamma }$ consists of indices associated with a “fat” interface that typically consists of several layers of knots associated with the basis functions with support intersecting two or more subdomains, see e.g. Fig. 1. The discrete interface and local spaces are defined as

$$\displaystyle{ \hat{V }_{\varGamma }:= \mbox{ span}\{B_{i,j}^{p,q},(i,j) \in \varTheta _{\varGamma }\},\quad V _{ I}^{(k)}:=\hat{ V }_{ h} \cap H_{0}^{1}(\hat{\varOmega }_{ k}). }$$

(8)

Fig. 1

Schematic illustration in index space of interface equivalence classes in 2D (left) and 3D (right) parametric space with p = 3, κ = 2: fat vertices, consisting of (κ + 1)² knots in 2D and (κ + 1)³ in 3D; fat edges (without vertices), consisting of (κ + 1) “slim” edges in 2D and (κ + 1)² in 3D; fat faces (without vertices and edges), consisting of κ + 1 slim faces in 3D

The space $\hat{V }_{h}$ can be decomposed as $\oplus _{k=1}^{K}V _{I}^{(k)} + \mathcal{H}(\hat{V }_{\varGamma })$, where $\mathcal{H}:\hat{ V }_{\varGamma } \rightarrow \hat{ V }_{h},$ is the piece-wise discrete spline harmonic extension operator, which provides the minimal energy extension of values given in $\hat{V }_{\varGamma }$. The interface component of the discrete solution satisfies the Schur complement reduced system

$$\displaystyle{ s(u_{\varGamma },v_{\varGamma }) =<\hat{ f},v_{\varGamma }>,\quad \forall v_{\varGamma } \in \hat{ V }_{\varGamma }, }$$

(9)

with a suitable right-hand side $\hat{f}$ and a Schur complement bilinear form defined by $s(w_{\varGamma },v_{\varGamma }):= a(\mathcal{H}(w_{\varGamma }),\mathcal{H}(v_{\varGamma }))$. For simplicity, in the sequel, we will drop the subscript Γ for functions in $\hat{V }_{\varGamma }$. In matrix form, (9) is the Schur complement system

$$\displaystyle{ \hat{S}_{\varGamma }w =\hat{ f}, }$$

(10)

where $\hat{S}_{\varGamma } = A_{\varGamma \varGamma } - A_{\varGamma I}A_{II}^{-1}A_{\varGamma I}^{T},\ \hat{f} = f_{\varGamma } - A_{\varGamma I}A_{II}^{-1}f_{I},$ are obtained from the original discrete problem by Gaussian elimination after reordering the spline basis functions into sets of interior (subscript I) and interface (subscript Γ) basis functions. The Schur complement system (10) is solved by a Preconditioned Conjugate Gradient (PCG) iteration, where $\hat{S}_{\varGamma }$ is never explicitly formed since the action of $\hat{S}_{\varGamma }$ on a vector is computed by solving Dirichlet problems for individual subdomains and some sparse matrix-vector multiplies, which are also needed when working with the local Schur complements required by the application of the BDDC preconditioner defined below. The preconditioned Schur complement system solved by PCG is then

$$\displaystyle{ M_{\text{ BDDC}}^{-1}\hat{S}_{\varGamma }w = M_{ \text{ BDDC}}^{-1}\hat{\,f}, }$$

(11)

where $M_{\text{ BDDC}}^{-1}$ is the BDDC preconditioner, defined in (18) below using some restriction and scaling operators associated with the following subspace decompositions.

Subspace Decompositions We split the local space V ^(k) defined in (8) into a direct sum of its interior (I) and interface (Γ) subspaces, i.e.

$$\displaystyle{\begin{array}{rll} V ^{(k)} &:= V _{ I}^{(k)} \oplus V _{\varGamma }^{(k)},\ \ \ \ \ \ \mbox{ where} \\ V _{I}^{(k)} &:= \mbox{ span}\{B_{i,j}^{p,q},(i,j) \in \varTheta _{I}^{(k)}\},\ \ \ \ \ \ \ \ V _{\varGamma }^{(k)} &:= \mbox{ span}\{B_{i,j}^{p,q},(i,j) \in \varTheta _{\varGamma }^{(k)}\},\end{array} }$$

which translate in the index sets

$$\displaystyle{\begin{array}{rl} \varTheta _{I}^{(k)} &:=\{ (i,j) \in \varTheta _{\varOmega }:\ \mbox{ supp}(B_{i,j}^{p,q}) \subset \hat{\varOmega }_{k}\}, \\ \varTheta _{\varGamma }^{(k)} &:=\{ (i,j) \in \varTheta _{\varGamma }:\ \mbox{ supp}(B_{i,j}^{p,q}) \cap (\partial \hat{\varOmega }_{k} \cap \varGamma _{k})\neq \emptyset \}, \end{array} }$$

and we define the associated product spaces by

$$\displaystyle{V _{I}:=\prod _{ k=1}^{K}V _{ I}^{(k)},\quad V _{\varGamma }:=\prod _{ k=1}^{K}V _{\varGamma }^{(k)}.}$$

The functions in V _Γ are generally discontinuous (multi-valued) across Γ, while our isogeometric approximations belong to $\hat{V }_{\varGamma }$, the subspace of V _Γ of functions continuous (single-valued) across Γ. We will select some interface basis functions as primal (subscript Π), that will be made continuous across the interface and will be subassembled between their supporting elements, and we will call dual (subscript Δ) the remaining interface degrees of freedom that can be discontinuous across the interface and which vanish at the primal degrees of freedom. This splitting allows us to decompose each local interface space into primal and dual subspaces $V _{\varGamma }^{(k)} = V _{\varPi }^{(k)}\bigoplus V _{\varDelta }^{(k)}$, and we can define the associated product spaces by

$$\displaystyle{V _{\varDelta }:=\prod _{ k=1}^{K}V _{\varDelta }^{(k)},\quad V _{\varPi }:=\prod _{ k=1}^{K}V _{\varPi }^{(k)}.}$$

We also need an intermediate subspace $\tilde{V }_{\varGamma } \subset V _{\varGamma }$ of partially continuous basis functions

$$\displaystyle{\tilde{V }_{\varGamma }:= V _{\varDelta }\bigoplus \hat{V }_{\varPi },}$$

where the product space V _Δ has been defined above and $\hat{V }_{\varPi }$ is a global subspace of the selected primal variables.

For two-dimensional problems, we will consider the primal space $\hat{V }_{\varPi }^{C}$ consisting of vertex basis functions with indices belonging to

$$\displaystyle{ \varTheta _{\text{C}} =\{ (i,j,k) \in \varTheta _{\varGamma }:\ \mbox{ supp}(B_{i,j,k}^{p,q,r}) \cap \text{C}\neq \emptyset \}. }$$

(12)

In order to define our preconditioners, we will need the following restriction and interpolation operators represented by matrices with {0, 1} elements

$$\displaystyle{ \begin{array}{lll} \tilde{R}_{\varGamma \varDelta }:\tilde{ V }_{\varGamma }\longrightarrow V _{\varDelta }, &\ \tilde{R}_{\varGamma \varPi }:\tilde{ V }_{\varGamma }\longrightarrow \hat{V }_{\varPi }, &\ \hat{R}_{\varPi }:\hat{ V }_{\varGamma }\longrightarrow \hat{V }_{\varPi } \\ R_{\varDelta }^{(k)}: V _{\varDelta }\longrightarrow V _{\varDelta }^{(k)},&\ R_{\varPi }^{(k)}:\hat{ V }_{\varPi }\longrightarrow \hat{V }_{\varPi }^{(k)} & \ \hat{R}_{\varDelta }^{(k)}:\hat{ V }_{\varGamma }\longrightarrow V _{\varDelta }^{(k)}.\end{array} }$$

(13)

For any edge/face $\mathcal{F}$, we will use the symbol $R_{\mathcal{F}}$ to denote a restriction matrix to the (“fat”) set of degrees of freedom associated with $\mathcal{F}$.

Deluxe Scaling We now apply to our isogeometric context the deluxe scaling proposed in [14]. Let Ω _k be any subdomain in the partition, k = 1, 2, …, K. We will indicate by $\varXi _{k}$ the index set of all the Ω _j , $j\not =k,$ that share an edge $\mathcal{F}$ with Ω _k . For regular quadrilateral subdomain partitions in two dimensions, the cardinality of $\varXi _{k}$ is 4 (or less for boundary subdomains).

In BDDC, the average $\bar{w}:= E_{D}w$ of an element in $w \in \tilde{ V }_{\varGamma },$ is computed separately for the sets of interface degrees of freedom of edge and face equivalence classes. We define the deluxe scaling for the class of $\mathcal{F}$ with only two elements, k, j, as for an edge in two dimensions. We define two principal minors, $S_{\mathcal{F}}^{(k)}$ and $S_{\mathcal{F}}^{(j)}$, obtained from S ^(k) and S ^(j) by removing all rows and columns which do not belong to the degrees of freedom which are common to the (fat) boundaries of Ω _k and Ω _j . 

Let $w_{\mathcal{F}}^{(k)}:= R_{\mathcal{F}}w^{(k)}$; the deluxe average across $\mathcal{F}$ is then defined as

$$\displaystyle{ \bar{w}_{\mathcal{F}} =\Big (S_{\mathcal{F}}^{(k)} + S_{ \mathcal{F}}^{(j)}\Big)^{-1}\Big(S_{ \mathcal{F}}^{(k)}w_{ \mathcal{F}}^{(k)} + S_{ \mathcal{F}}^{(j)}w_{ \mathcal{F}}^{(j)}\Big). }$$

(14)

If the Schur complements of an equivalence class have small dimensions, they can be computed explicitly, otherwise the action of $\Big(S_{\mathcal{F}}^{(k)} + S_{\mathcal{F}}^{(j)}\Big)^{-1}$ can be computed by solving a Dirichlet problem on the union of the relevant subdomains with a zero right hand side in the interiors of the subdomains.

Each of the relevant equivalence classes, which involve the subdomain Ω _k , will contribute to the values of $\bar{w}$. Each of these contributions will belong to $\hat{V }_{\varGamma },$ after being extended by zero to $\varGamma \setminus \mathcal{F};$ the resulting element is given by $R_{\mathcal{F}}^{T}\bar{w}_{\mathcal{F}}.$ We then add the contributions from the different equivalence classes to obtain

$$\displaystyle{ \bar{w} = E_{D}w = w_{\varPi } +\sum _{\mathcal{F}}R_{\mathcal{F}}^{T}\bar{w}_{ \mathcal{F}}. }$$

(15)

E _D is a projection and its complementary projection is given by

$$\displaystyle{ P_{D}w:= (I - E_{D})w = w_{\varDelta } -\sum _{\mathcal{F}}R_{\mathcal{F}}^{T}\bar{w}_{ \mathcal{F}}. }$$

(16)

With a small abuse of notation in what follows, we will consider $E_{D}w \in \hat{ V }_{\varGamma }$ also as an element of $\tilde{V }_{\varGamma }$, by the obvious embedding $\hat{V }_{\varGamma } \subset \tilde{ V }_{\varGamma }$. In order to rewrite E _D in matrix form, for each subdomain Ω _k , we define the block-diagonal scaling matrix

$$\displaystyle{D^{(k)} = diag(D_{ \mathcal{F}j_{1}}^{(k)},D_{ \mathcal{F}j_{2}}^{(k)},\ldots,D_{ \mathcal{F}j_{k}}^{(k)}),}$$

where $j_{1},j_{2},\ldots,j_{k} \in \varXi _{k}$ and the diagonal blocks are given by the deluxe scaling $D_{\mathcal{F}}^{(k)}:=\Big (S_{\mathcal{F}}^{(k)} + S_{\mathcal{F}}^{(j)}\Big)^{-1}S_{\mathcal{F}}^{(k)}$. We can now extend the operators defined in (13) and define the scaled local operators by $R_{D,\varGamma }^{(k)}:= D^{(k)}R_{\varGamma }^{(k)}$, $\tilde{R}_{D,\varDelta }^{(k)}:= R_{\varGamma,\varDelta }^{(k)}R_{D,\varGamma }^{(k)}$ and the global scaled operator

$$\displaystyle{ \tilde{R}_{D,\varGamma }:= \mbox{ the direct sum }\hat{R}_{\varPi } \oplus _{k=1}^{K}\tilde{R}_{ D,\varDelta }^{(k)}, }$$

(17)

so that the averaging operator is $E_{D} =\tilde{ R}_{\varGamma }\tilde{R}_{D,\varGamma }^{T}$, where $\tilde{R}_{\varGamma }:=\hat{ R}_{\varPi } \oplus _{k=1}^{K}\tilde{R}_{\varDelta }^{(k)}.$

The BDDC Preconditioner We denote by A ^(k) the local stiffness matrix restricted to subdomain $\bar{\varOmega }_{k}$. By partitioning the local degrees of freedom into those in the interior (I) and those on the interface (Γ), as before, and by further partitioning the latter into dual (Δ) and primal (Π) degrees of freedom, then A ^(k) can be written as

$$\displaystyle{A^{(k)} = \left [\begin{array}{cc} A_{II}^{(k)} & A_{\varGamma I}^{(k)^{T} } \\ A_{\varGamma I}^{(k)} & A_{\varGamma \varGamma }^{(k)}\\ \end{array} \right ] = \left [\begin{array}{ccc} A_{II}^{(k)} & A_{\varDelta I}^{(k)^{T} } & A_{\varPi I}^{(k)^{T} } \\ A_{\varDelta I}^{(k)} & A_{\varDelta \varDelta }^{(k)} & A_{\varPi \varDelta }^{(k)^{T} } \\ A_{\varPi I}^{(k)} & A_{\varPi \varDelta }^{(k)} & A_{\varPi \varPi }^{(k)}\\ \end{array} \right ].}$$

Using the scaled restriction matrices defined in (13) and (17), the BDDC preconditioner can be written as

$$\displaystyle{ M_{\text{ BDDC}}^{-1} =\tilde{ R}_{ D,\varGamma }^{T}\tilde{S}_{\varGamma }^{-1}\tilde{R}_{ D,\varGamma },\ \ \ \ \ \mbox{ where} }$$

(18)

$$\displaystyle{ \tilde{S}_{\varGamma }^{-1} =\tilde{ R}_{\varGamma \varDelta }^{T}\left (\sum _{ k=1}^{K}\left [\begin{array}{cc} 0&R_{ \varDelta }^{(k)^{T} }\\ \end{array} \right ]\left [\begin{array}{cc} A_{II}^{(k)} & A_{\varDelta I}^{(k)^{T} } \\ A_{\varDelta I}^{(k)} & A_{\varDelta \varDelta }^{(k)}\\ \end{array} \right ]^{-1}\left [\begin{array}{c} 0 \\ R_{\varDelta }^{(k)}\\ \end{array} \right ]\right )\tilde{R}_{\varGamma \varDelta }+\varPhi S_{\varPi \varPi }^{-1}\varPhi ^{T}. }$$

(19)

Here S _{Π Π} is the BDDC coarse matrix and Φ is a matrix mapping primal degrees of freedom to interface variables, see e.g. [2, 22]. Our main theorem is the following (see [6] for a proof and more complete details).

Theorem 1

Consider the model problem ( 1 ) in two dimensions and let the primal set be given by the subdomain corner set $\hat{V }_{\varPi }^{C}$ defined in ( 12 ). Then the condition number of the preconditioned operator is bounded by

$$\displaystyle{\mathrm{cond}\Big(M_{BDDC}^{-1}\hat{S}_{\varGamma }\Big) \leq C(1 +\log (H/h))^{2},}$$

with C > 0 independent of h,H and the jumps of the coefficient ρ.

Comments on the Three-Dimensional Case The choice of primal degrees of freedom is fundamental for the construction of efficient BDDC preconditioners. The space $\hat{V }_{\varPi }^{C}$ is not sufficient to obtain scalable and fast preconditioners in three dimensions. In three dimensions, we can define an additional index set associated with fat edges

$$\displaystyle{\varTheta _{\text{E}} =\{ (i,j,k) \in \varTheta _{\varGamma }/\varTheta _{C}:\ \mbox{ supp}(B_{i,j,k}^{p,q,r}) \cap \text{E}\neq \emptyset \},}$$

and enrich the primal space with averages computed for each slim edge parallel to the subdomain edge (see Fig. 1). Three-dimensional numerical results (see [6]) show faster rates of convergence when considering such an enriched coarse space: in particular, the addition of edge slim averages is sufficient to obtain quasi-optimality and scalability as is the case with standard FEM discretizations. The deluxe convergence rate for increasing p seems to be orders of magnitude better than that of BDDC with stiffness scaling, but not as insensitive to p as in the 2D results of Table 1 in the next section.

Table 1 BDDC deluxe dependence on p in the 2D quarter-ring domain: condition number cond and iteration counts n_it as a function of the NURBS polynomial degree p. Fixed h = 1∕64,  K = 4 × 4,  κ = p − 1 (top), κ = 2 (bottom)

Adaptive Choice of Reduced Sets of Primal Constraints In recent years, a number of people have investigated different adaptive choices of primal constraints in BDDC and FETI-DP methods, see e.g. [13, 18, 19, 24, 26, 27]. Most of these works focus on the adaptive selection of 2D edge or 3D face constraints, i.e. constraints associated with the interface between two subdomains, by solving some generalized eigenproblems. It is less clear how to extend such techniques to equivalence classes shared by more than two subdomains, such as 2D or 3D vertices and 3D edges. Here, inspired by the techniques of [13], we propose an adaptive selection of 2D primal vertices, driven by the desire to reduce the expensive fat vertex primal constrains used in the standard or deluxe BDDC method.

Let Ω _k be any subdomain in the partition, k = 1, 2, …, K and consider the associated local Schur complement S ^(k). Denote by $\mathcal{F}$ one of the equivalence classes (a vertex, edge, or face) and partition the degrees of freedom local to Ω _k into $\mathcal{F}$ and its complement $\mathcal{F}^{{\prime}}$. Then S ^(k) can be partitioned as

$$\displaystyle{ S^{(k)} = \left (\begin{array}{*{10}c} S_{\mathcal{F}\mathcal{F}}^{(k)} & S_{\mathcal{F}\mathcal{F}^{{\prime}}}^{(k)} \\ S_{\mathcal{F}^{{\prime}}\mathcal{F}}^{(k)} & S_{\mathcal{F}^{{\prime}}\mathcal{F}^{{\prime}}}^{(k)} \end{array} \right ). }$$

(20)

For each equivalence class $\mathcal{F}$, define the new Schur complement

$$\displaystyle{ \tilde{S}_{\mathcal{F}\mathcal{F}}^{(k)} = S_{ \mathcal{F}\mathcal{F}}^{(k)} - S_{ \mathcal{F}\mathcal{F}^{{\prime}}}^{(k)}S_{ \mathcal{F}^{{\prime}}\mathcal{F}^{{\prime}}}^{(k)^{-1} }S_{\mathcal{F}^{{\prime}}\mathcal{F}}^{(k)} }$$

(21)

and define the generalize eigenvalue problem

$$\displaystyle{ S_{\mathcal{F}\mathcal{F}}^{(k)}v =\lambda \tilde{ S}_{ \mathcal{F}\mathcal{F}}^{(k)}v. }$$

(22)

Given a threshold $\theta \geq 1$, we select the eigenvectors $\{v_{1},v_{2},\ldots,v_{N_{c}}\}$ associated to the eigenvalues of (22) greater than $\theta$ and we perform a BDDC change of basis in order to make these selected eigenvectors the primal variables.

4 Numerical Results

In this section, we report on numerical experiments with the isogeometric BDDC deluxe preconditioner for two-dimensional elliptic model problems (1), discretized with isogeometric NURBS spaces with a mesh size h, polynomial degree p and regularity κ. The domain is decomposed into K nonoverlapping subdomains of characteristic size H, as described in Sec. 3. The discrete Schur-complement problems are solved by the PCG method with the isogeometric BDDC preconditioner, with a zero initial guess and a stopping criterion of a 10⁻⁶ reduction of the Euclidean norm of the PCG residual. In the tests, we study how the convergence rate of the BDDC preconditioner depends on h, K, p, κ. The 2D tests have been performed with a MATLAB code based on the GeoPDEs library by De Falco et al. [11].

Scalability in K and Quasi-Optimality in H∕h The condition number cond and iteration counts n_it of the BDDC deluxe preconditioner are reported in the table of Fig. 2 for a quarter-ring domain (shown on the left of the table), as a function of the number of subdomains K and mesh size h, for fixed p = 3, κ = 2 (top) or p = 5, κ = 4 (bottom). The results show that the proposed preconditioner is scalable, since moving along the diagonals of each table the condition number appears to be bounded from above by a constant independent of K. The results for higher degree p = 5 and regularity κ = 4 are even better than those for the lower degree case. The BDDC deluxe preconditioner appears to retain a very good performance in spite of the increase of the polynomial degree p, a property that was not always satisfied in [4]. To better understand this issue, we next study the BDDC performance for increasing values of p.

Fig. 2

BDDC deluxe preconditioner for a 2D quarter-ring domain (left): condition number cond and iteration counts n_it as a function of the number of subdomains K and mesh size h. Fixed p = 3, κ = 2 (top), p = 5, κ = 4 (bottom)

Dependence on p In this test, we compare the BDDC deluxe performance as a function of the polynomial degree p and the regularity κ. We recall that our theoretical work is only an h-analysis and does not cover the dependence of the convergence rate on p and κ. The domain considered is the quarter-ring discretized with a mesh size h = 1∕64 and K = 4 × 4 subdomains. The spline degree p varies from 2 to 10 and the regularity is always maximal (κ = p − 1) inside the subdomains, while at the subdomain interface is either maximal (κ = p − 1, top) or low (κ = 2, bottom). The results in Table 1 show that for κ = p − 1 the condition numbers and iteration counts are bounded independently of the degree p and actually improve slightly for increasing p, while for κ = 2 the condition numbers show a very modest sublinear growth with p, with associated iteration counts that are practically constant. This is a remarkable property that is not shared by any other nonoverlapping IGA preconditioner in the (current) literature.

Adaptive Choice of Vertex Primal Constraints Table 2 reports the results with the proposed adaptive choice of primal constraints applied only to the vertex constraints (the edge variables remain dual). We consider both an eigenvalue threshold $\theta = 2$ leading to the minimal choice of N _c  = 1 primal vertex constraint (that turns out to be the average of the fat vertex values) and a lower threshold $\theta = 1.5$ leading to a richer choice of N _c  = 4 primal vertex constraints for each subdomain vertex. In case of variable polynomial degree p, we also consider a very low threshold $\theta = 1.1$ that leads to a richer choice of approximately N _c  = 2p primal constraints for each subdomain vertex. The results in a) show that the BDDC deluxe preconditioner is scalable, since cond and n_it appears to be bounded from above by a constant independent of K, and the results in b) indicate that the preconditioner is quasi-optimal, since cond and n_it appears to grow polylogarithmically in H∕h. The results in c) show that the minimal choice N _c  = 1 does not perform well for increasing p (there is no convergence for p = 6), while with the richer choice corresponding to $\theta = 1.1$ we obtained only a mild performance degradation up to p = 6.

Table 2 Adaptive choice of primal vertex constraints for the BDDC deluxe preconditioner on a square domain, with eigenvalue threshold $\theta$ and associated number N _c of selected primal constraints