Keywords

1 Introduction

When modeling physical or engineering phenomena one has to numerically solve partial differential equations with highly heterogeneous contrast. The heterogeneity of the media makes many standard numerical methods to work very slowly. Domain Decomposition Methods (DDM), in particular, Schwarz methods, form a class of parallel highly efficient methods for solving a system of equations arising from the standard discretizations of elliptic partial differential equations, e.g., cf. [14] and references therein. In classical overlapping Schwarz method the domain is decomposed into the overlapping subdomains where the local subproblems are solved in the application of the preconditioner. We also usually add a global coarse problem obtaining proper scalability, e.g., cf. [14]. Recently, the research of DDM and in particular Schwarz method extended into to problems with highly heterogeneous coefficients, e.g., cf. [3, 5, 6, 9,10,11, 13]. It is common that the coarse space is built by enriching a small standard coarse space with eigenfunctions of some generalized eigenvalue problems, e.g., cf. [3,4,5, 13]. The resulting methods are robust with respect to the heterogeneity of the coefficients, and quite often are adaptive in a sense that we can construct it automatically by adding those eigenfunctions which are associated with all respective eigenvalues below a preset threshold. The condition bounds of the obtained preconditioned problem depend only on the threshold and are independent of the coefficients.

The goal of this paper is to construct an adaptive coarse space for the standard overlapping Schwarz method with the minimal overlap for the macro finite element reduced Hsieh-Clough-Tocher (RHCT) discretization of the fourth order elliptic problem with highly heterogeneous highly varying coefficients in two dimensions. Then, the preconditioned problem is solved by the Preconditioned Conjugate Gradient Method (PCG), e.g., cf. [7]. The method is based on the abstract Schwarz framework. The coarse space is an algebraic sum of a specially constructed multiscale global space associated with the edges of the subdomains and local edge subspaces formed by eigenfunctions of generalized eigenvalue problems. This work is an extension of the recent results of [5] for the second order elliptic problem to the fourth order problem discretized by the RHCT method.

The obtained estimates are independent of the geometries of the subdomains, and the heterogeneities in the coefficients. The bounds are depended only on the parameters chosen in the eigenvalue problems, i.e. a user has to decide in a pre-computational step how many eigenvectors have to be computed and included in our coarse space construction. It can be done adaptively, i.e., including the eigenfunctions for which the respective eigenvalues are below a preset threshold.

The remainder of this paper is organized as follows, in Sect. 2 we present the RHCT macro finite element discretization. In Sect. 3 our coarse space is constructed. Section 4 contains a description of the overlapping additive Schwarz preconditioner, and in Sect. 5 we briefly discuss some implementation issues.

2 Finite Element Discretization

In this section, we present our model problem and its RHCT macro element discretization.

Let \(\varOmega \) be a convex and polygonal domain in the plane. The differential problem is to find \(u^* \in H^2_0(\varOmega )\) such that

$$\begin{aligned} a(u^*,v)=\int _\varOmega f v \,dx \quad \forall v \in H^2_0(\varOmega ), \end{aligned}$$
(1)

where

$$ f \in L^2(\varOmega ), \qquad $$
$$ H^2_0(\varOmega )=\{u\in H^2(\varOmega ): u=\partial _n u=0 \quad \mathrm {on} \quad \partial \varOmega \}, $$

and

$$\begin{aligned} a(u,v)= \int _\varOmega \beta (x) [ u_{x_1 x_1}v_{x_1 x_1}+ 2\, u_{x_1 x_2} v_{x_1 x_2} +u_{x_2 x_2} v_{x_2 x_2} ] \, dx. \end{aligned}$$
(2)

Here \(\beta \) is a strictly positive bounded function, and \(\partial _n\) is a normal unit derivative. Hence, we can always scale \(\beta \) by its minimal value.

We introduce a quasiuniform triangulation \(T_h=T_h(\varOmega )\) of \(\varOmega \) consisting of triangles, \(h=\max _{\tau \in T_h} \mathrm {diam}(\tau )\) be the parameter of the triangulation, e.g., cf. [1]. Let \(\varOmega _h, \overline{\varOmega }_h, \partial \varOmega _h\) be the sets of vertices or the nodes of \(T_h(\varOmega )\), belonging to \(\varOmega _h, \overline{\varOmega }_h, \partial \varOmega _h\), respectively.

For a two-dimensional multi-index \( \alpha =(\alpha _1,\alpha _2), \) where \(\alpha _1, \alpha _2 \) are nonnegative integers, we define

$$\begin{aligned} |\alpha |=\alpha _1+\alpha _2,\qquad \partial ^{\alpha }= \frac{ \partial ^{|\alpha |}}{\partial x_1^{\alpha _1} \partial x_2^{\alpha _2}}. \end{aligned}$$
Fig. 1.
figure 1

The reduced Hsieh-Clough-Tocher macro element. There are three degrees of freedom at each vertex.

Full size image

Further, we assume that \(\beta \) is piecewise constant over \(T_h\), it may have jumps across the 1D common edges of two neighboring elements in \(T_h\).

The reduced Hsieh-Clough-Tocher (RHCT) macro element space \(V_h\) is defined as follows, e.g., cf. Chap. 7, Sect. 46, p. 285 in [2], (also cf. Fig. 1):

$$\begin{aligned} \begin{array}{rcl} V_h = \{u \in C^1(\varOmega ): u \in P_3(\tau _i),\; \tau _i \in T_h(\varOmega ), \; \mathrm { for} \; \mathrm {triangles} \; \tau _{i},\quad \\ i=1,2,3, \; \mathrm {formed} \; \mathrm {by}\; \mathrm {connecting} \; \mathrm {the} \;\mathrm {vertices} \; \mathrm {of}\quad \\ \mathrm {any} \; \tau \in T_{h}(\varOmega _{k}) \; \mathrm {to}\;\; \mathrm {its}\;\; \mathrm {centroid,} \; \partial _nu_{|e} \in P_1(e) \; \mathrm {for}\quad \\ e~\mathrm {an ~edge ~of}\; \tau \;\mathrm {and} \; u=\partial _n u =0 \; \mathrm {on} \; \partial \varOmega \}. \end{array} \end{aligned}$$
(3)

The degrees of freedom of the RHCT element are given by

$$\begin{aligned} \{ v(p), v_{x_1}(p), v_{x_2}(p)\}, \end{aligned}$$

where p is a vertex of an element, cf. Fig. 1.

The discrete RHCT element problem will then be formulated as follows: find \(u_h \in V_h\) such that

$$\begin{aligned} a(u_h,v)=\int _\varOmega f v \,dx \quad \forall v \in V_h. \end{aligned}$$
(4)

The problem has a unique solution by the Lax-Milgram lemma. By formulating the discrete problem in the standard RHCT nodal basis \(\{\phi _i^\alpha \}_{x_i\in \varOmega _h,|\alpha |\le 1 }\), we get the following system of algebraic equations

$$\begin{aligned} A_h \varvec{u}_h=\varvec{f}_h \end{aligned}$$
(5)

where \(\displaystyle A_h=(a(\phi _i^{\alpha _1},\phi _j^{\alpha _2})\!\!\!\!\mathop {)_{i,j}}_{\;\alpha _1,\alpha _2}\), \(\displaystyle \varvec{f}_h=(f_j^\alpha \mathop {)_{x_j\in \varOmega _h}}_{|\alpha |\le 1}\) with \(f_j=\int _\varOmega f(x)\phi _i^\alpha \,dx\), and \(\varvec{u}_h=(u_i^\alpha )_{i,\alpha }\) with \(u_i^\alpha =\partial ^\alpha u_h(x_i)\). Here \(u_h=\sum _{x_i\in \varOmega _h} \sum _{|\alpha |\le 1} u_i^\alpha \phi _i\). The resulting system is symmetric which is in general very ill-conditioned; any standard iterative method may perform badly due to the ill-conditioning of the system.

In this paper, we present a method for solving such systems using the preconditioned conjugate method (cf. [7]) and propose an overlapping additive Schwarz preconditioner (e.g., cf. [14]). Let assume that there exists a partition of \(\varOmega \) into a collection of disjoint open and connected polygonal substructures \(\varOmega _k\), such that

$$\begin{aligned} \overline{\varOmega }= & {} \bigcup _{k=1}^N\overline{\varOmega }_k. \end{aligned}$$

We need another assumption, namely, let the triangulation \(T_h\) be aligned with the subdomains \(\varOmega _k\), i.e. let any triangle of \(T_h\) be contained in a substructure \(\varOmega _k\). Hence, each subdomain \(\varOmega _k\) inherits the local triangulation \(T_h(\varOmega _k)=\{\tau \in T_h: \tau \subset \varOmega _k\}\). We make an additional assumption that the number of subdomains which share a vertex or an edge of an element of \(T_h\) is bounded by a constant. An important role plays an interface \(\overline{\varGamma }= \sum _{k=1}^N (\overline{\partial \varOmega _k \setminus \partial \varOmega })\).

The non-empty intersection of two subdomains \(\partial \varOmega _i\cap \partial \varOmega _j\) not on \(\partial \varOmega \) is either an 1D edge \(\mathcal {\overline{\mathcal {E}}}_{i j}=\partial \varOmega _i\cap \partial \varOmega _j\), or it is a vertex of \(T_h\). A common vertex of substructures that is NOT on \(\partial \varOmega \) is called a crosspoint. The sum of closed edges of substructures, which are not on \(\partial \varOmega \) equals \(\varGamma \) the interface of this partition. We define local sets of nodal points, \(\varOmega _{k,h}\), \(\mathcal {E}_{k l,h},\overline{\varOmega }_{k,h},\overline{\mathcal {E}}_{k l,h}\) etc., as the sets of vertices of elements of \(T_h\), which are in \(\varOmega _{k}\), \(\mathcal {E}_{k l},\overline{\varOmega }_k,\overline{\mathcal {E}}_{k l}\) etc., respectively.

3 Coarse Space

In this section, we present an adaptive coarse space, which is a space of discrete biharmonic functions, cf. Sect. 3.1 below, consisting of two space components: the multiscale coarse space component and the generalized edge based eigenfunction space component.

3.1 Discrete Biharmonic Extensions

In this section, we define the discrete biharmonic functions. We define the local subspace \(V_h(\varOmega _k)\) as the space of restrictions to \(\overline{\varOmega }_k\), of the space \(V_h\), i.e.,

$$\begin{aligned} V_h(\varOmega _k)=\{u_{|\overline{\varOmega }_k}: u\in V_h\}, \end{aligned}$$

and we let introduce its subspace of functions with zero boundary conditions (in \(H^2_0\) sense), i.e.,

$$\begin{aligned} V_{h,0}(\varOmega _k)=V_h(\varOmega _k)\cap H^2_0(\varOmega _k). \end{aligned}$$

We also need a local bilinear form

$$\begin{aligned} a_k(u,v)= \int _{\varOmega _k} \beta (x) [ u_{x_1 x_1}v_{x_1 x_1}+ 2\, u_{x_1 x_2} v_{x_1 x_2} +u_{x_2 x_2} v_{x_2 x_2} ] \, dx. \end{aligned}$$

Let \(\mathcal {P}_k u\in V_{h,0}(\varOmega _k)\) for any \(u \in V_h(\varOmega _k)\) be the \(a_k\) orthogonal projection onto \(V_{h,0}(\varOmega _k)\), i.e.,

$$\begin{aligned} a_k(\mathcal {P}_k u,v)=a_k(u,v) \qquad \forall v \in V_{h,0}(\varOmega _k). \end{aligned}$$
(6)

Then, let the local discrete biharmonic extension operator

$$\mathcal {H}_k:V_h(\varOmega _k)\rightarrow V_h(\varOmega _k)$$

be defined as

$$\begin{aligned} \mathcal {H}_k u=u -\mathcal {P}_k u, \end{aligned}$$
(7)

or equivalently \(\mathcal {H}_ku\) is the unique solution to the following local problem:

(8)

where \(Tr\, u_k=(u_{k| \partial \varOmega _k}, \nabla u_{k| \partial \varOmega _k} )\) for \(u_k\in V_h(\varOmega _k)\), e.g., cf. [8]. Since it is a discrete case, the boundary conditions are equivalently to the discrete boundary conditions: \(Tr\, \mathcal {H}_k u(x)=Tr\, u (x)\) for all \(x\in \partial \varOmega _{k,h}\). A function \(u \in V_h(\varOmega _k)\) is discrete biharmonic in \(\varOmega _k\) if \(u_{|\overline{\varOmega }_k}=\mathcal {H}_k u \in V_h(\varOmega _k)\). If for \(u\in V_h\) all its restriction to local subdomains are discrete biharmonic, then u is piecewise discrete biharmonic in our partition. Please note, that a discrete biharmonic function in \(V_h(\varOmega _k)\) is uniquely defined by its values of degrees of freedom at the nodal points of \(\partial \varOmega _{k,h}\) and has the following minimizing property:

$$\begin{aligned} a_k(\mathcal {H}_ku,\mathcal {H}_k u)=\min \{\!\!\!&a_k(u,u): \nonumber \\&u\in V_h(\varOmega _k) \,:\, Tr\, u(x) =Tr\, \mathcal {H}_k u(x) \quad x\in \partial \varOmega _k\}. \end{aligned}$$
(9)

3.2 Multiscale Coarse Space Component

Our coarse space comprises two parts, in this section, we define the multiscale component. We need a definition of a patch around an edge \(\mathcal {E}_{kl}\), namely let the patch \(\mathcal {E}_{kl}^\delta \) an open domain which closure is the closed union of all fine triangles of \(T_h(\varOmega _k)\) and \(T_h(\varOmega _l)\) such that either one of its open edges or vertices are contained in \(\mathcal {E}_{kl}\). We can naturally split the patch into two disjoint parts:

$$\begin{aligned} \overline{\mathcal {E}}_{kl}^\delta =\overline{\mathcal {E}}_{kl}^{\delta ,k}\cup \overline{\mathcal {E}}_{kl}^{\delta ,l}, \end{aligned}$$

where \(\mathcal {E}_{kl}^{\delta ,s}=\mathcal {E}_{kl}^\delta \cap \varOmega _s\), \(s=k,l.\), cf. Fig. 2.

Fig. 2.
figure 2

The patch \(\mathcal {E}_{kl}^\delta \) and its two subpatches related to \(\mathcal {E}_{kl}\) the common edge to subdomains \(\varOmega _k\) and \(\varOmega _l\).

Full size image

The sum of all patches contained in \(\varOmega _k\) form a boundary layer interior to \(\varOmega \) defined as

$$\begin{aligned} \overline{\varOmega }_k^\delta = \bigcup _{\varGamma _{k l}\subset \partial \varOmega _k\setminus \partial \varOmega } \overline{\mathcal {E}}_{kl}^{\delta ,k}. \end{aligned}$$

For simplicity of presentation we assume that all patches \(\mathcal {E}_{kl}^{\delta ,k}\) for a substructure \(\varOmega _k\), are disjoint.

Let \(V_h(\mathcal {E}_{k l}^\delta )\) be the space of restrictions of functions from \(V_h\) to \(\mathcal {E}_{k l}^\delta \)

$$\begin{aligned} V_h(\mathcal {E}_{k l}^\delta )=\{u_{|\mathcal {E}_{k l}^\delta }: u\in V_h \} \end{aligned}$$

and its subspace \(V_{h,0}(\mathcal {E}_{k l}^\delta )\) with zero boundary condition, i.e.,

$$\begin{aligned} V_{h,0}(\mathcal {E}_{k l}^\delta )= V_h(\mathcal {E}_{k l}^\delta )\cap H^2_0(\mathcal {E}_{k l}^\delta ). \end{aligned}$$
(10)

A function in this space is uniquely defined by the values of three degrees of freedom at all nodes in \(\mathcal {E}_{k l,h}\).

Note that \(Tr\, u\) onto each fine edge of \(\mathcal {E}_{k l}\) can be represented as \((u,\partial _s u,\partial _n u)\), where u is a \(C^1\) piecewise cubic function on the inherited 1D triangulation of this edge, \(\partial _s u\) is its derivative, and \(\partial _n u\) is a continuous piecewise linear function. We also define two bilinear forms related to an edge \(\mathcal {E}_{kl}\), the first one being the restriction of the form a(u, v), cf. (2), to the patch, namely,

$$\begin{aligned} a_{k l} (u,v)=\int _{\mathcal {E}_{k l}} \overline{\beta }[ \partial _{ss} u\, \partial _{ss}v +\partial _{ns}u \, \partial _{ns} v \,ds] \end{aligned}$$
(11)

where \(\partial _{ss} u\) is the weak second order tangential derivative of the trace of u onto the edge \(\mathcal {E}_{kl}\), and \(\partial _{ns} u\) is the weak tangential derivative of the trace of the normal derivative on this edge. Here \(\overline{\beta }\) is constant over each fine edge \(e \subset \mathcal {E}_{k l}\) being the common edge of fine 2D triangles \(\tau _+\in T_h(\varOmega _k)\) and \(\tau _-\in T_h(\varOmega _l)\). Let it be defined as \(\max (\beta _{|\tau _+},\beta _{|\tau _-})\).

The second patch bilinear form is the scaled weighted \(L^2\) over the patch, i.e.,

$$\begin{aligned} b_{k l}(u,v)=h^{-3}\int _{\mathcal {E}_{k l}^\delta } \beta u v\,d x. \end{aligned}$$
(12)

We have a simple proposition.

Proposition 1

The both forms \(a_{k l}(u,v)\) and \(b_{k l}(u,v)\) are symmetric and positive definite over \(V_{h,0}(\mathcal {E}_{k l}^\delta ).\)

We now introduce the multiscale coarse space.

Let a subspace \(V_{ms}\subset V_h\) be formed by all discrete biharmonic functions in the sense of (8), which satisfies the following variational equality on each patch \(\mathcal {E}_{k l}^\delta \):

$$\begin{aligned} a_{k l} (\hat{u}_{k l},v)=0 \quad \forall v\in V_{h,0}(\mathcal {E}_{k l}^\delta ), \end{aligned}$$
(13)

where \(\hat{u}_{kl}\in V_{h,0}(\mathcal {E}_{k l}^\delta )\) satisfies \(\partial ^\alpha \hat{u}(x)=\partial ^\alpha u(x)\) \(x\in \overline{\mathcal {E}}_{k l,h}\).

We have a straightforward proposition.

Proposition 2

A function \(u\in V_{ms}\) is uniquely defined by its dofs at all cross-points.

Proof

Since \(u\in V_{ms}\) is discrete biharmonic, it is defined by the values of its dofs at interface i.e., at crosspoints and in \(\mathcal {E}_{k l,h}\) for all interfaces. Thus, it is enough to show that all dofs of u are uniquely defined on all interfaces \(\mathcal {E}_{k l}\). Let define the function \(\hat{u}_{k l}\in V_h(\mathcal {E}_{k l})\) such that it satisfies \(\partial ^\alpha \hat{u}_{k l}(x)=\partial ^\alpha u(x)\) for \(|\alpha |\le 1\) and \(x \in \partial \mathcal {E}_{k l}\), \(\partial ^\alpha \hat{u}_{k l}(x)=0\) for all remaining fine vertices on the boundary of the patch \(\mathcal {E}_{k l}\) and:

$$\begin{aligned} a_{k l} (\hat{u}_{k l},v)=0 \quad \forall v\in V_{h,0}(\mathcal {E}_{k l}^\delta ). \end{aligned}$$

We can represent \(\hat{u}_{kl}=w_1+w_0\) with \(w_0\in V_{h,0}(\mathcal {E}_{k l}^\delta )\). E.g., we can take \(w_1\) with the DOFs equal to DOFs of \(\hat{u}_{kl}\) on the boundary of the patch, and with zero valued remaining DOFs. Then, the last variational equation is equivalent to: find \(w_0\in V_{h,0}(\mathcal {E}_{k l}^\delta )\) such that

$$\begin{aligned} a_{k l}(w_0,v)=-a_{kl}(w_1,v) \quad \forall v\in V_{h,0}(\mathcal {E}_{k l}^\delta ). \end{aligned}$$

It follows from Proposition 1, that \(w_0\), and thus \(\hat{u}_{k l}\), is uniquely defined. It is clear that all DOFs of \(\hat{u}_{k l}\) and u have the same values at \(\overline{\mathcal {E}}_{k l,h}\), so u is unique.

The values of its DOFs at the nodal points of each face can be computed by solving (13), and then the values of DOFs at the nodal points of each subdomain can be computed by solving (8).

3.3 Generalized Edge Based Eigenfunction Space Component

First we define a generalized eigenproblem of the form: find \((\lambda _j^{k l},\phi _j^{k l})\in \mathbb {R} \times V_{h,0}(\mathcal {E}_{k l}^\delta )\) such that

$$\begin{aligned} a_{k l} (\phi _j^{k l} ,v) = \lambda _j^{k l} b_{k l} (\phi ,v) \qquad \forall v\in V_{h,0}(\mathcal {E}_{k l}^\delta ). \end{aligned}$$
(14)

Proposition 1 yields, that there are real and positive eigenvalues and their respective \(b_{k l}\) - orthonormal eigenvectors satisfying (14), such that

$$\begin{aligned} 0<\lambda _1^{k l}\le \lambda _2^{k l}\le \ldots \le \lambda _M^{k l}, \end{aligned}$$

where M is the dimension of \(V_{h,0}(\mathcal {E}_{k l}^\delta ).\)

For any \(1\le n=n(\mathcal {E}_{k l}) \le M \) we can define the orthogonal projection: \(\pi _n^{k l}:V_{h,0}(\mathcal {E}_{k l}^\delta ) \rightarrow span\{\phi _j^{k l}\}_{j=1}^n \subset V_{h,0}(\mathcal {E}_{k l}^\delta )\) as

$$\begin{aligned} \pi _n^{k l} v= \sum _{j=1}^n b_{k l} (v,\phi _j^{k l})\phi _j^{k l}. \end{aligned}$$
(15)

Then for each eigenvector \(\phi _j^{k l}\), \(1\le j \le n(\mathcal {E}_{k l})\) we define \(\varPhi _j^{k l} \in V_h\) which has DOFs equal to the ones of \(\phi _j^{k l}\) at all nodes on the edge \(\mathcal {E}_{k l}\), zero DOFs on the remaining edges and at all crosspoints, and finally discrete biharmonic inside each subdomain, in the sense of (8), what defines uniquely the values of its DOFs at all interior nodes of the subdomain. Then, the edge terms of the coarse space are introduced as:

$$\begin{aligned} V_{h,n}^{k l}=\mathrm {span}\{\varPhi _j^{k l}\}_{j=1}^{n(\mathcal {E}_{k l})}, \qquad \forall \mathcal {E}_{k l}\subset \varGamma . \end{aligned}$$

The coarse space is defined as

$$\begin{aligned} V_0:=V_{ms} + \sum _{\mathcal {E}_{k l}\subset \varGamma } V_{h,n}^{k l}. \end{aligned}$$
(16)

4 Additive Schwarz Method (ASM) Preconditioner

Our preconditioner is based on the abstract framework of ASM, i.e. is based on a decomposition of the global space \(V_h\) into local subspaces and one global coarse space, equipped into respective symmetric positive definite bilinear forms, e.g., cf. [14]. Here we take only the original form a(u, v), i.e. (2), as the local forms Each local subspace \(V_k\) related to \(\varOmega _k\), is defined as the space formed by all functions \(u\in V_h\) whose DOFs take the value zero at all nodal points that lie outside \(\overline{\varOmega }_k\).

The coarse space \(V_0\) was introduced in the previous section, cf. (16). We get

$$\begin{aligned} V_h=V_0+\sum _{k=1}^N V_k. \end{aligned}$$

Then, we introduce the additive Schwarz operator \(T:V_h\rightarrow V_h\) as

$$\begin{aligned} T=T_0 + \sum _{k=1}^N T_k, \end{aligned}$$

where the coarse space projection operator, \(T_0: V_h\rightarrow V_0\), is defined by

$$\begin{aligned} a(T_0u,v)=a(u,v) \qquad \forall v\in V_0, \end{aligned}$$

and the local subspace projection operators, \(T_k:V_h\rightarrow V_k\), are determined by

$$\begin{aligned} a(T_ku,v)=a(u,v) \qquad \forall v\in V_k, \qquad k=1,\ldots ,N. \end{aligned}$$

The problem (1) is then replaced as the equivalent preconditioned system,

$$\begin{aligned} T u_h=g, \end{aligned}$$
(17)

where

$$ g=g_0+\sum _{k=1}^N g_k $$

with \(g_0=T_0u_h^*\), \(g_k=T_ku_h^*\), \(k=1,\ldots ,N\), and \(u_h^*\) the discrete solution, cf. (4).

Note, that the right hand side vectors, \(g_k, k=0\cdots ,N,\) can be calculated without explicitly knowing the discrete solution, e.g., cf. [12, 14].

4.1 An Estimate of the Condition Number

We present the main result of this paper, namely an estimate of the condition number of the preconditioned system (1).

We have the following theorem:

Theorem 1

There exist positive constants c, C independent of h, \(\beta \), and number of subdomains, such that

$$\begin{aligned} c(\min _{k l} \lambda _{n+1}^{k l} )\, a(u,u) \le a(Tu,u)\le & {} C \, a(u,u) \qquad \forall u \in V_h, \end{aligned}$$

where \( \lambda _{n+1}^{k l}\) and \(n=n(\mathcal {E}_{k l})\) are defined in Sect. 3.3.

The theorem proof uses the abstract ASM framework, e.g., cf. [14], we check the three key assumptions of this framework. The key component is to define a so called stable decomposition which is done with the help of the operators \(\pi _n^{k l}\), cf. (15), and then to utilize its properties.

The number of eigenfunctions needed for the robustness of our method usually corresponds to the number of channels crossing a subdomain interface. This number can be predefined from experience or chosen adaptively by looking at the smallest eigenvalues. Note that the lower bounds in Theorem 1 is dependent on how many eigenvectors of the local face generalized eigenproblem are included in our coarse grid.

5 Implementation Issues

In this section, we briefly discuss the implementation of our ASM preconditioner. For the simplicity of presentation, we use our preconditioner with the Richardson’s iteration. In practice, one uses the preconditioned conjugate gradient iteration (e.g., cf. [7]) for the system (17).

  • Precomputation step. Computing the coarse grid basis. Constructing the coarse space requires the solution of the generalized eigenvalue problem (14) on each subdomain face (interface), the first few eigenfunctions corresponding to the smallest eigenvalues are then included in the coarse space. Prescribing a threshold \(\lambda _0\), and then computing the eigenpairs with eigenvalues smaller than \(\lambda _0\), we can get an automatic way to enrich the coarse space. The simplest way would be to compute a fixed number of eigenpairs, e.g. \(n=5\) or so, this may however not guarantee robustness as the number of channels crossing a face may be much larger.

  • Richardson iteration. The Richardson iteration with the parameter \(\tau \) is defined as follows: starting with any \(u^{(0)}\), iterate until convergence:

    $$\begin{aligned} \begin{array}{rcl} u^{(i+1)}&{}=&{}u^{(i)}+ \tau \, (g-T(u^{(i)})) =u^{(i)}+ \tau \, T(u^*_h - u^{(i)})\\ &{} = &{} u^{(i)}-\tau \,r^{(i)} \end{array}, \quad i\ge 0. \end{aligned}$$

    Computing of \(r^{(i)}=g-T(u^{(i)})\) requires solving the following problems:

    • \(\rhd \) Local subdomain problems:

      Compute \(r_k\in V_k\) \(k=1,\ldots ,N\) by solving the following local problems

      $$\begin{aligned} a(r_k,v)= & {} a(T_k(u^*_h -u^{(i)}),v) =f(v)-a(u^{(i)},v) \qquad \forall v\in V_k. \end{aligned}$$

    • \(\rhd \) Coarse problem:

      Compute \(r_0\in V_0\) such that

      $$\begin{aligned} a(r_0,v)= & {} a(T_0(u^*_h-u^{(i)}),v) = f(v)-a(u^{(i)},v) \qquad \forall v\in V_0, \end{aligned}$$

    Then

    $$\begin{aligned} r^{(i)}=r_0 + \sum _{k=1}^N r_k. \end{aligned}$$

    All these problems are independent and can be solved in parallel.

The local subdomain problems are solved locally on their respective subdomains. The coarse problem is global, and its dimension equals the number of the crosspoints times three plus the number of local eigenfunctions.