Substructuring preconditioners for an $h$-$p$ domain decomposition method with interior penalty mortaring

Abstract

We propose and study an iterative substructuring method for an $h$-$p$ Nitsche-type discretization, following the original approach introduced in Bramble et al. Math. Comp. 47(175):103–134, (1986) for conforming methods. We prove quasi-optimality with respect to the mesh size and the polynomial degree for the proposed preconditioner. Numerical experiments assess the performance of the preconditioner and verify the theory.

1 Introduction

Discontinuous Galerkin (DG) interior penalty (IP) methods were introduced in the late 70’s for approximating second order [8, 34, 59] and fourth order problems [15]. They were arising as a natural evolution or extension of Nitsche’s method [51], and were based on the observation that interelement continuity could be attained by penalization; in the same spirit Dirichlet boundary conditions are weakly imposed for Nitsche’s method. The use, study and application of DG IP methods was abandoned for a while, probably due to the fact that they were never proven to be more advantageous or efficient than their conforming relatives. The lack of optimal and efficient solvers for the resulting linear systems, at that time, surely was also contributing to that situation.

However, over the last ten-fifteen years, there has been a considerable interest in the development and understanding of DG methods for elliptic problems (see, for instance, [9] and the references therein), partly thanks to their simplicity in handling nonmatching grids and designing of hp-refinement strategies. The IP and Nitsche approaches have also found some new applications; in the design of new conforming and nonconforming methods [10, 11, 31, 46, 47, 49] and as a way to handle nonmatching grids for domain decomposition [17, 40].

This has also motivated the interest in developing efficient solvers for DG methods. In particular, additive Schwarz methods are considered and analyzed in [3–7, 16, 24, 42]. Multigrid methods are studied in [25, 44, 48]. Two-level methods and multi-level methods are presented in [26, 33], and other subspace correction methods are considered in [12–14]. It is worth noticing that, so far, most efforts have been directed to develop solvers for the $h$-version of the DG methods. Only very recently, some authors have considered the case of $p$ and $h$-$p$ discretizations. The first result in this direction is given in [7] where the authors study two-level non-overlapping Schwarz preconditioners for a class of $h$-$p$ DG methods.

Still the development of preconditioners for DG methods based on domain decomposition (DD) has been mostly limited to classical Schwarz methods. Research towards more sophisticated nonoverlapping DD preconditioners, such as the Bramble Pasciak Schatz (BPS), Neumann–Neumann, BDDC, FETI or FETI-DP is now at its inception. Nonoverlapping DD methods typically refer to methods defined on a decomposition of a domain made up of a collection of mutually disjoint subdomains, generally called substructures. These family of methods are obviously well suited for parallel computations and furthermore, for several problems (like problems with jump coefficients) they offer some advantages over their relative overlapping methods, and have already proved their usefulness. Roughly speaking, these methods are algorithms for preconditioning the Schur complement with respect to the unknowns on the skeleton of the subdomain partition. They are generally referred to as substructuring preconditioners. While the theory for the conforming case is now well established and understood for many problems [58], the discontinuous nature of the finite element spaces at the interface of the substructures (in the case of Nitsche-type methods) or even within the skeleton of the domain partition, poses extra difficulties in the analysis which preclude from having a straight extension of such theory. Mainly, unlike in the conforming case, the coupling of the unknowns along the interface does not allow for splitting the global bilinear form as a sum of local bilinear forms associated to the substructures (see for instance [42] and [3, Proposition 3.2]). Moreover the discontinuity of the finite element space makes the use of standard $H^{1/2}$-norms in the analysis of the discrete harmonic functions difficult.

For Nitsche-type methods, a new definition of discrete harmonic functions has been introduced in [36] together with some tools (similar to those used in the analysis of mortar preconditioners) that allow the authors to adapt and extend the general theory [58] for substructuring preconditioners in two dimensions. More precisely, in [36–38] the authors introduced and analyzed BDDC, Neumann–Neumann and FETI-DP domain decomposition preconditioners for a first order Nitsche-type discretization of an elliptic problem with jumping coefficients. For the discretization, a symmetric IP DG scheme is used (only) on the skeleton of the subdomain partition, while piecewise linear conforming approximation is used in the interior of the subdomains. In these works, the authors prove quasi-optimality with respect to the mesh-size and optimality with respect to the jump in the coefficient. They also address the case of nonconforming meshes.

More recently, several BDDC preconditioners have been introduced and analyzed for some full DG discretizations [23, 28, 55], following a different path. In [55] the authors consider the $p$-version of the preconditioner for an Hybridized IP DG method [30, 41], for which the unknown is defined directly on the skeleton of the partition. They prove cubic logarithmic growth on the polynomial degree but also show numerically that the results are not sharp. BDDC preconditioners for the IP-DG method have been studied in [23] and [28]. In the former, the authors deal with first order $h$-discretizations; in [28], the authors consider the more challenging $h$-$p$ case. In both works, the approach for the analysis differs considerably from the one taken in [36–38] and relies on suitable space decomposition of the global DG space; using either nonconforming or conforming subspaces together with the auxiliary space techniques studied in [27]. As a consequence the analysis of the BDDC preconditioner for DG discretizations can be reduced to the analysis of the corresponding BDDC for conforming, nonconforming or spectral methods.

In this work, we are interested in addressing $h$-$p$ Nitsche-type methods and we focus on the original substructuring approach introduced in [21] for a conforming discretization of two dimensional problems and in [22, 39] for three dimensions (see also [58, 60] for a detailed description). Our approach differs substantially from the one in [23, 28] and has many similarities with the analysis in [36–38] but we consider the case of $h$-$p$ discretizations and the BPS preconditioner. We focus on the Bramble Pasciak Schatz (BPS) preconditioner, with the aim of filling a gap (since this preconditioner has not been studied for Nitsche or DG methods) but also to provide a simpler analysis of the substructuring preconditioner.

In the framework of nonconforming domain decomposition methods, this kind of preconditioner has been applied to the mortar method [1, 19, 53, 54] and to the three fields domain decomposition method [18], always considering the $h$-version of the methods. For spectral discretizations and the $p$ version of conforming approximations the preconditioner has been studied in [50, 52]. For $h$-$p$ conforming discretizations of two dimensional problems the BPS preconditioner is studied in [2]. To the best of our knowledge, this preconditioner has not been considered for Nitsche-type or DG methods before.

In our analysis of the BPS preconditioner for an $h$-$p$ Nitsche-type discretization, we use some of the tools introduced in [36, 37], such as their definition of the discrete harmonic lifting that allows to define the discrete Steklov–Poincaré operator associated to the Nitsche-type method. However, our construction of the preconditioners is guided by the definition of a suitable norm on the skeleton of the subdomain partition, that scales like an $H^{1/2}$-norm and captures the energy of the DG functions on the skeleton. This allow us to provide a much simpler analysis, proving quasi-optimality with respect to the mesh size and the polynomial degree for the proposed preconditioners. Furthermore, we demonstrate that unlike what happens in the conforming case, to ensure quasi-optimality of the preconditioners a block diagonal structure that de-couples completely the edge and vertex degrees of freedom on the skeleton is not possible; this is due to the presence of the penalty term which is needed to deal with the discontinuity. We show however that the implementation of the preconditioner can be done efficiently and that it performs in agreement with the theory.

The rest of the paper is organized as follows. The basic notation, functional setting and the description of the Nitsche-type method are given in next section; Sect. 2. Some technical tools required in the construction and analysis of the proposed preconditioner are revised in Sect. 3. The substructuring preconditioner is introduced and analyzed in Sect. 4. Its practical implementation together with some variants of the preconditioner are discussed in Sect. 5. The theory is verified through several numerical experiments presented in Sect. 6.

Here and in the following, to avoid the proliferation of constants, we will use the notation $x \lesssim y$ to represent the inequality $x \le C y$, where $C > 0$ might depend on the shape regularity of the different partitions, but will be always independent of the mesh sizes, the polynomial approximation order, and the size and number of subdomains. Writing $x \simeq y$ will signify that there exists a constant $C > 0$ such that $C^{-1}x \le y \le Cx$.

2 Nitsche methods and basic notation

In this section, we introduce the basic notation, the functional setting and the Nitsche discretization.

To ease the presentation we restrict ourselves to the following model problem. Let $\Omega \subset {\mathbb {R}}^{2}$ be a bounded polygonal domain, let $f\in L^2(\Omega )$ and let

$$\begin{aligned} \left\{ \begin{array}{lll} -\Delta u^{*} = f &{}\quad \text{ in } \Omega ,\\ u^{*} =0 &{}\quad \text{ on } \partial \Omega . \end{array}\right. \end{aligned}$$

The above problem admits the following weak formulation: find $u^*\in H^1_0(\Omega )$ such that:

$$\begin{aligned} a(u^*,v)=f(v)\quad \text {for all} \quad v\in H^1_0(\Omega ), \end{aligned}$$

(1)

where

$$\begin{aligned} a(u,v) = \int _\Omega \nabla u \cdot \nabla v \, \mathrm dx \quad f(v) = \int _\Omega f v \, \mathrm dx , \quad \forall \, u, v\in H^1_0(\Omega ). \end{aligned}$$

2.1 Partitions

We now introduce the different partitions needed in our work. We denote by ${\mathcal T}_{H}$ a geometrically conforming subdomain partition of $\Omega$ into $N$ nonoverlapping shape-regular triangular or quadrilateral subdomains:

$$\begin{aligned} \overline{\Omega }=\bigcup _{\ell =1}^{N} \overline{\Omega }_\ell ,\,\,\, {\Omega _{\ell }}\cap \Omega _j =\emptyset \quad \ell \ne j. \end{aligned}$$

We set

$$\begin{aligned} {H_{\ell }}=\min _{j\,:\, \bar{\Omega }_\ell \cap \bar{\Omega }_j \ne \emptyset } H_{\ell ,j} \qquad \text{ where } \quad H_{\ell ,j}=\left| \partial {\Omega _{\ell }}\cap \partial \Omega _j\right| , \end{aligned}$$

(2)

and we also assume that ${H_{\ell }}\simeq \text{ diam }({\Omega _{\ell }})$ for each $\ell =1,\ldots N$. We finally define the granularity of ${\mathcal T}_{H}$ by $H=\min _{\ell } {H_{\ell }}$.

We denote by $\Sigma$ the skeleton of the subdomain partition ${\mathcal T}_{H}$

$$\begin{aligned} \Sigma =\bigcup _{\ell =1}^{N} \partial {\Omega _{\ell }}\end{aligned}$$

and we set

$$\begin{aligned} \Gamma =\prod _{\ell =1}^{N} \partial {\Omega _{\ell }}. \end{aligned}$$

Observe that from the above definitions, we allow functions defined on $\Gamma$ to be double-valued while functions defined on $\Sigma$ are singled valued.

The edges of the subdomain partition that form the skeleton will be denoted by $E$ and we will refer to them as macro edges or, when they refer to a particular subdomain, as subdomain edges.

For each ${\Omega _{\ell }}$, let $\left\{ {\mathcal T}_{h}^\ell \right\}$ be a family of fine partitions of $\Omega _\ell$ into elements (triangles or quadrilaterals) $K$ with diameter $h_{K}$. All partitions ${\mathcal T}_{h}^\ell$ are assumed to be shape-regular and we define a global partition ${\mathcal T}_{h}$ of $\Omega$ as

$$\begin{aligned} {\mathcal T}_{h}=\bigcup _{\ell =1}^{N} {\mathcal T}_{h}^\ell . \end{aligned}$$

Observe that by construction ${\mathcal T}_{h}$ is a fine partition of $\Omega$ which is compatible within each subdomain $\Omega _\ell$ but which may be nonmatching across the skeleton $\Sigma$. Throughout the paper, we always assume that the following bounded local variation property holds: for any pair of neighboring elements $K^{+} \in {\mathcal T}_{h}^{\ell ^{+}}$ and $K^{-} \in {\mathcal T}_{h}^{\ell ^{-}}$, $\ell ^{+} \ne \ell ^{-}$, $h_{K^{+}}\simeq h_{K^{-}}$.

Note that the restriction of ${\mathcal T}_{h}$ to the skeleton $\Sigma$ induces a partition of each subdomain edge $E\subset \Gamma$. We define the set of element edges on the skeleton $\Sigma$ and on the boundary of $\Omega$ as follows:

$$\begin{aligned} {{\mathcal E}^{o}_h}&:=\{ e = \partial K^{+} \cap \partial K^{-}, \, K^{+}\in {\mathcal T}_{h}^{\ell ^{+}}\, , K^{-}\in {\mathcal T}_{h}^{\ell ^{-}}\, , \ell ^{+} \ne \ell ^{-}\} \,, \\ {{\mathcal E}^{\partial }_h}&:=\{ e= \partial K\cap \partial \Omega , \, K\in {\mathcal T}_{h}\} \,, \end{aligned}$$

and we set ${{\mathcal E}_h}={{\mathcal E}^{o}_h}\cup {{\mathcal E}^{\partial }_h}$.

2.2 Basic functional setting

For $s\ge 1$, we define the broken Sobolev space

$$\begin{aligned} H^{s}({\mathcal T}_{H})=\left\{ \phi \in L^{2}(\Omega ) \,\,: \quad \phi \big |_{{\Omega _{\ell }}} \in H^{s}({\Omega _{\ell }}) \quad \forall \,\, {\Omega _{\ell }}\in {\mathcal T}_{H}\,\right\} \sim \prod _{\ell }\, H^s({\Omega _{\ell }}), \end{aligned}$$

whereas the trace space associated to $H^{1}({\mathcal T}_{H})$ is defined by

$$\begin{aligned} \Phi = \prod _{\ell }\, H^{1/2}(\partial {\Omega _{\ell }}). \end{aligned}$$

For $u = (u^\ell )_{\ell =1}^N$ in $H^1({\mathcal T}_{H})$ we will denote by $u_{|_\Gamma }$ the unique element $\phi =(\phi ^\ell )_{\ell =1}^N$ in $\Phi$ such that

$$\begin{aligned} \phi ^\ell =u^\ell _{|_{\partial {\Omega _{\ell }}}}. \end{aligned}$$

We now recall the definition of some trace operators following [9], and introduce the different discrete spaces that will be used in the paper.

Let $e\in {{\mathcal E}^{o}_h}$ be an edge on the interior skeleton shared by two elements $K^{+}$ and $K^{-}$ with outward unit normal vectors $\mathbf{n}^{+}$ and $\mathbf{n}^{-}$, respectively. For scalar and vector-valued functions $\varphi \in H^{1}({\mathcal T}_{H})$ and ${\varvec{\tau }}\in \left[ {H}^{1}({\mathcal T}_{H})\right] ^2$, we define the average and the jump on $e \in {{\mathcal E}^{o}_h}$ as

$$\begin{aligned}&\{{\varvec{\tau }}\}=\frac{1}{2}({\varvec{\tau }}^+ +{\varvec{\tau }}^-),&[\![\,\varphi \,]\!]=\varphi ^+\mathbf{n}^++\varphi ^-\mathbf{n}^-,&\text{ on } e\in {{\mathcal E}^{o}_h}. \end{aligned}$$

On a boundary element edge $e\in {{\mathcal E}^{\partial }_h}$ we set $\{{\varvec{\tau }}\}={\varvec{\tau }}$ and $[\![\,\varphi \,]\!]=\varphi \mathbf{n}$, $\mathbf{n}$ denoting the outward unit normal vector to $\Omega$.

To each element $K\in \mathcal {T}^\ell _h$, we associate a polynomial approximation order $p_{K} \ge 1$, and define the $h$-$p$ finite element space of piecewise polynomials as

$$\begin{aligned} {X_h^{\ell }}= \{v \in C^0({\Omega _{\ell }})\text { such that }v|_{K} \in \mathbb {P}^{p_K}(K), ~K\in \mathcal {T}^\ell _h\}, \end{aligned}$$

where $\mathbb {P}^{p_{K}}(K)$ stands for the space of polynomials of degree at most $p_{K}$ on $K$. We also assume that the polynomial approximation order satisfies a local bounded variation property: for any pair of elements $K^{+}$ and $K^{-}$ sharing an edge $e \in {{\mathcal E}^{o}_h}$, $p_{K^{+}} \simeq p_{K^{-}}$.

Our global approximation space ${X_h}$ is then defined as

$$\begin{aligned} {X_h}= \{ v\in L^{2}(\Omega ) \,\, : \text { such that }v_{|_{{\Omega _{\ell }}}} \in {X_h^{\ell }}\}\sim \prod _{\ell =1}^N{X_h^{\ell }}. \end{aligned}$$

We also define ${X^{0}_h}\subset {X_h}$ as the subspace of functions of ${X_h}$ vanishing on $\Gamma$, i.e.,

$$\begin{aligned} {X^{0}_h}=\{ v\in {X_h}\,\, : \text { such that }v_{|_{\Gamma }} = 0 \} . \end{aligned}$$

The trace spaces associated to ${X_h^{\ell }}$ and ${X_h}$ are defined as follows

$$\begin{aligned}&\Phi _h^{\ell }=\{ \eta ^{\ell } \in H^{1/2}(\partial {\Omega _{\ell }}) \, :\,\, \eta ^{\ell } = w_{|_{ \partial {\Omega _{\ell }}}} \text { for some } w\in {X_h^{\ell }}\} \quad \forall \ell =1,\ldots ,N,\;\\&\Phi _h= \prod _{\ell =1}^{N} \Phi _h^{\ell }\; \ \subset \Phi . \end{aligned}$$

Notice that the functions in the above finite element spaces are conforming in the interior of each subdomain but are double-valued on the skeleton. Moreover, any function $v\in {X_h}$ can be represented as $v = ( v^{\ell })_{\ell =1}^N$ with $v^{\ell }\in {X_h^{\ell }}$.

Next, for each subdomain ${\Omega _{\ell }}\in {\mathcal T}_{H}$ and for each subdomain edge $E \subset \partial {\Omega _{\ell }}$, we define the discrete trace spaces

$$\begin{aligned}&\Phi _{\ell }(E) = {\Phi _h^{\ell }}_{|_E}.\end{aligned}$$

Note that, since we are in two dimensions, the boundary of a subdomain edge $E$ is the set of the two endpoints (or vertices) of $E$, that is if $E=(a,b)$ then $\partial E=\{a,b\}$.

Finally, we introduce a suitable coarse space ${\mathfrak L}_{H} \subset \Phi$, that will be required for the definition of the substructuring preconditioner:

$$\begin{aligned} {\mathfrak L}_{H} = \{ \eta = (\eta ^\ell )_{\ell =1}^N\in \Phi \,\, : \,\,\, \eta ^\ell _{|_{E}} \in {\mathbb {P}}^{1}(E), \quad \forall \, E\subset \partial {\Omega _{\ell }}, \quad \forall {\Omega _{\ell }}\in {\mathcal T}_{H}\}. \end{aligned}$$

(3)

2.3 Nitsche-type methods

In this section, we introduce the Nitsche-type method we consider for approximating the model problem (1). In such method, first introduced in [57], weak continuity across the skeleton is enforced in an analogous way to what is done at interelement edges in the interior penalty discontinuous Galerkin method.

We introduce a mesh size function $\mathtt {h}\in L^{\infty }(\Sigma )$ defined as

$$\begin{aligned} \mathtt {h}(x)=\left\{ \begin{array}{ll} h_{K} &{}\quad \hbox {if } x\in \partial K\cap \partial \Omega ,\\ \min \{ h_{K^{+}}, h_{K^{-}}\} &{}\quad \hbox {if } x\in \partial K^{+} \cap \partial K^{-}\cap \Gamma , K^{\pm }\in {\mathcal T}_{h}^{\ell ^{\pm }}\, , \ell ^{+} \ne \ell ^{-}, \end{array}\right. \end{aligned}$$

(4)

and a polynomial degree function $\mathtt {p}\in L^{\infty }(\Sigma )$:

$$\begin{aligned} \mathtt {p}(x)=\left\{ \begin{array}{ll} p_{K} &{}\quad \hbox {if } x\in \partial K\cap \partial \Omega ,\\ \max \{ p_{K^{+}}, p_{K^{-}}\} &{}\quad \hbox {if } x\in \partial K^{+} \cap \partial K^{-}\cap \Gamma , K^{\pm }\in {\mathcal T}_{h}^{\ell ^{\pm }}, \ell ^{+} \ne \ell ^{-}. \end{array}\right. \end{aligned}$$

(5)

For each subdomain $\Omega _\ell$, we also define $h_{\ell }$ and $p_{\ell }$ as the minimum (resp. the maximum) of the restriction to $\partial {\Omega _{\ell }}$ of the local mesh size $\mathtt {h}$ (resp. the local polynomial degree function $\mathtt {p}$), that is,

$$\begin{aligned} h_{\ell }=\min _{x\in \partial {\Omega _{\ell }}\cap \Gamma } \mathtt {h}(x) \quad \quad \text { and } \quad \quad p_{\ell }=\max _{x\in \partial {\Omega _{\ell }}\cap \Gamma } \mathtt {p}(x) . \end{aligned}$$

(6)

Remark 2.1

A different definition for the local mesh size function $\mathtt {h}$ and the local polynomial degree function $\mathtt {p}$ involving harmonic averages is sometimes used for the definition of Nitsche or DG methods [36]. We point out that such a definition yields to functions $\mathtt {h}$ and $\mathtt {p}$ which are of the same order as the ones given in (4) and (5), and therefore result in an equivalent method.

We now define the following Nitsche-type discretization [17, 57] to approximate problem (1): find $u^*_h\in {X_h}$ such that

$$\begin{aligned} {\mathcal A}_h(u^*_h,v_h)=f(v_h)\quad \text { for all } \quad v_h\in {X_h}, \end{aligned}$$

(7)

where, for all $u,v \in {X_h}, {\mathcal A}_h(\cdot ,\cdot )$ is defined as

$$\begin{aligned} {\mathcal A}_h(u,v)&= \sum _{\ell =1}^{N}\int _{{\Omega _{\ell }}} \nabla u \cdot \nabla v \, \mathrm dx -\sum _{e \in {{\mathcal E}_h}} \int _e \{\nabla u\}\cdot [\![\,v\,]\!]\, \mathrm ds \nonumber \\&- \sum _{e \in {{\mathcal E}_h}} \int _e [\![\,u\,]\!]\cdot \{\nabla v\} \, \mathrm ds +\sum _{e \in {{\mathcal E}_h}} \alpha \, \int _e \mathtt {p}^2 \, \mathtt {h}^{-1}[\![\,u\,]\!]\cdot [\![\,v\,]\!] \, \mathrm ds . \end{aligned}$$

(8)

Here, $\alpha >0$ is the penalty parameter that needs to be chosen $\alpha \ge \alpha _0$ for some $\alpha _0\gtrsim 1$ large enough to ensure the coercivity of ${\mathcal A}_h(\cdot ,\cdot )$.

On ${X_h}$, we introduce the following seminorms:

$$\begin{aligned} |v|_{1,{\mathcal T}_{H}}^{2}=\sum _{\ell =1}^{N}\Vert \nabla v\Vert ^{2}_{L^{2}({\Omega _{\ell }})} , \quad | v |_{*,{{\mathcal E}_h}}^{2} = \sum _{e\in {{\mathcal E}_h}} \Vert \mathtt {p}\, \mathtt {h}^{-1/2}\, [\![\,v\,]\!]\Vert _{L^{2}(e)}^{2}, \end{aligned}$$

(9)

together with the natural norm induced by ${\mathcal {A}}_{h}(\cdot ,\cdot )$:

$$\begin{aligned} \Vert v\Vert _{h}^2=|v|_{1,{\mathcal T}_{H}}^{2} + \alpha | v |_{*,{{\mathcal E}_h}}^{2} \quad \forall \, v\in {X_h}. \end{aligned}$$

(10)

Following [57] (see also [9]) it is easy to see the bilinear form ${\mathcal A}_h(\cdot ,\cdot )$ is continuous and coercive (provided $\alpha \ge \alpha _0$ ) with respect to the norm (10), i.e.,

$$\begin{aligned}&\hbox {Continuity}: |{\mathcal A}_h(u,v)| \lesssim \Vert u\Vert _{h}\Vert v\Vert _{h} \quad \forall \, u,v\in {X_h}\\&\hbox {Coercivity}: {\mathcal A}_h(v,v) \gtrsim \Vert v\Vert _{h}^{2} \quad \forall \, v\in {X_h}. \end{aligned}$$

From now on we will always assume that $\alpha \ge \alpha _0$. Notice that the continuity and coercivity constants depend only on the shape regularity constant of ${\mathcal T}_{h}$.

3 Some technical tools

We now revise some technical tools that will be required in the construction and analysis of the proposed preconditioners.

We recall that, for $\gamma$ being either an element edge or a macro edge or the boundary of a subdomain, and for $s \in ]0,1[$, we can define the $H^s(\gamma )$ seminorm and norm by

$$\begin{aligned} |\eta |^2_{H^{s}(\gamma )} = \int _{\gamma } \int _{\gamma } \frac{(\eta (x) - \eta (y))^2}{| x - y |^{2s+1} } \,ds_x \,ds_y, \qquad \Vert \eta \Vert ^2_{H^{s}(\gamma )} = \Vert \eta \Vert _{L^2(\gamma )}^2 + | \eta |^2_{H^{s}(\gamma )}.\nonumber \\ \end{aligned}$$

(11)

For $E \subset \partial \Omega _\ell$ a subdomain edge, we will also consider the space $H^{1/2}_{00}(E)$ of functions whose extension by zero is in $H^{1/2}(\partial \Omega _\ell )$, which we will equip with the norm

$$\begin{aligned} \Vert \eta \Vert ^2_{H^{1/2}_{00}(E)} = | \eta |^2_{H^{1/2}(E)} + \int _E \frac{| \eta (x) |^2}{| x - a |^{2s}} \,ds_x +\int _E \frac{| \eta |^2}{| x - b |^{2s}} \,ds_x. \end{aligned}$$

The following local inverse inequality holds (cf. [56], for example): for any $\eta \in {\mathbb {P}}^{p_{K}}(K)$ it holds

$$\begin{aligned} | \eta |_{H^{r}(e)} \lesssim p_{K}^{2(r-s)}h_{K}^{s - r} | \eta |_{H^{s}(e)}, \quad e\subset \partial K\end{aligned}$$

for all $s,r$ with $0 \le s < r \le 1$. Using the above inequality for $s = 0$ and $r=1$ and space interpolation, it is easy to deduce that for a subdomain edge $E\subset \partial \Omega _\ell$ and for all $s,r, 0 \le s < r \le 1$, for all $\eta \in X_h^\ell |_E$ it holds that

$$\begin{aligned} | \eta |_{H^{r}(E)}&\lesssim p_{\ell }^{2(r-s)} h_{\ell }^{s - r} | \eta |_{H^{s}(E)}, \end{aligned}$$

(12)

$$\begin{aligned} | \eta |_{H^{r}(\partial {\Omega _{\ell }})}&\lesssim p_{\ell }^{2(r-s)} h_{\ell }^{s - r} | \eta |_{H^s(\partial {\Omega _{\ell }})}, \end{aligned}$$

(13)

The next two results are a generalization to the $h$-$p$ version of [21, Lemma 3.2, 3.4 and 3.5] and [18, Lemma 3.2], see e.g., [45]. For the sake of brevity the proof is omitted.

Lemma 3.1

For all $\xi \in \Phi _h^\ell$ and for all $\zeta _L\in H^{1/2}(\partial {\Omega _{\ell }})$ linear on each edge of $\partial {\Omega _{\ell }}$ and such that $\zeta _L(a)= \xi (a)$ at all vertices $a$ of ${\Omega _{\ell }}$, it holds

$$\begin{aligned} |\zeta _L |_{H^{1/2}(\partial {\Omega _{\ell }})}^2 \lesssim \left( 1+\log {\left( \frac{H_\ell \,p_{\ell }^{2}}{h_{\ell }}\right) }\right) |\xi |^2_{H^{1/2}(\partial {\Omega _{\ell }})}. \end{aligned}$$

Lemma 3.2

For all $\xi \in \Phi _h^\ell$ such that $\xi (a) = 0$ at all vertices $a$ of ${\Omega _{\ell }}$ and for all $\zeta _L\in H^{1/2}(\partial {\Omega _{\ell }})$ linear on each subdomain edge of $\partial {\Omega _{\ell }}$, it holds

$$\begin{aligned} \sum _{E\subset \partial {\Omega _{\ell }}} \Vert \xi \Vert _{H^{1/2}_{00}(E)}^2\lesssim \left( 1+\log {\left( \frac{H_{\ell }\,p_{\ell }^{2}}{h_{\ell }}\right) }\right) ^2 \left| \xi + \zeta _L \right| _{H^{1/2}(\partial {\Omega _{\ell }})}^2. \end{aligned}$$

3.1 Norms on $\Phi _h$

We now introduce a suitable norm on $\Phi _h$ that will suggest how to properly construct the preconditioner. The natural norm that we can define for all $\eta =(\eta ^\ell )_{\ell =1}^N\in \Phi _h$ is:

$$\begin{aligned} ||\eta ||_{\Phi _h} = \inf _{ \begin{array}{c} u\in {X_h}\\ {u}_{| \Gamma }=\eta \end{array}} \Vert u\Vert _{h}, \end{aligned}$$

(14)

where the $\inf$ is taken over all $u\in {X_h}$ that coincide with $\eta$ on $\Gamma$. We recall that the identity $\eta = u_{|_\Gamma }$ is to be intended as $\eta ^\ell = u^\ell _{|_{\partial {\Omega _{\ell }}}}$. Although (14) is the natural trace norm induced on $\Phi$ by the norm (10), working with it might be difficult.

For this reason, we introduce another norm which will be easier to deal with and which, as we will show below, is equivalent to (14). The structure of the preconditioner proposed in this paper will be driven by this norm. We define:

$$\begin{aligned} ||\eta ||_{\Phi _h,*}^2&=\displaystyle \sum \nolimits _{{\Omega _{\ell }}\in {\mathcal T}_{H}} |\eta |^2_{H^{1/2}(\partial {\Omega _{\ell }})} + \alpha \displaystyle \sum \nolimits _{e\in {{\mathcal E}_h}}\Vert \mathtt {p}\,\mathtt {h}^{-1/2} [\![\,\eta \,]\!]\Vert _{L^{2}(e)}^{2}. \end{aligned}$$

(15)

The next result shows that the norms (14) and (15) are indeed equivalent:

Lemma 3.3

The following norm equivalence holds:

$$\begin{aligned} ||\eta ||_{\Phi _h} \lesssim ||\eta ||_{\Phi _h,*} \lesssim ||\eta ||_{\Phi _h} \quad \forall \eta \in \Phi _h\end{aligned}$$

Proof

We first prove that $||\eta ||_{\Phi _h,*} \lesssim ||\eta ||_{\Phi _h}$. Let $\eta =(\eta ^\ell )_{\ell =1}^N\in \Phi _h$ and let $u=(u^\ell )_{\ell =1}^N$ such that ${u}_{| \Gamma }=\eta$. Thanks to the trace inequality, we have

$$\begin{aligned} |\eta ^{\ell }|^2_{H^{1/2}(\partial {\Omega _{\ell }})} \lesssim |u^{\ell }|^2_{H^1({\Omega _{\ell }})}, \end{aligned}$$

and, summing over all the subdomains ${\Omega _{\ell }}\in {\mathcal T}_{H}$ we have

$$\begin{aligned} \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} |\eta ^{\ell }|^2_{H^{1/2}(\partial {\Omega _{\ell }})} \lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} |u^{\ell }|^2_{H^1({\Omega _{\ell }})} =|u|_{1,{\mathcal T}_{H}}^{2}. \end{aligned}$$

Adding now the term $\alpha \sum _{e\in {{\mathcal E}_h}}\Vert \mathtt {p}\mathtt {h}^{-1/2} [\![\,\eta \,]\!]\Vert _{L^2(e)}^{2}$ to both sides, and recalling the definition of the norms (10), (14) and (15) we get the thesis.

We now prove that $||\eta ||_{\Phi _h}\lesssim ||\eta ||_{\Phi _h,*}$. Given $\eta = (\eta ^\ell )_{\ell =1}^N\in \Phi _h$, let $\check{u}^\ell \in X_h^\ell$ be the standard discrete harmonic lifting of $\eta ^\ell$, for which the bound $| \check{u}^\ell |_{H^1({\Omega _{\ell }})} \lesssim | \eta ^\ell |_{H^{1/2}(\partial {\Omega _{\ell }})}$ holds (see e.g. [21]) and let $\check{u} =(\check{u}^\ell )_{\ell =1}^N$. Summing over all the subdomains ${\Omega _{\ell }}$ and adding the term $\alpha \sum _{e\in {{\mathcal E}_h}}\Vert \mathtt {p}\mathtt {h}^{-1/2} [\![\,\eta \,]\!]\Vert _{L^2(e)}^{2}$ we get

$$\begin{aligned} ||\eta ||_{\Phi _h} \le \Vert \check{u}\Vert _{h}\lesssim ||\eta ||_{\Phi _h,*}. \end{aligned}$$

$\square$

4 Substructuring preconditioners

In this section we present the construction and analysis of a substructuring preconditioner for the Nitsche method (7–8).

The first step in the construction is to split the set of degrees of freedom into interior degrees of freedom (corresponding to basis functions identically vanishing on the skeleton) and degrees of freedom associated to the skeleton of the subdomain partition.

Then, the idea of the “substructuring” approach (see [21]) consists in further distinguishing two types among the degrees of freedom associated to $\Gamma$: edge degrees of freedom and vertex degrees of freedom. Therefore, any function $u \in {X_h}$ can be split as the sum of three suitably defined components: $u = u^{0}+u_{\Gamma }=u^0 + u^E + u^V$.

We first show how to eliminate the interior degrees of freedom and introduce the discrete Steklov–Poincaré operator associated to (8), acting on functions defined on $\Gamma$.

We then propose a preconditioner of substructuring type for the discrete Steklov–Poincaré operator and provide the convergence analysis.

4.1 Discrete Steklov–Poincaré operator

Following [36, 37], we now introduce a discrete harmonic lifting that allows to defining the discrete Steklov–Poincaré operator associated to (8). We also show that such a discrete Steklov–Poincaré operator defines a norm that is equivalent to the one defined in Lemma 5.2.

Let ${X^{0}_h}\subset {X_h}$ be the subspace of functions vanishing on the skeleton of the decomposition. Given any discrete function $w \in {X_h}$, we can split it as the sum of an interior function $w^0 \in {X^{0}_h}$ and a suitable discrete lifting of its trace. More precisely, following [36, 37], we split

$$\begin{aligned} w = w^0 + R_h(w_{| \Gamma }), \quad w^0 \in {X^{0}_h}, \end{aligned}$$

where, for $\eta \in \Phi _h, R_h(\eta ) \in {X_h}$ denotes the unique element of ${X_h}$ satisfying

$$\begin{aligned} R_h(\eta )_{|_\Gamma } = \eta , \quad {\mathcal A}_h(R_h(\eta ),v_h) = 0 \quad \forall v_h \in {X^{0}_h}. \end{aligned}$$

(16)

The following proposition is easy to prove (see [36, 37]).

Proposition 4.1

For $\eta =(\eta ^\ell )_{\ell =1}^N\in \Phi _h$, the following identity holds:

$$\begin{aligned} R_h(\eta )_{|_{{\Omega _{\ell }}}} = w^\ell _H + w^\ell _0, \end{aligned}$$

with $w^\ell _H \in X_h^\ell$ denoting the standard discrete harmonic lifting of $\eta ^\ell$

$$\begin{aligned} w^\ell _H = \eta ^\ell \text { on } \partial {\Omega _{\ell }}, \quad \int _{\Omega _{\ell }}\nabla w^\ell _H \cdot \nabla v_h^\ell = 0 \quad \forall v_h^\ell \in X_h^\ell \cap H^1_0({\Omega _{\ell }}), \end{aligned}$$

and $w^\ell _0 \in X_h^\ell \cap H^1_0({\Omega _{\ell }})$ being the solution of

$$\begin{aligned} \int _{{\Omega _{\ell }}} \nabla w^\ell _0 \cdot \nabla v_h^\ell = \int _{\partial {\Omega _{\ell }}} [\![\,\eta ^ \ell \,]\!] \cdot \nabla v_h^\ell , \quad \forall v_h^\ell \in X_h^\ell \cap H^1_0({\Omega _{\ell }}). \end{aligned}$$

The space ${X_h}$ can be split as direct sum of an interior and a trace component, that is

$$\begin{aligned} {X_h}= {X^{0}_h}\oplus R_h(\Phi _h) . \end{aligned}$$

Using the above splitting, the definition of $R_h(\cdot )$ and the definition of ${\mathcal A}_h(\cdot ,\cdot )$, it is not difficult to verify that,

$$\begin{aligned} {\mathcal A}_h(w,v)&= {\mathcal A}_h(w^0,v^0) + {\mathcal A}_h(R_h(w_{|_\Gamma }),R_h(v_{|_\Gamma })) \\&= a(w^0,v^0) + s(w_{|_\Gamma },v_{|_\Gamma }), \quad \forall \, w,v \in {X_h}\end{aligned}$$

where the discrete Steklov–Poincaré operator $s: \Phi _h\times \Phi _h\rightarrow {\mathbb R}$ is defined as

$$\begin{aligned} s(\xi ,\eta ) = {\mathcal A}_h(R_h(\xi ),R_h(\eta )) \quad \forall \, \xi , \eta \in \Phi _h. \end{aligned}$$

(17)

We have the following result:

Lemma 4.2

Let $R_h$ be the discrete harmonic lifting defined in (16). Then,

$$\begin{aligned} \Vert R_h(\eta )\Vert _{h} \simeq || \eta ||_{\Phi _h,*} \quad \forall \, \eta \in \Phi _h. \end{aligned}$$

Proof

If we show that $\Vert R_h(\eta )\Vert _{h} \simeq || \eta ||_{\Phi _h}$, then the thesis follows thanks to the equivalence of the norms shown in Lemma 3.3. First, we prove that $\Vert R_h(\eta )\Vert _{h} \lesssim || \eta ||_{\Phi _h}$; let $\eta \in \Phi _h$, then from the definition of the $\inf$, we get that

$$\begin{aligned} \exists u\in {X_h}\,:\, u_{| \Gamma } = \eta \quad {\hbox { such that }} \quad \Vert u\Vert _{h} \le 2 ||\eta ||_{\Phi _h}. \end{aligned}$$

Then, we can write $R_h(\eta ) = u+v$ with $v\in {X^{0}_h}$, and (16) reads

$$\begin{aligned} {\mathcal A}_h(v,w) = -{\mathcal A}_h(u,w)\quad \forall w \in {X^{0}_h}. \end{aligned}$$

Setting $w=v \in {X^{0}_h}$ in the above equation, leads to

$$\begin{aligned} {\mathcal A}_h(v,v) = -{\mathcal A}_h(u,v). \end{aligned}$$

Then, using the coercivity and continuity of ${\mathcal A}_h(\cdot ,\cdot )$ in the $\Vert \cdot \Vert _{h}$ norm we find

$$\begin{aligned} \Vert v\Vert _{h}^{2} \lesssim {\mathcal A}_h(v,v)=|{\mathcal A}_h(u,v)| \lesssim \Vert u\Vert _{h}\Vert v\Vert _{h}. \end{aligned}$$

Hence, $\Vert v\Vert _{h} \lesssim \Vert u\Vert _{h}$, and so this bound together with the triangle inequality gives

$$\begin{aligned} \Vert R_h(\eta )\Vert _{h}\le \Vert u\Vert _{h}+\Vert v\Vert _{h} \lesssim \Vert u\Vert _{h} \lesssim ||\eta ||_{\Phi _h}. \end{aligned}$$

The other inequality $|| \eta ||_{\Phi _h} \lesssim \Vert R_h(\eta )\Vert _{h}$ follows from the trace theorem. $\square$

From the above result, the following result for the discrete Steklov–Poincaré operator follows easily.

Corollary 4.3

For all $\xi \in \Phi _h$, it holds

$$\begin{aligned} s(\xi ,\xi ) \simeq ||\xi ||_{\Phi _h,*}^2. \end{aligned}$$

Proof

Let $\xi \in \Phi _h$ then from the definition of $s(\cdot ,\cdot )$, the continuity and coercivity of ${\mathcal A}_h(\cdot ,\cdot )$ and applying Lemma 4.2 we have

$$\begin{aligned} s(\xi ,\xi ) = {\mathcal A}_h(R_h(\xi ),R_h(\xi )) \simeq \Vert R_h(\xi )\Vert _{h}^2\simeq ||\xi ||_{\Phi _h,*}^2. \end{aligned}$$

$\square$

4.2 The preconditioner

Following the approach introduced in [21], we now present the construction of a preconditioner for the discrete Steklov–Poincaré operator $s(\cdot ,\cdot )$. We split the space of skeleton functions $\Phi _h$ as the sum of vertex and edge functions. We observe that independently of whether the two dimensional mesh ${\mathcal T}_{h}$ consists of triangles or quadrangles, the trace $\Phi _h^{\ell }$ of the space ${X_h^{\ell }}$ contains the space of piecewise linear functions on the one dimensional mesh induced on $\Gamma ^\ell$ by ${\mathcal T}_{h}^\ell$. Therefore ${\mathfrak L}_{H} \subset \Phi _h$.

We then introduce the space of edge functions $\Phi _h^E \subset \Phi _h$ defined by

$$\begin{aligned} \Phi _h^E = \{ \eta \in \Phi _h,~ \eta ^\ell (a)=0~ \text { at all vertex } a \text { of } ~{\Omega _{\ell }}\quad \forall \, {\Omega _{\ell }}\in {\mathcal T}_{H}\} \end{aligned}$$

and we immediately get

$$\begin{aligned} \Phi _h= {\mathfrak L}_{H} \oplus \Phi _h^E . \end{aligned}$$

(18)

The preconditioner that we consider is built by introducing the bilinear forms

$$\begin{aligned} {\hat{s}}^E:\Phi _h^E \times \Phi _h^E \rightarrow {\mathbb R}\qquad {\hat{s}}^V:{\mathfrak L}_{H} \times {\mathfrak L}_{H} \rightarrow {\mathbb R}\end{aligned}$$

acting respectively on edge and vertex functions. We assume that ${\hat{s}}^E$ and ${\hat{s}}^V$ satisfy:

$$\begin{aligned} {\hat{s}}^E(\eta ^E,\eta ^E)&\simeq \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}}\sum _{E\subset \partial {\Omega _{\ell }}}\Vert \eta ^E\Vert ^2_{H^{1/2}_{00}(E)} \quad \forall \, \eta ^{E}\in \Phi _h^E, \end{aligned}$$

(19)

$$\begin{aligned} {\hat{s}}^V(\eta ^V,\eta ^V)&\simeq \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} \left| \eta ^V\right| ^2_{H^{1/2}(\partial {\Omega _{\ell }})} \quad \forall \, \eta ^{V} \in {\mathfrak L}_{H}, \end{aligned}$$

(20)

and we define ${\hat{s}}: \Phi _h\times \Phi _h\rightarrow {\mathbb R}$ as

$$\begin{aligned} {\hat{s}}(\eta ,\xi ) = {\hat{s}}^E(\eta ^E,\xi ^E) + {\hat{s}}^V(\eta ^V,\xi ^V) + q(\eta ,\xi ), \end{aligned}$$

(21)

where

$$\begin{aligned} q(\eta ,\xi ) =\sum \limits _{e\in {{\mathcal E}_h}} \alpha \int _e \mathtt {p}^2 \,\mathtt {h}^{-1}[\![\,\eta \,]\!] [\![\,\xi \,]\!] \, ds \quad \forall \, \eta ,\xi \in \Phi _h. \end{aligned}$$

(22)

Finally, we can state the main theorem of the paper.

Theorem 4.4

Let $s(\cdot ,\cdot )$ and ${\hat{s}}(\cdot ,\cdot )$ be the bilinear forms defined in (17) and (21), respectively. Then, we have:

$$\begin{aligned} \min _\ell \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^{-2} {\hat{s}}(\eta ,\eta ) \lesssim s(\eta ,\eta ) \lesssim {\hat{s}}(\eta ,\eta ) \qquad \forall \, \eta \in \Phi _h. \end{aligned}$$

The proof of Theorem 4.4 follows the analogous proofs given in [18, 21] for conforming finite element approximations. We give it here for completeness.

Proof

We start proving that $s(\eta ,\eta ) \lesssim {\hat{s}}(\eta ,\eta )$. Let $\eta \in \Phi _h$, then, $\eta = \eta ^V + \eta ^E$ with $\eta ^E\in \Phi _h^E$ and $\eta ^V\in {\mathfrak L}_{H}$. By using Corollary 4.3, properties (19–20) of the edge and vertex bilinear forms, as well as the definition of $q(\cdot ,\cdot )$, we get

$$\begin{aligned} s(\eta ,\eta )&\lesssim ||\eta ||_{\Phi _h,*}^2 = \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} | \eta ^E + \eta ^V |^2_{ H^{1/2}(\partial \Omega _\ell )} + \alpha \sum _{e\in {{\mathcal E}_h}} \Vert \mathtt {p}\, \mathtt {h}^{-1/2} [\![\,\eta \,]\!]\Vert _{L^2(e)}^2 \\&\lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} | \eta ^E |^2_{H^{1/2}(\partial \Omega _\ell )} + \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} | \eta ^V |^2_{ H^{1/2}(\partial \Omega _\ell )} + q(\eta ,\eta ) \\&\lesssim {\hat{s}}^E(\eta ^E,\eta ^E) + {\hat{s}}^V(\eta ^V,\eta ^V) + q(\eta ,\eta ), \end{aligned}$$

and hence

$$\begin{aligned} s(\eta ,\eta ) \lesssim {\hat{s}}(\eta ,\eta ) \quad \forall \, \eta \in \Phi _h. \end{aligned}$$

We next prove the lower bound. We shall show that

$$\begin{aligned} {\hat{s}}(\eta ,\eta ) \lesssim \max _\ell \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 s(\eta ,\eta ) \quad \forall \, \eta \in \Phi _h. \end{aligned}$$

(23)

For $\eta \in \Phi _h$, we have $\eta = \eta ^V + \eta ^E$ with $\eta ^E\in \Phi _h^E$ and $\eta ^V\in {\mathfrak L}_{H}$. Then, from the definition of ${\hat{s}}(\cdot ,\cdot )$ we have

$$\begin{aligned} \!\!{\hat{s}}(\eta ,\eta )&\!={\hat{s}}^E(\eta ^E,\eta ^E) \!+\! {\hat{s}}^V(\eta ^V,\eta ^V) \!+\! q(\eta ,\eta ) \\&\simeq \!\!\!\! \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}}\sum _{E\subset \partial {\Omega _{\ell }}} \Vert \eta ^E\Vert ^2_{H^{1/2}_{00}(E)} \!+\! \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}}\left| \eta ^V\right| ^2_{H^{1/2}(\partial {\Omega _{\ell }})} \!+\! \alpha \sum _{e\in {{\mathcal E}_h}} \Vert \mathtt {p}\,\mathtt {h}^{-1/2}[\![\,\eta \,]\!]\Vert _{L^2(e)}^2. \end{aligned}$$

Applying Lemma 3.2 with $\xi =\eta ^{E}$ and $\zeta _{L}=\eta ^{V}$, we obtain

$$\begin{aligned} \sum _{E\subset \partial {\Omega _{\ell }}} \Vert \eta ^E\Vert ^2_{H^{1/2}_{00}(E)} \lesssim \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 | \eta |^2_{H^{1/2}({\Omega _{\ell }})}, \end{aligned}$$

which implies

$$\begin{aligned} {\hat{s}}^E(\eta ^E,\eta ^E) \lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 | \eta |^2_{H^{1/2}(\partial {\Omega _{\ell }})} . \end{aligned}$$

To bound ${\hat{s}}^V(\eta ^V,\eta ^V)$, we apply Lemma 3.1 with $\zeta _{L}=\eta ^{V}$ and $\xi =\eta$, and we get

$$\begin{aligned} {\hat{s}}^V(\eta ^V,\eta ^V) \lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} | \eta ^V |^2_{H^{1/2}(\partial {\Omega _{\ell }})} \lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 | \eta |^2_{H^{1/2}(\partial {\Omega _{\ell }})}, \end{aligned}$$

and hence

$$\begin{aligned} {\hat{s}}^E(\eta ^E,\eta ^E) + {\hat{s}}^V(\eta ^V,\eta ^V) \lesssim \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 | \eta |^2_{H^{1/2}(\partial {\Omega _{\ell }})}. \end{aligned}$$

Adding now the term $\alpha \sum _{e\in {{\mathcal E}_h}}\Vert \mathtt {p}\mathtt {h}^{-1/2} [\![\,\eta \,]\!]\Vert _{L^2(e)}^{2}$ to both sides and recalling the definition of $q(\cdot ,\cdot )$ we have:

$$\begin{aligned} \!{\hat{s}}(\eta ,\eta )&= {\hat{s}}^E(\eta ^E,\eta ^E) \!\!+\!\! {\hat{s}}^V(\eta ^V,\eta ^V) \!+\!q(\eta ,\eta ) \\&\lesssim \max _\ell \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2\!\! \left( \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}} | \eta |^2_{H^{1/2}(\partial {\Omega _{\ell }})} \!+\! \alpha \sum _{e\in {{\mathcal E}_h}}\Vert \mathtt {p}\mathtt {h}^{\!-\!1/2} [\![\,\eta \,]\!]\Vert _{L^2(e)}^{2}\!\! \right) \\&= \max _\ell \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2 ||\eta ||_{\Phi _h,*}^2. \end{aligned}$$

Finally, using the norm equivalence given in Corollary 4.3, we obtain (23) and the proof of the Theorem is completed. $\square$

As a direct consequence of Theorem 4.4 we obtain the following estimate for the condition number of the preconditioned Schur complement.

Corollary 4.5

Let ${\mathbf S}$ and ${\mathbf P}$ be the matrix representation of the bilinear forms $s(\cdot ,\cdot )$ and ${\hat{s}}(\cdot ,\cdot )$, respectively. Then, the condition number of ${\mathbf P}^{-1} {\mathbf S}, \kappa ({\mathbf P}^{-1} {\mathbf S})$, satisfies

$$\begin{aligned} \kappa ({\mathbf P}^{-1} {\mathbf S}) \lesssim \max _\ell \left( 1 + \log \left( \frac{H_{\ell }\,p_{\ell }^2}{h_{\ell }} \right) \right) ^2. \end{aligned}$$

(24)

Unfortunately, the splitting (18) of $\Phi _h$ is not orthogonal with respect to the $\hat{s}(\cdot ,\cdot )$-inner product given in (21), and therefore the preconditioner based on $\hat{s}(\cdot ,\cdot )$ is not block diagonal, in contrast to what happens in the full conforming case. Furthermore the off-diagonal blocks in the preconditioner cannot be dropped without loosing the quasi-optimality. The reason is the presence of the $q(\cdot ,\cdot )$ bilinear form in the definition (21), and the fact that the two components in the splitting (18) of $\Phi _h$ scale differently in the seminorm that $q(\cdot ,\cdot )$ defines. In fact, it is possible to show that, if for some constant $\kappa (h)$, it holds

$$\begin{aligned} \Vert \eta ^V \Vert _{\Phi _h,*}^2\le \kappa (h)\Vert \eta \Vert _{\Phi _h,*}^2 \quad \forall \eta = \eta ^V+\eta ^E \in \Phi _h, \end{aligned}$$

(25)

then such $\kappa (h)$ must verify $\kappa (h)\gtrsim H/h$, which implies that, if we use a fully block diagonal preconditioner based on the splitting (18) of $\Phi _h$ an estimate of the form (23) would no be longer true. In order to show this, consider linear finite elements on quasi uniform meshes with meshsize $h$ in all subdomains, and let $\eta = (\eta ^\ell )_{\ell =1}^N$ be the function identically vanishing in all subdomains but one, say $\Omega _k$, and let $\eta ^k$ be equal to $1$ in a single vertex of $\Omega _k$ and zero at all other nodes. With this definition, we have $|[\![\,\eta \,]\!]| = |\eta ^k|$ on $\partial \Omega _k$ and $[\![\,\eta \,]\!]=0$ on $\Sigma \setminus \partial \Omega _k$. Then, by a direct calculation, and recalling the definition of the seminorm $|\cdot |_{*,{{\mathcal E}_h}}$ in (9), we easily see that

$$\begin{aligned} |\eta |^{2}_{*,{{\mathcal E}_h}}\simeq 1, \quad \text{ but } \quad |\eta ^{V}|^{2}_{*,{{\mathcal E}_h}}\simeq \frac{H_k}{h_k} \end{aligned}$$

or equivalently

$$\begin{aligned} q(\eta ^V,\eta ^V) \simeq \frac{H_k}{h_k}, \quad q(\eta ,\eta )\simeq 1. \end{aligned}$$

(26)

Therefore the energy of the coarse interpolant $\eta ^{V}$ exceeds that of $\eta$ by a factor of $H_k/h_k$. Hence, bounding $\eta ^{V}$ alone in the $\Vert \cdot \Vert _{\Phi _h,*}$-norm would result in an estimate of the type (25)

$$\begin{aligned} q(\eta ^V,\eta ^V) \lesssim \Vert \eta ^V \Vert _{\Phi _h,*}^2 \lesssim \kappa (h) q(\eta ,\eta ), \end{aligned}$$

(27)

which in view of (26) would imply

$$\begin{aligned} \kappa (h) \gtrsim \frac{H_k}{h_k}. \end{aligned}$$

Remark 4.1

We point out that the lack of the block-diagonal structure of the preconditioner associated to ${\hat{s}}(\cdot ,\cdot )$ defined in (21), will not affect its computational efficiency, see Sect. 6.

5 Realizing the preconditioner

We start by deriving the matrix form of the discrete Steklov–Poincaré operator $s(\cdot ,\cdot )$ defined in (17). We choose a Lagrangian nodal basis for the discrete space $X_{h}$, and we take care of numbering interior degrees of freedom first (grouped subdomain-wise), then edge degrees of freedom (grouped edge by edge and in such a way that the degrees of freedom corresponding to the common edge of two adjacent subdomains are ordered consecutively), and finally the degrees of freedom corresponding to the vertices of the subdomains.

We let $\mathtt {n}_{\mathtt {i}}, \mathtt {n}_{\mathtt {e}}$ and $\mathtt {n}_{\mathtt {v}}$ be the number of interior, edge and vertex degrees of freedom, respectively, and set $\mathtt {n}=\mathtt {n}_{\mathtt {e}}+\mathtt {n}_{\mathtt {v}}.$ Problem (7) is then reduced to looking for a vector ${{\mathbf u}}\in \mathbb {R}^{\mathtt {n}_\mathtt {i}+\mathtt {n}}$ with ${\mathbf u}=({\mathbf u}_{\mathtt {i}},{\mathbf u}_{\mathtt {e}}, {\mathbf u}_{\mathtt {v}})$ solution to a linear system of the following form

$$\begin{aligned} \begin{pmatrix} {\mathbf A}_{\mathtt {i}\mathtt {i}} &{} {\mathbf A}_{\mathtt {i}\mathtt {e}} &{} {\mathbf A}_{\mathtt {i}\mathtt {v}} \\ {\mathbf A}_{\mathtt {i}\mathtt {e}}^T &{} {\mathbf A}_{\mathtt {e}\mathtt {e}} &{} {\mathbf A}_{\mathtt {e}\mathtt {v}} \\ {\mathbf A}_{\mathtt {i}\mathtt {v}}^T &{} {\mathbf A}_{\mathtt {e}\mathtt {v}}^T &{} {\mathbf A}_{\mathtt {v}\mathtt {v}} \end{pmatrix} \begin{pmatrix} {\mathbf u}_{\mathtt {i}} \\ {\mathbf u}_{\mathtt {e}} \\ {\mathbf u}_{\mathtt {v}} \end{pmatrix} = \begin{pmatrix} {\mathbf F}_{\mathtt {i}} \\ {\mathbf F}_{\mathtt {e}} \\ {\mathbf F}_{\mathtt {v}} \end{pmatrix}. \end{aligned}$$

Here, ${\mathbf u}_{\mathtt {i}}\in \mathbb {R}^{\mathtt {n}_{\mathtt {i}}}$ (resp. ${\mathbf F}_{\mathtt {i}} \in \mathbb {R}^{\mathtt {n}_{\mathtt {i}}}$) represents the unknown (resp. the right hand side) component associated to interior nodes. Analogously, ${\mathbf u}_{\mathtt {e}}, {\mathbf F}_{\mathtt {e}} \in \mathbb {R}^{\mathtt {n}_{\mathtt {e}}}$ and ${\mathbf u}_{\mathtt {v}}, {\mathbf F}_{\mathtt {v}} \in \mathbb {R}^{\mathtt {n}_{\mathtt {v}}}$ are associated to edge and vertex nodes, respectively. We recall that for each vertex we have one degree of freedom for each of the subdomains sharing it. For each macro edge $E$, we will have two sets of nodes (some of them possibly physically coinciding) corresponding to the degrees of freedom of $\Phi _h^{\ell ^+}(E)$ and of $\Phi _h^{\ell ^-}(E)$.

As usual, we start by eliminating the interior degrees of freedom, to obtain the Schur complement system

$$\begin{aligned} {\mathbf S}\begin{pmatrix} {\mathbf u}_{\mathtt {e}} \\ {\mathbf u}_{\mathtt {v}} \end{pmatrix} ={\mathbf g}, \end{aligned}$$

with

$$\begin{aligned}&{\mathbf S}= \begin{pmatrix} {\mathbf A}_{\mathtt {e}\mathtt {e}} - {\mathbf A}_{\mathtt {i}\mathtt {e}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf A}_{\mathtt {i}\mathtt {e}} &{}\quad {\mathbf A}_{\mathtt {e}\mathtt {v}}-{\mathbf A}_{\mathtt {i}\mathtt {e}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf A}_{\mathtt {i}\mathtt {v}}\\ {\mathbf A}_{\mathtt {e}\mathtt {v}}^T-{\mathbf A}_{\mathtt {i}\mathtt {v}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf A}_{\mathtt {i}\mathtt {e}} &{}\quad {\mathbf A}_{\mathtt {v}\mathtt {v}}-{\mathbf A}_{\mathtt {i}\mathtt {v}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf A}_{\mathtt {i}\mathtt {v}} \end{pmatrix},&{\mathbf g}= \begin{pmatrix} {\mathbf F}_E - {\mathbf A}_{\mathtt {i}\mathtt {e}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf F}_{\mathtt {i}} \\ {\mathbf F}_V - {\mathbf A}_{\mathtt {i}\mathtt {v}}^T {\mathbf A}_{\mathtt {i}\mathtt {i}}^{-1} {\mathbf F}_{\mathtt {i}} \end{pmatrix}. \end{aligned}$$

The Schur complement ${\mathbf S}$ represents the matrix form of the Steklov–Poincaré operator $s(\cdot , \cdot )$. Remark that in practice we do not need to actually assemble ${\mathbf S}$ but only to be able to compute its action on vectors.

In order to implement the preconditioner introduced in the previous section we need to represent algebraically the splitting of the trace space given by (18). As defined in (3), we consider the space ${\mathfrak L}_{H}$ of functions that are linear on each subdomain edge, and introduce the matrix representation of the injection of ${\mathfrak L}_{H}$ into $\Phi _h$. More precisely, we let $\mathbf {\Xi }= \{ {\mathbf x}_{i}, \, i=1,\ldots ,\mathtt {n}_{\mathtt {e}}, \mathtt {n}_{\mathtt {e}}+1,\ldots , \mathtt {n}_{\mathtt {e}}+\mathtt {n}_{\mathtt {v}}\}$ be the set of edge and vertex nodes.

For any vertex node ${\mathbf x}_j, j=\mathtt {n}_{\mathtt {e}}+1,\ldots ,\mathtt {n}_{\mathtt {e}}+\mathtt {n}_{\mathtt {v}}$ , let $\varphi _{j}(\cdot )$ be the piecewise polynomial that is linear on each subdomain edge and that satisfies

$$\begin{aligned} \varphi _{j}({\mathbf x}_k)=\delta _{jk} \quad j,k=\mathtt {n}_{\mathtt {e}}+1,\ldots ,\mathtt {n}_{\mathtt {e}}+\mathtt {n}_{\mathtt {v}}. \end{aligned}$$

The matrix ${\mathbf R}^{T}\in \mathbb {R}^{\mathtt {n}\times \mathtt {n}_{\mathtt {v}}}$ realizing the linear interpolation of vertex values is then defined as

$$\begin{aligned} {\mathbf R}^{T}(i,j-\mathtt {n}_{\mathtt {e}}+1)=\varphi _{j}({\mathbf x}_{i}), \quad i=1,\ldots , \mathtt {n}_\mathtt {e}, \quad j=\mathtt {n}_{\mathtt {e}}+1,\ldots ,\mathtt {n}_{\mathtt {e}}+\mathtt {n}_{\mathtt {v}}. \end{aligned}$$

Next, we define a square matrix $\widetilde{{\mathbf R}}^{T}\in \mathbb {R}^{\mathtt {n}\times \mathtt {n}}$ as

$$\begin{aligned} \widetilde{{\mathbf R}}^{T} = \begin{pmatrix} {\mathbf I}_\mathtt {e}&{}\quad {\mathbf R}^T\\ \varvec{0} &{}\quad {\mathbf I}_\mathtt {v}\end{pmatrix} , \end{aligned}$$

${\mathbf I}_{\mathtt {e}} \in \mathbb {R}^{\mathtt {n}_{\mathtt {e}}\times \mathtt {n}_{\mathtt {e}}}$ and ${\mathbf I}_{\mathtt {v}} \in \mathbb {R}^{\mathtt {n}_{\mathtt {v}}\times \mathtt {n}_{\mathtt {v}}}$ being the identity matrices. Let now $\widetilde{{\mathbf S}}$ be the matrix obtained after applying the change of basis corresponding to switching from the standard nodal basis to the basis related to the splitting (18), that is

$$\begin{aligned} \widetilde{{\mathbf S}} = \widetilde{{\mathbf R}} {\mathbf S}\widetilde{{\mathbf R}}^T = \left( \begin{array}{ll} \widetilde{{\mathbf S}}_{\mathtt {e}\mathtt {e}} &{}\quad \widetilde{{\mathbf S}}_{\mathtt {v}\mathtt {e}}\\ \widetilde{{\mathbf S}}_{\mathtt {v}\mathtt {e}}^T &{}\quad \widetilde{{\mathbf S}}_{\mathtt {v}\mathtt {v}} \end{array}\right) . \end{aligned}$$

(28)

Our problem is then reduced to the solution of a transformed Schur complement system

$$\begin{aligned} \widetilde{{\mathbf S}} \, \widetilde{{\mathbf u}}= \widetilde{{\mathbf g}}, \end{aligned}$$

(29)

where $\widetilde{{\mathbf u}} = \widetilde{{\mathbf R}}^{-T} {\mathbf u}$ and $\widetilde{{\mathbf g}}= \widetilde{{\mathbf R}} {\mathbf g}$.

The preconditioner ${\mathbf P}$. The preconditioner ${\mathbf P}$ that we propose is obtained as the matrix counterpart of (21). In the literature it is possible to find different ways to build bilinear forms $\hat{s}^E(\cdot ,\cdot )$, $\hat{s}^V(\cdot ,\cdot )$ that satisfy (19) and (20), respectively. The choice that we make here for defining $\hat{s}^E(\cdot ,\cdot )$ is the one proposed in [21] and it is based on an equivalence result for the $H^{1/2}_{00}$ norm.

We revise now its construction. Let $l_0(\cdot )$ denote the discrete operator defined on $\Phi ^0_\ell (E)$ associated to the finite-dimensional approximation of $-\partial ^2/\partial s^2$ on $E$. It is defined by:

$$\begin{aligned} \langle l_0 \varphi ,\phi \rangle _E = (\varphi ^\prime ,\phi ^\prime )_E \quad \forall \phi \in \Phi ^0_\ell (E), \end{aligned}$$

(30)

where the prime superscript refers, as usual, to the derivative $\partial /\partial s$ with respect to the arc length $s$ on $E$. Notice that, since $l_0(\cdot )$ is symmetric and positive definite, its square root can be defined. Furthermore, it can be shown that for all $\varphi \in \Phi ^0_\ell (E)$

$$\begin{aligned} \Vert \varphi \Vert _{H^{1/2}_{00}(E)}\simeq (l_0^{1/2}\varphi , \varphi )^{1/2}_{E}, \end{aligned}$$

see [21].

Then, we define

$$\begin{aligned} {\hat{s}}^E(\eta ^E,\xi ^E) = \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}}\sum _{E\subset \partial {\Omega _{\ell }}} (l_0^{1/2}\eta ^E,\xi ^E)_{E}\; \quad \forall \, \eta ^E, \xi ^E \in \Phi ^0_\ell (E). \end{aligned}$$

(31)

For $\eta ^E\in \Phi ^0_\ell (E)$ we denote by $\varvec{\eta }^E$ its vector representation. Then, it can be verified that, for each subdomain edge $E\subset \partial {\Omega _{\ell }}$, we have (see [20] pag. 1110 and [35])

$$\begin{aligned} (l_0^{1/2}\eta ^E, \eta ^E)_{E} ={\varvec{\eta }^E}^T \widehat{\mathbf K}_E\varvec{\eta }^E \end{aligned}$$

where $\widehat{\mathbf K}_E= {\mathbf M}_E^{1/2} ( {\mathbf M}_E^{-1/2} {\mathbf R}_E {\mathbf M}_E^{-1/2})^{1/2} {\mathbf M}_E^{1/2}$, and where ${\mathbf M}_E$ and ${\mathbf R}_E$ are the mass and stiffness matrices associated to the discretization of the operator $-\hbox {d}^2/\hbox {ds}^2$ (in $\Phi ^0_\ell (E)$) with homogeneous Dirichlet boundary conditions at the extrema $a$ and $b$ of $E$.

Observe, that for each macro edge $E$ shared by the subdomains $\Omega _{\ell ^+}$ and $\Omega _{\ell ^-}$, $\widehat{\mathbf K}_E$ is a two by two block diagonal matrix of the form

$$\begin{aligned} \widehat{\mathbf K}_E = \begin{pmatrix} \widehat{\mathbf K}_E^{+} &{}\quad {\mathbf 0}\\ {\mathbf 0} &{}\quad \widehat{\mathbf K}_E^{-} \\ \end{pmatrix}, \end{aligned}$$

where $\widehat{\mathbf K}_E^\pm$ are the contributions from the subdomains $\Omega _{\ell ^\pm }$ sharing the macro-edge $E$. Due to the small dimension of $\widehat{\mathbf K}_E$, its computation can be performed by classical techniques such as the singular values decomposition (SVD), without influencing the efficiency of the whole process also for relatively high values of p.

As far as the vertex bilinear form $\hat{s}^V(\cdot ,\cdot )$ is concerned, we choose [21, 60]:

$$\begin{aligned} \hat{s}^V(\eta ^V,\eta ^V) = \sum _{{\Omega _{\ell }}\in {\mathcal T}_{H}}\int _{{\Omega _{\ell }}} \nabla (\mathcal{H}^\ell \eta ^\ell ) \cdot \nabla (\mathcal{H}^\ell \eta ^\ell ) \, \mathrm dx , \end{aligned}$$

(32)

where $\mathcal H(\cdot )$ denotes the continuous harmonic lifting. We observe that if the ${\Omega _{\ell }}$’s are rectangles, for $\eta \in {\mathfrak L}_{H}$ we have that $\mathcal{H}^\ell \eta ^\ell$ is the $\mathbb {Q}^{1}({\Omega _{\ell }})$ polynomial that coincides with $\eta ^\ell$ at the four vertices of ${\Omega _{\ell }}$. Computing $\hat{s}^V(\eta ^V,\xi ^V)$ for $\eta ^V,\xi ^V\in {\mathfrak L}_{H}$ is therefore easy, since it is reduced to compute the local (associated to ${\Omega _{\ell }}$) stiffness matrix for $\mathbb {Q}^{1}({\Omega _{\ell }})$ polynomials.

Remark 5.1

A similar construction also holds for quadrilaterals which are affine images of the unit square and for triangular domains. In fact, if ${\Omega _{\ell }}$ is a triangle then for $\eta \in {\mathfrak L}_{H}$ we have that $\mathcal{H}_h^\ell \eta ^\ell$ is the $\mathbb {P}^{1}({\Omega _{\ell }})$ function coinciding with $\eta ^\ell$ at the three vertices of ${\Omega _{\ell }}$. If ${\Omega _{\ell }}$ is the affine image of the unit square, we work by using the harmonic lifting on the reference element.

The preconditioner ${\mathbf P}$ can then be written as:

$$\begin{aligned} {\mathbf P}\!=\!\! \left( \begin{array}{ccccc} {\mathbf K}_{E_1} &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad {\mathbf K}_{E_2} &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 0&{}\quad \ddots &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0&{}\quad {\mathbf K}_{E_M}&{}\quad 0 \\ 0&{}\quad 0 &{}\quad 0 &{}\quad 0&{}\quad {\mathbf P}_{\mathtt {v}\mathtt {v}} \end{array} \right) \!+ \widetilde{{\mathbf Q}} \,, \end{aligned}$$

(33)

where for each macro edge $E_i$,

$$\begin{aligned} {\mathbf K}_{E_i}=\left( \begin{array}{cc} (\widehat{\mathbf K}_{E_i}^{+})^{1/2} &{}\quad 0 \\ 0 &{}\quad (\widehat{\mathbf K}_{E_i}^{-})^{1/2} \end{array} \right) . \end{aligned}$$

In (33) ${\mathbf P}_{\mathtt {v}\mathtt {v}}$ is defined as the matrix counterpart of (32) whereas

$$\begin{aligned} \widetilde{{\mathbf Q}}= \widetilde{{\mathbf R}} {\mathbf Q}\widetilde{{\mathbf R}}^T, \quad \widetilde{{\mathbf Q}} = \left( \begin{array}{cccc} {\mathbf Q}_{E_1} &{}\quad 0 &{}\quad 0 &{}\quad \widetilde{{\mathbf Q}}_{E_1 V} \\ 0 &{}\quad {\mathbf Q}_{E_2} &{}\quad 0 &{}\quad \widetilde{{\mathbf Q}}_{E_2 V} \\ 0 &{}\quad 0 &{}\quad \ddots &{}\quad \vdots \\ \widetilde{{\mathbf Q}}_{E_1 V}^T &{}\quad \widetilde{{\mathbf Q}}_{E_2 V}^T &{}\quad \cdots &{}\quad \widetilde{{\mathbf Q}}_{\mathtt {v}\mathtt {v}}, \end{array} \right) \end{aligned}$$

is the matrix counterpart of (22). Then ${\mathbf P}$ has the following structure

$$\begin{aligned} {\mathbf P}\!=\!\! \left( \begin{array}{cccc} {\mathbf K}_{E_1} + {\mathbf Q}_{E_1} &{} 0 &{}0&{}0\\ 0 &{}\quad \ddots &{}\quad 0&{}\quad 0\\ 0 &{}\quad 0&{}\quad {\mathbf K}_{E_M} + {\mathbf Q}_{E_M} &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad {\mathbf P}_{\mathtt {v}\mathtt {v}} + \widetilde{{\mathbf Q}}_{\mathtt {v}\mathtt {v}} \end{array} \right) + \left( \begin{array}{cccc} 0 &{}\quad 0 &{}\quad 0 &{}\quad \widetilde{{\mathbf Q}}_{E_1 V} \\ 0 &{}\quad \ddots &{}\quad 0 &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad \widetilde{{\mathbf Q}}_{E_M V} \\ \widetilde{{\mathbf Q}}_{E_1 V}^T &{} \cdots &{}\widetilde{{\mathbf Q}}_{E_M V}^T &{} 0,\quad \end{array} \right) .\nonumber \\ \end{aligned}$$

(34)

In view of definition (32) and of Remark 5.1, we observe that the coarse preconditioner ${\mathbf P}_{\mathtt {v}\mathtt {v}} + \widetilde{{\mathbf Q}}_{\mathtt {v}\mathtt {v}}$ is a standard discontinuous Galerkin problem defined on a coarse mesh with $P_1$ (respectively $Q_1$) elements in the case of triangular (respectively quadrilateral) subdomains. The global matrix ${\mathbf P}$ is a low-rank perturbation of an invertible block diagonal matrix. From (34) it can be easily seen that ${\mathbf P}$ has an “arrow” structure that makes it particularly well suited for direct methods. Indeed it is possible to show that for matrices with such a structure, LU decomposition has minimum fill-in and therefore is particularly efficient. The action of ${\mathbf P}^{-1}$ can therefore be easily computed, see e.g. [29, pag. 86] and [32, sec. 2.7.4, p. 83].

The preconditioner ${{\mathbf P}}_\star$. For comparison we introduce a preconditioner ${{\mathbf P}}_\star$ with the same block structure of ${\mathbf P}$ but with the elements of the non-zero blocks coinciding with the corresponding elements of $\widetilde{{\mathbf S}}$. We expect this preconditioner to be the best that can be done within the block structure that we want our preconditioner to have. In order to do so, we replace the $\widetilde{{\mathbf S}}_{\mathtt {e}\mathtt {e}}$ component of $\widetilde{{\mathbf S}}$ with the matrix obtained by dropping all couplings between the degrees of freedom corresponding to nodes belonging to different macro edges, and use the resulting matrix as preconditioner. More precisely, for any subdomain edge $E_{k}$ of the subdomain partition, $k=1,\ldots ,M$, let ${{\mathbf J}}_{k} \in \mathbb {R}^{\mathtt {n}_{\mathtt {e}}\times \mathtt {n}_{\mathtt {e}}}$ be the diagonal matrix that extract only the edge degrees of freedom belonging to the macro edge $E_{k}$, i.e.,

$$\begin{aligned} {{\mathbf J}}_{k}(i,j)= {\left\{ \begin{array}{ll} 1 &{} \hbox {if } i=j \hbox {and } {\mathbf x}_{i} \in E_{k}\\ 0 &{} \hbox {otherwise} \end{array}\right. } \quad i,j=1,\dots ,\mathtt {n}_{\mathtt {e}}. \end{aligned}$$

Then, we define

$$\begin{aligned} \widetilde{{\mathbf P}}_{\mathtt {e}\mathtt {e}} =\sum _{k=1}^{m} {{\mathbf J}}_{k}^{T} \widetilde{{\mathbf S}}_{\mathtt {e}\mathtt {e}} {{\mathbf J}}_{k}. \end{aligned}$$

This provides our preconditioner

$$\begin{aligned} {\mathbf P}_{\star } = \left( \begin{array}{cc} \widetilde{{\mathbf P}}_{\mathtt {e}\mathtt {e}} &{}\quad \widetilde{{\mathbf S}}_{\mathtt {e}\mathtt {v}} \\ \widetilde{{\mathbf S}}_{\mathtt {e}\mathtt {v}}^T &{}\quad \widetilde{{\mathbf S}}_{\mathtt {v}\mathtt {v}} \end{array}\right) . \end{aligned}$$

(35)

Building this preconditioner implies the need of assembling at least part of the Schur complement; this is quite expensive and therefore this preconditioner is not feasible in practical applications.

Remark 5.2

Note that we cannot drop the coupling between edge and vertex points, i.e. we cannot eliminate the off-diagonal blocks ${\mathbf Q}_{E_i V},{\mathbf Q}_{E_i V}^T$. Indeed, as already pointed out at the end of Sect. 4.2, with the splitting (18) of $\Phi _h$ it is not possible to design a block diagonal preconditioner without losing quasi-optimality. In Sect. 6 we will present some computations that show that the preconditioner

$$\begin{aligned} {\mathbf P}_{D} = \left( \begin{array}{cc} \widetilde{{\mathbf P}}_{\mathtt {e}\mathtt {e}} &{}\quad 0\\ 0 &{}\quad \widetilde{{\mathbf S}}_{\mathtt {v}\mathtt {v}} \end{array}\right) , \end{aligned}$$

(36)

is not optimal.

6 Numerical results

In this section we present some numerical experiments to validate the performance of the proposed preconditioners.

We set $\Omega =(0,1)^{2}$, and consider a sequence of subdomain partitions made of $N=4^{\ell }$ squares, $\ell =1,2,\ldots$, cf. Fig. 1a for $\ell =1,2,3,4$. For a given subdomain partition, $\ell =1,2,\ldots$, we have tested our preconditioners on a sequence of structured and unstructured triangular grids made of $n=2*4^{r}$ elements with $r=\ell ,\ell +1,\ldots$. Notice that the corresponding coarse and fine mesh sizes are given by $H \approx 2^{-\ell }, \ell =1,2,\ldots$, and $h \approx 2^{-r}, \quad r=\ell ,\ell +1,\ldots$, respectively.

Fig. 1

Top initial structured grids on subdomains partitions made by $N=4^{\ell }$ squares, $\ell =1,2,3,4$. Bottom first four refinement levels of unstructured grids on a subdomain partition made of $N=4$ squares

In Fig. 1a we have reported the initial structured grids, on subdomain partitions made by $N=4^{s}$ squares, $s=1,2,3,4$. Figure 1b shows the first four refinement levels of unstructured grids on a subdomain partition made of $N=4$ squares.

We solved the (preconditioned) linear system of equations by the Preconditioned Conjugate Gradient (PCG) method with a relative tolerance set equal to $10^{-9}$. The condition number of the (preconditioned) Schur complement matrix has been estimated within the PCG iteration by exploiting the analogies between the Lanczos technique and the PCG method (see [43, Sects. 9.3, 10.2] for more details). Finally, we choose the source term in problem (1) as $f(x,y)=1$, and set the penalty parameter $\alpha$ equal to $10$.

We first present some computations that show the behavior of the condition number of the Schur complement matrix ${\mathbf S}$, cf. (5).

In Fig. 2 (log-log scale) we report, for different subdomain partitions made by $N=4^{\ell }$ squares, $\ell =1,2,3,4,5$, the condition number estimate of the Schur complement matrix ${\mathbf S}$, $\kappa ({\mathbf S})$, as a function of the mesh-size $1/h$. We clearly observe that $\kappa ({\mathbf S})$ increases linearly as the mesh size $h$ goes to zero.

Fig. 2

Condition number estimate of the Schur complement matrix ${\mathbf S}$ versus $1/h$ on different subdomains partitions made by $N=4^{\ell }$ squares, $\ell =1,2,3,4,5$. Structured (left) and unstructured (right) triangular grids. Piecewise linear elements ($p=1$)

Next, we consider the preconditioned linear system of equations

$$\begin{aligned} {\mathbf P}^{-1}\widetilde{{\mathbf S}} \, \widetilde{{\mathbf u}}= {\mathbf P}^{-1} \widetilde{{\mathbf g}}, \end{aligned}$$

and test the performance of the preconditioners ${\mathbf P}$ and ${\mathbf P}_{\star }$ [cf. (33) and (35), respectively]. Throughout all our tests, the action of the preconditioner was computed with a direct solver.

In the first set of experiments, we consider piecewise linear elements ($p=1$), and compute the estimated condition number when varying the number of subdomains and the mesh size. Table 1 shows the behaviour of the estimated condition number when increasing the number of subdomains $N$ and the number of elements $n$ of the fine mesh. In Table 1 we also report (between parenthesis) the ratio between the condition number of the preconditioned system and $\left( 1+\log (H/h)\right) ^2$. These results have been obtained on a sequence of structured triangular grids like the ones shown in Fig. 1a. Results reported in Table 1 (top) refers to the performance of the preconditioner ${\mathbf P}$, whereas the analogous results obtained with the preconditioner ${\mathbf P}_{\star }$ are shown in Table 1 (bottom).

Table 1 Preconditioner ${\mathbf P}$ (top) and ${\mathbf P}_{\star }$ (bottom). Condition number estimates and ratio between the condition number of the preconditioned system and $\left( 1+\log (H/h)\right) ^2$ (between parenthesis). Structured triangular grids, piecewise linear elements ($p=1$)

We have repeated the same set of experiments on the sequence of unstructured triangular grids (cf. Fig. 1b). The computed results are shown in Table 2. As before, between parenthesis we report ratio between the condition number of the preconditioned system and $\left( 1+\log (H/h)\right) ^2$. As expected, a logarithmic growth is clearly observed for both preconditioner ${\mathbf P}$ and ${\mathbf P}_{\star }$.

Table 2 Preconditioner ${\mathbf P}$ (top) and ${\mathbf P}_{\star }$ (bottom). Condition number estimates and ratio between the condition number of the preconditioned system and $\left( 1+\log (H/h)\right) ^2$ (between parenthesis). Unstructured triangular grids, piecewise linear elements ($p=1$)

Next, once again with $p=1$, we present some computations that show that the preconditioner ${\mathbf P}_{D}$ defined in (36), i.e., the block-diagonal version of the preconditioner ${\mathbf P}_{\star }$, is not optimal (cf. Remark 5.2). More precisely, in Table 3 we report the estimated condition number of the preconditioned system for decreasing values of $H$ and $h$. Table 3 also shows (between parenthesis) the ratio between $\kappa ({\mathbf P}_{D} \widetilde{{\mathbf S}})$ and $Hh^{-1}$. We can clearly observe that on both structured and unstructured mesh configurations, the ratio between $\kappa ({\mathbf P}_{D} \widetilde{{\mathbf S}})$ and $Hh^{-1}$ remains substantially constant as $H$ and $h$ vary, indicating that the preconditioner ${\mathbf P}_{D}$ is not optimal.

Table 3 Preconditioner ${\mathbf P}_{D}$. Condition number estimates and ratio between $\kappa ({\mathbf P}_{D} \widetilde{{\mathbf S}})$ and $Hh^{-1}$ (between parenthesis). Structured (top) and unstructured (bottom) triangular grids, piecewise linear elements ($p=1$)

Finally, we present some computations obtained with high-order elements. As before, we consider a subdomain partition made of $N=4^{\ell }$ squares, $\ell =1,2,\ldots$, (cf. Fig. 1 for $\ell =1,2,3$). In this set of experiments, the subdomain partition coincides with the fine grid, i.e., $H=h$ , and on each element we consider the space of polynomials of degree $p=2,3,4,5,6$ in each coordinate direction. Table 4 shows the estimated condition number of the non-preconditioned Schur complement matrix and the CG iteration counts. We have run the same set of experiments employing the preconditioners ${\mathbf P}$ and ${\mathbf P}_{\star }$, and the results are reported in Table 5. We clearly observe that, as predicted, for a fixed mesh configuration the condition number of the preconditioned system grows logarithmically as the polynomial approximation degree increases.

Table 4 Condition number estimates $\kappa ({\mathbf S})$ and CG iteration counts (between parenthesis). Cartesian grids

Table 5 Preconditioner ${\mathbf P}$ (top), ${\mathbf P}_{\star }$ (bottom). Condition number estimates and ratio between the condition number of the preconditioned system and $\left( 1+\log (p^{2})\right) ^2$ (between parenthesis). Cartesian grids

Finally, we compare the performance of the proposed preconditioner with that of the nonoverlapping Schwarz preconditioner ${\mathbf P}_{\text {ad}}$ analyzed in [7] (cf. also [6]) for $h$-$p$ -discontinuous Galerkin finite element methods. More precisely, we define

$$\begin{aligned} {\mathbf P}_{\text {ad}} =\sum _{\ell =1}^N {\mathbf R}_\ell ^T {\mathbf A}_\ell ^{-1} {\mathbf R}_\ell + {\mathbf R}_0^T {\mathbf A}_0^{-1} {\mathbf R}_0. \end{aligned}$$

Here, for $\ell =1,\ldots , N$, the subdomains local solvers are defined as the restriction of the global bilinear form onto $X_h^\ell$, i.e., ${\mathbf A}_\ell ={\mathbf R}_\ell {\mathbf A}{\mathbf R}_\ell ^T$, being ${\mathbf R}_\ell ^T$ the extension by zero operator. For the coarse solver, we define the coarse space $X_0$ as the space of piecewise discontinuous bilinear functions defined on each subdomain $\Omega _\ell$, denote by ${\mathbf R}_0^T$ the classical injection operator from $X_0$ onto $X_h$, and set ${\mathbf A}_0={\mathbf R}_0{\mathbf A}{\mathbf R}_0^T$. As shown in [7], we expect that the condition number of the preconditioned system behaves as $\kappa ({\mathbf P}_{\text {ad}}{\mathbf A}) \lesssim p^2 Hh^{-1}$. We ran the same set of experiments as the previous one (that is the subdomain partition coincides with the fine grid), employing the nonoverlapping Schwarz preconditioner ${\mathbf P}_{\text {ad}}$. The numerical results are reported in Table 6 together with the ratio between $\kappa ({\mathbf P}_{\text {ad}}{\mathbf A})$ and $p^{2}$ (between parenthesis). Comparing these results with the analogous ones shown in Table 5, we can conclude that, for high order polynomial approximation degrees, the preconditioner ${\mathbf P}$ is more efficient than the nonoverlapping Schwarz solver.

Table 6 Nonoverlapping Schwarz preconditioner ${\mathbf P}_{\text {ad}}$. Condition number estimates and ratio between the condition number of the preconditioned system and $p^{2}$ (between parenthesis). Cartesian grids