A Uniform Additive Schwarz Preconditioner for High-Order Discontinuous Galerkin Approximations of Elliptic Problems

Abstract

In this paper we design and analyze a uniform preconditioner for a class of high-order Discontinuous Galerkin schemes. The preconditioner is based on a space splitting involving the high-order conforming subspace and results from the interpretation of the problem as a nearly-singular problem. We show that the proposed preconditioner exhibits spectral bounds that are uniform with respect to the discretization parameters, i.e., the mesh size, the polynomial degree and the penalization coefficient. The theoretical estimates obtained are supported by numerical tests.

1 Introduction

In the last years, the design of efficient solution techniques for the system of equations arising from Discontinuous Galerkin (DG) discretizations of elliptic partial differential equations has become an increasingly active field of research. On the one hand, DG methods are characterized by a great versatility in treating a variety of problems and handling, for instance, non-conforming grids and hp-adaptive strategies. On the other hand, the main drawback of DG methods is the larger number of degrees of freedom compared to (standard) conforming discretizations. In this respect, the case of high-order DG schemes is particularly representative, since the corresponding linear system of equations is very ill-conditioned: it can be proved that, for elliptic problems, the spectral condition number of the resulting stiffness matrix grows like $h^{-2}p^4$, h and p being the granularity of the underlying mesh and the polynomial approximation degree, respectively, cf. [6]. As a consequence, the design of effective tools for the solution of the linear system of equations arising from high-order DG discretizations becomes particularly challenging.

In the context of elliptic problems, Schwarz methods for low order DG schemes have been studied in [29], where overlapping and non-overlapping domain decomposition preconditioners are considered, and bounds of $O(H/\delta )$ and O(H / h), respectively, are obtained for the condition number of the preconditioned operator. Here H, h and $\delta$ stand for the granularity of the coarse and fine grids and the size of the overlap, respectively. Further extensions including inexact local solvers, and the extension of two-level Schwarz methods to advection–diffusion and fourth-order problems can be found in [1–3, 5, 12, 26, 30, 38]. In the field of Balancing Domain Decomposition (BDD) methods, a number of results exist in literature: exploiting a Neumann–Neumann type method, in [23, 24] a conforming discretization is used on each subdomain combined with interior penalty method on non-conforming boundaries, thus obtaining a bound for the condition number of the resulting preconditioner of $O((1-\log (H/h))^2)$. In [21], using the unified framework of [11] a BDDC method is designed and analyzed for a wide range of DG methods. The auxiliary space method (ASM) (see e.g., [32, 33, 41, 49]) is employed in the context of h-version DG methods to develop, for instance, the two-level preconditioners of [22] and the multilevel method of [15]. In both cases a stable splitting for the linear DG space is provided by a decomposition consisting of a conforming subspace and a correction, thus obtaining uniformly bounded preconditioners with respect to the mesh size.

All the previous results focus on low order (i.e., linear) DG methods. In the context of preconditioning high-order DG methods we mention [6, 8], where a class of non-overlapping Schwarz preconditioners is introduced, and [4], where a quasi-optimal (with respect to h and p) preconditioner is designed in the framework of substructuring methods for hp-Nitsche-type discretizations. Multigrid methods for high-order DG discretizations have been analyzed in [9], cf. also [7] for the extension to genereal polygonal/polyhedral meshes. A study of a BDDC scheme in the case of hp-spectral DG methods is addressed in [19], where the DG framework is reduced to the conforming one via the ASM. The ASM framework is employed also in [14], where the high-order conforming space is employed as auxiliary subspace, and a uniform multilevel preconditioner is designed for hp-DG spectral element methods in the case of locally varying polynomial degree. To the best of our knowledge, this preconditioner is the only uniform preconditioner designed for high-order DG discretizations. We note that, in the framework of high-order methods, the decomposition involving a conforming subspace was already employed in the case of a-posteriori error analysis, see for example [17, 35, 51]. In this paper, we address the issue of preconditioning high-order DG methods by exploiting this kind of space splitting based on a high-order conforming space and a correction. However, in our case the space decomposition is suggested by the interpretation of the high-order DG scheme in terms of a nearly-singular problem, cf. [39]. Even though the space decomposition is similar to that of [14], the preconditioner and the analysis we present differs considerably since here we employ the abstract framework of subspace correction methods provided by [50]. More precisely, we are able to show that a simple pointwise Jacobi method paired with an overlapping additive Schwarz method for the conforming subspace, gives uniform convergence with respect to all the discretization parameters, i.e., the mesh size, the polynomial order and the penalization coefficient appearing in the DG bilinear form.

The rest of the paper is organized as follows. In Sect. 2, we introduce the model problem and the corresponding discretization through a class of symmetric DG schemes. Section 3 is devoted to few auxiliary results regarding the Gauss–Legendre–Lobatto nodes, whose properties are fundamental to prove the stability of the space decomposition proposed in Sect. 4. The analysis of the preconditioner is presented in Sect. 5 and the theoretical results are supported by the numerical simulations of Sect. 6. We also test the performance of the proposed method in the case of more general diffusion equation, with isotropic discontinuous as well as anisotropic diffusion tensors.

2 Model Problem and High-Order DG Discretization

In this section we introduce the model problem and its discretization through several Discontinuous Galerkin schemes, see also [11].

Throughout the paper, we use the notation $x\lesssim y$ and $x\gtrsim y$ to denote the inequalities $x\le C y$ and $x\ge C y$, respectively, C being a positive constant independent of the discretization parameters. Moreover, $x\approx y$ means that there exist constants $C_1, C_2>0$ such that $C_1 y \le x \le C_2y$. When needed, the constants are written explicitly.

Given a convex polygonal/polyhedral domain $\Omega \in {\mathbb {R}}^d$, $d = 2,3$, and $f\in L^2(\Omega )$, we consider the following weak formulation of the Poisson problem with homogeneous Dirichlet boundary conditions: find $u\in V:= H^{1}_0(\Omega )$, such that

$$\begin{aligned} \int _\Omega \nabla u \cdot \nabla v\ dx =\int _\varOmega f v\ dx \, \qquad \forall v\in V. \end{aligned}$$

(1)

Let $\mathcal {T}_h$ denote a shape-regular, conforming, locally quasi-uniform partition of $\Omega$ into shape-regular elements $\kappa$ of diameter , and set . We also assume that each element $\kappa \in \mathcal {T}_h$ results from the mapping, through an affine operator ${\mathsf {F}}_\kappa$, of a reference element $\hat{\kappa }$, which is the open, unit d-hypercube in ${\mathbb {R}}^d$, $d=2,3$.

We denote by $\mathcal {F}_h^I$ and $\mathcal {F}_h^B$ the set of internal and boundary faces (for $d=2$ “face” means “edge”) of $\mathcal {T}_h$, respectively, and define . We associate to any a unit vector $\mathbf {n} _F$ orthogonal to the face itself and also denote by $\mathbf {n} _{F,\kappa }$ the outward normal vector to $F\subset \partial \kappa$ with respect to $\kappa$. We observe that for any , $\mathbf {n} _{F,\kappa }=\mathbf {n} _F$, since F belongs to a unique element. For any , we assume $\overline{F}=\partial \overline{\kappa ^+}\cap \partial \overline{\kappa ^-}$, where

$$\begin{aligned} \kappa ^+&:= \{\kappa \in \mathcal {T}_h: F\subset \partial \kappa ,\ \mathbf {n} _F\cdot \mathbf {n} _{F,\kappa }>0\},\\ \kappa ^-&:= \{\kappa \in \mathcal {T}_h: F\subset \partial \kappa ,\ \mathbf {n} _F\cdot \mathbf {n} _{F,\kappa }<0\}. \end{aligned}$$

For regular enough vector-valued and scalar functions $\varvec{\tau }$ and v, we denote by $\varvec{\tau }^\pm$ and $v^\pm$ the corresponding traces taken from the interior of $\kappa ^\pm$, respectively, and define the jumps and averages across the face as follows

For , the previous definitions reduce to and .

We now associate to the partition $\mathcal {T}_h$, the high-order Discontinuous Galerkin finite element space $V_{hp}$ defined as

with ${\mathbb {Q}}^p$ denoting the space of all tensor-product polynomials on $\hat{\kappa }$ of degree $p>1$ in each coordinate direction. We define the lifting operators and , where

for any $\varvec{\eta }\in [V_{hp}]^d$.

We then introduce the DG finite element formulation: find $u\in V_{hp}$ such that

(2)

with defined as

(3)

where $\theta =0$ for the SIPG method of [10] and $\theta = 1$ for the LDG method of [20]. With regard to the vector function $\varvec{\beta }$, we have $\varvec{\beta }=\varvec{0}$ for the SIPG method, while $\varvec{\beta }\in {\mathbb {R}}^d$ is a uniformly bounded (and possibly null) vector for the LDG method. The penalization function is defined as

being $\alpha \ge 1$ and $h_{\kappa ^{\pm }}$ the diameters of the neighboring elements $\kappa ^{\pm } \in \mathcal {T}_h$ sharing the face .

We endow the DG space $V_{hp}$ with the following norm

and state the following result, cf. [6, 36, 44, 45].

Lemma 1

The following results hold

(4)

For the SIPG formulation coercivity holds provided the penalization coefficient $\alpha$ is chosen large enough.

From Lemma 1 and using the Poincaré inequality for piecewise $H^1$ functions of [13], the following spectral bounds hold, cf. [6].

Lemma 2

For any $u\in V_{hp}$ it holds that

(5)

3 Gauss–Legendre–Lobatto Nodes and Quadrature Rule

In this section we provide some details regarding the choice of the basis functions spanning the space $V_{hp}$ and the corresponding degrees of freedom. On the reference d-hypercube $[-1,1]^d$, we choose the basis obtained by the tensor product of the one-dimensional Lagrange polynomials on the reference interval $[-1,1]$, based on Gauss–Legendre–Lobatto (GLL) nodes. We denote by $\mathcal {N}_ I (\hat{\kappa })$ ( $\mathcal {N}_ B (\hat{\kappa })$) the set of interior (boundary) nodes of $\hat{\kappa }$, and define $\mathcal {N}(\hat{\kappa }):= \mathcal {N}_ I (\hat{\kappa }) \cup \mathcal {N}_ B (\hat{\kappa })$. The analogous sets in the physical frame are denoted by $\mathcal {N}_ I (\kappa )$, $\mathcal {N}_ B (\kappa )$ and $\mathcal {N}(\kappa )$, where any ${\xi _p}\in \mathcal {N}(\kappa )$ is obtained by applying the linear mapping ${\mathsf {F}}_\kappa :\hat{\kappa } \rightarrow \kappa$ to the corresponding $\hat{\xi }_p\in \mathcal {N}(\hat{\kappa })$. The choice of GLL points as degrees of freedom allow us to exploit the properties of the associated quadrature rule. We recall that, given $(p+1)^d$ GLL quadrature nodes $\{\hat{\xi }_p\}$ and weights $\{\hat{{\mathsf {w}}}_{\xi _p}\}$, we have

$$\begin{aligned} \sum _{\hat{\xi }_p\in \mathcal {N}(\hat{\kappa })}v(\hat{\xi }_p)\hat{{\mathsf {w}}}_{\xi _p} = \int _{\hat{\kappa }} v\ dx\qquad \forall v\in {\mathbb {Q}}^{2p-1}(\hat{\kappa }), \end{aligned}$$

which implies that

$$\begin{aligned} \sum _{\hat{\xi }_p\in \mathcal {N}(\hat{\kappa })}v(\hat{\xi }_p)^2\hat{{\mathsf {w}}}_{\xi _p} \ne \int _{\hat{\kappa }} v^2\ dx\qquad \forall v\in {\mathbb {Q}}^{p}(\hat{\kappa }). \end{aligned}$$

However, by defining, for $v\in {\mathbb {Q}}^{p}(\hat{\kappa })$, the following norm

$$\begin{aligned} \Vert v\Vert _{0,p,\hat{\kappa }}^2 := \sum _{{\xi _p}\in \mathcal {N}(\hat{\kappa })}v(\hat{\xi }_p)^2\hat{{\mathsf {w}}}_{\xi _p}, \end{aligned}$$

it can be proved that

(6)

cf. [18, Section 5.3]. The same result holds for the physical frame $\kappa$, i.e., . Considering the Lagrange basis , , we can write any $v\in V_{hp}$ as

(7)

where we note that $v^{\xi _p} = v(\xi _p)\phi _{\xi _p}$.

Lemma 3

For any $v\in V_{hp}$, given the decomposition (7), the following equivalence holds

Proof

The proof can be restricted to the case of a single element $\kappa \in \mathcal {T}_h$. We write $v\in V_{hp}$ as in (7), and observe that

hence, by (6),

and the thesis follows summing over all $\kappa \in \mathcal {T}_h$. $\square$

4 Space Decomposition for High-Order DG Methods

The design of our preconditioner is based on a two-stage space decomposition: we first split the high-order DG space as $V_{hp}=V_{hp}^B+ V_{hp}^C$, with $V_{hp}^B$ denoting a proper subspace of $V_{hp}$, to be defined later, and $V_{hp}^C$ denoting the high-order conforming subspace. As a second step, both spaces are further decomposed to build two corresponding additive Schwarz methods in each of the subspaces. The final preconditioner on $V_{hp}$ is then obtained by combining the two subspace preconditioners. The first space splitting is suggested by the interpretation of the high-order DG formulation (2) as a nearly-singular problem. To present the motivation behind this choice, we briefly introduce the theoretical framework of [39] regarding space decomposition methods for this class of equations. Given a finite dimensional Hilbert space V, we consider the following problem: find ${U} \in V$ such that

$$\begin{aligned} A {U}=(A_0 + \epsilon A_1) {U} = {F}, \end{aligned}$$

(8)

where F is a given vector and where $A_0$ is symmetric and positive semi-definite and $A_1$ is symmetric and positive definite. As a consequence, if $\epsilon =0$, the problem is singular, but here we are interested in the case $\epsilon >0$ (with $\epsilon$ small, $\epsilon \ll 1$), i.e., (8) is nearly-singular. In general, the conditioning of problem (8) degenerates for decreasing $\epsilon$, and this affects the performance of standard preconditioned iterative methods, unless proper initial guess are chosen. In the framework of space decomposition methods, in order to obtain a $\epsilon$-uniform preconditioner, a key assumption on the space splitting $V_{hp} = \sum _{i=1}^N V_i$ is needed.

Assumption 1

([39]) The decomposition $V_{hp} = \sum _{i=1}^N V_i$ satisfies

$$\begin{aligned}\ker (A_0) = \sum _{i=1}^N (V_i\cap \ker (A_0)),\end{aligned}$$

where $\ker (A_0)$ is the kernel of $A_0$.

We now turn to our DG framework, and show that a high-order DG formulation can be indeed read as a nearly-singular problem with a suitable choice of $\epsilon$. For the sake of simplicity, and without any loss of generality, we retrieve Eq. (8) working directly on a bilinear form that is spectrally equivalent to . To this aim, let the bilinear forms , and be defined as

and let $A_\nabla$, $A_J$, and $\widetilde{A}$ be their corresponding operators. Clearly, $A_\nabla$ and $A_J$ are both symmetric and positive semi-definite, and $\widetilde{A}$ is symmetric and positive definite. Moreover, thanks to Lemma 1, and the local quasi-uniformity of the partition, the following spectral equivalence result holds

From the spectral equivalence shown above, it is immediate to conclude that any optimal preconditioner for $\widetilde{A}$ is automatically an optimal preconditioner for A. Therefore, in the following we focus our attention on the following problem

$$\begin{aligned} {\widetilde{A}\widetilde{u} = \left( A_\nabla +\frac{1}{\epsilon }A_J\right) \widetilde{u} = f}, \end{aligned}$$

(9)

with $\epsilon := h/(\alpha p^2)<1$. After some simple calculations, we can write (9) as

$$\begin{aligned} \left[ \epsilon (A_\nabla + A_J)+(1-\epsilon )A_J\right] {\widetilde{u}} = \epsilon {f}, \end{aligned}$$

which corresponds to (8) with $A_1=A_\nabla + A_J$ and $A_0=(1-\epsilon )A_J$. In order to obtain a suitable space splitting satisfying Assumption 1, we observe that, according to the definition above, the kernel of $A_0$ is given by the space of continuous polynomial functions of degree p vanishing on the boundary $\partial \Omega$. We then derive the first space decomposition

$$\begin{aligned} V_{hp} = V_{hp}^B + V_{hp}^C , \end{aligned}$$

(10)

with

i.e., $V_{hp}^{B}$ consists of the functions in $V_{hp}$ that are null in any degree of freedom in the interior of any $\kappa \in \mathcal {T}_h$. Moreover, we observe that $V_{hp}^B\subset V_{hp}$, and $V_{hp}^{B}\cap V_{hp}^{C}\subset V_{hp}^C$, hence Assumption 1 is satisfied by decomposition (10), which is the basis to develop the analysis of our preconditioner for problem (2).

4.1 Technical Results

In this subsection we present several results, which are fundamental for the forthcoming analysis. We introduce a suitable interpolation operator $\mathsf {Q_h}:V_{hp}\rightarrow V_{hp}^C$, consisting of the Oswald operator, cf. [16, 17, 28, 34, 37]. For any $v\in V_{hp}$, we can define on each $\kappa \in \mathcal {T}_h$ the action of the operator $\mathsf {Q_h}$, by prescribing the value of $\mathsf {Q_h} v$ in any ${\xi _p}\in \mathcal {N}(\kappa )$:

(11)

with . Note that from the above definition it follows that $v-\mathsf {Q_h} v\in V_{hp}^B$, for any $v\in V_{hp}$. In addition to the space of polynomials , we define as

and state the following trace and inverse trace inequalities.

Lemma 4

([17, Lemma 3.1]) The following trace and inverse trace inequalities hold

(12)

The next result is a keypoint for the forthcoming analysis, and can be found in [34] and [17, Lemma 3.2].

Lemma 5

([34] and [17, Lemma 3.2]) For any $v\in V_{hp}$, the following estimate holds

with .

Thanks to Lemma 5 we can prove the following theorem.

Theorem 1

For any $v\in V_{hp}$, it holds that

(13)

where is defined as in (11). Then the space decomposition defined in (10) is stable.

Proof

We observe that, from (5), the quasi-uniformity of the mesh and Lemma 5, we obtain

The upper bound (13) follows from the triangle inequality and the above estimate

For any $v\in V_{hp}$, we recall that $v-\mathsf {Q_h} v\in V_{hp}^B$, which implies

$\square$

5 Construction and Analysis of the Preconditioner

In this section we introduce our preconditioner and analyze the condition number of the preconditioned system. Employing the nomencalture of [48], the preconditioner is a parallel subspace correction method (also known as additive Schwarz preconditioner, see. e.g., [27, 40, 47]). Our construction uses a decomposition in two subspaces, cf. (10), and inexact subspace solvers. Each of the subspace solvers is a parallel subspace correction method itself.

5.1 Canonical Representation of a Parallel Subspace Correction Method

The main ingredients needed for the analysis of the parallel subspace correction (PSC) preconditioners are suitable space splittings and the corresponding subspace solvers (see [27, 31, 40, 46–48, 50]). In our analysis we use the notation and the general setting from [50]. We have the following abstract result.

Lemma 6

([50, Lemma 2.4]) Let V be a Hilbert space which is decomposed as $V = \sum _{i=1}^N V_i$, $V_i\subset V$, $i=1,\ldots ,N$, and $T_i:V\rightarrow V_i$, $i=1,\ldots , N$ be operators whose restrictions on $V_i$ are symmetric and positive definite. For $T:=\sum _{i=1}^N T_i$ the following identity holds

(14)

According to the above lemma, to show a bound on the condition number of the preconditioned system we need to show that there exist positive constants c and C such that

Remark 1

In many cases we have $T_i=P_i$, $i=1,\ldots ,N$, where $P_i:V\rightarrow V_i$ are the elliptic projections defined as follows: for $v\in V$, its projection $P_iv$ is the unique element of $V_i$ satisfying , for all $v_i\in V_i$. Note that by definition, $P_i$ is the identity on $V_i$, namely, $P_iv_i = v_i=P_i^{-1}v_i$, for all $v_i\in V_i$. Hence, for $T = \sum _{i=1}^N P_i$, the relation (14) gives

(15)

5.2 Space Splitting and Subspace Solvers

To fix the notation, let us point out that in what follows we use T (with subscript when necessary) to denote (sub)space solvers and preconditioners. Accordingly, P with subscript or superscript denotes elliptic projection on the corresponding subspace.

We now define the space splitting and the corresponding subspace solvers. We recall the space decomposition from Sect. 4, $V_{hp} = V_{hp}^B + V_{hp}^C$, where $V_{hp}^{B}$ are all functions in $V_{hp}$ for which the degrees of freedom in the interior of any vanish, and $V_{hp}^C$ is the space of high-order continuous polynomials vanishing on $\partial \Omega$. Note that $V_{hp}^{B}\cap V_{hp}^{C}\ne \{0\}$, and that $V_{hp}^B$ contains non-smooth and oscillatory functions, while $V_{hp}^C$ contains the smooth part of the space $V_{hp}$. Next, on each of these subspaces we define approximate solvers $T_B:V_{hp}\rightarrow V_{hp}^B$ and $T_C: V_{hp}\rightarrow V_{hp}^C$.

First, we decompose $V_{hp}^B$ as follows

(16)

where

The approximate solver on $V_B$ then is a simple Jacobi method, defined as

where $P_B$ and $P^{\xi _p}$ are the elliptic projections on $V_{hp}^B$ and $V^{\xi _p}$, respectively. Note that $T_B$ is defined on all of $V_{hp}$ and is also an isomorphism when restricted to $V_{hp}^B$, because the elliptic projection $P_B$ and $P^{\xi _p}$ are the identity on $V^B_{hp}$ and $V^{\xi _p}$, respectively. In addition, the splitting is a direct sum, and, hence, any $v\in V_{hp}^B$ is uniquely represented as , $v^{\xi _p}\in V^{\xi _p}$. Then, taking $P_i=P^{\xi _p}P_B: V_{hp}\rightarrow V^{\xi _p}$, from (15), we have

(17)

Next, we introduce the preconditioner $T_C$ on $V_{hp}^C$. This is the two-level overlapping additive Schwarz method introduced in [42, 43] for high-order conforming discretizations. If we denote by $N_V$ the number of interior vertices of $\mathcal {T}_h$, then this preconditioner corresponds to the following decomposition of $V_{hp}^C$:

$$\begin{aligned} V^C_{hp} = \sum _{i=0}^{N_V} V^C_i. \end{aligned}$$

(18)

Here $V_0^C$ is the (coarse) space of continuous piecewise linear functions on $\mathcal {T}_h$, and for $i=1,\ldots ,N_V$, $V^C_i := V^C_{hp}\cap H^{1}_0(\Omega _i)$, where $\Omega _i$ is the union of the elements sharing the i-th vertex (see Fig. 1 for a two-dimensional example). We recall that, in the case of Neumann and mixed boundary conditions, in order to obtain a uniform preconditioner, the decomposition (18) should be enriched with the subdomains associated to those vertices not lying on a Dirichlet boundary, see [42, 43] for details.

Fig. 1

Examples of subdomains in a two-dimensional setting

Then, for any $V^C_i$, $i = 0,\ldots ,N_V$, we denote by $P_i^C:V^C_{hp}\rightarrow V^C_i$ the elliptic projections on $V^C_i$ and define the two-level overlapping additive Schwarz operator as

$$\begin{aligned} T_C: V_{hp}\rightarrow V_{hp}^C, \quad T_C:=\left[ P_0^C+\sum _{i=1}^{N_V}P_i^C\right] P_C = (P_0 + P_V)P_C, \end{aligned}$$

(19)

where $P_C$ is the elliptic projection on $V_{hp}^C$. As in the case of $T_B$, we have that the restriction of $T_C$ on $V_{hp}^C$ is an isomorphism. In addition, from (15) with $P_i = P_i^CP_C:V_{hp}\rightarrow V_i^C$, we have

(20)

Observe that, especially for three dimensional problems, the dimension of the coarse space can be quite large, for example when the underlying mesh is very fine. In these cases, the solution of the corresponding coarse subproblem through a direct method can be computationally unfeasible. However, since the coarse level is the piece-wise linear conforming subspace, the associated linear system of equations can be efficiently solved by further preconditioning it with one of the efficient techniques already available for this class of problems, for example (Algebraic) Multigrid methods.

5.3 Definition of the Global Preconditioner

Finally, we define the global preconditioner on $V_{hp}$ by setting

$$\begin{aligned} T_{DG}:V_{hp}\rightarrow V_{hp}, \quad T_{DG}:=T_{B}+T_{C}, \end{aligned}$$

(21)

We remark that from Lemma 6, with $N=2$, $T_1=T_B$, $V_1=V_{hp}^B$, $T_2=T_C$, $V_2=V_{hp}^C$, we have

(22)

5.4 Condition Number Estimates: Subspace Solvers

We now show the estimates on the conditioning of the subspace solvers needed to bound the condition number of $T_{DG}$. The first result that we prove is on the conditioning of $T_B$.

Lemma 7

Let $T_{B}$ denote the Jacobi preconditioner defined in (5.2). Then there exist two positive constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$, independent of the granularity of the mesh h, the polynomial approximation degree p and the penalization coefficient $\alpha$, such that

(23)

(24)

with $\mathsf {Q_h} v$ defined in (11).

Proof

We refer to the space decomposition (16) and write

For the lower bound (23), we employ the eigenvalue estimate (5) and Lemma 3, thus obtaining

We now observe that for any , $v^{\xi _p}\in {\mathbb {Q}}^p_0(\kappa )$, and we can thus apply the inverse trace inequality (12) to obtain

Noting that , it follows that

and the thesis follows from the coercivity bound (4) and  (17). With regard to the upper bound (24), for the sake of simplicity we denote $w = (I-\mathsf {Q_h})v$, and observe that $w = (I-\mathsf {Q_h})w$. Since $w\in V_{hp}^B$, we write

and, from (17),

Applying again the estimate (5) and Lemma 3, we obtain

where the last steps follows from Lemma 5 and the quasi-uniformity of the mesh. $\square$

For the analysis of the additive preconditioner $T_C$ given in (19), we need several preliminary results (see [42, 43] for additional details). First of all, given the decomposition

$$\begin{aligned} v = v_0+\sum _{i=1}^{N_V} v_i\qquad \forall v\in V^C_{hp},\ v_0\in V_0^C,\ v_i\in V^C_i, \end{aligned}$$

(25)

we define the coarse function $v_0$ as the $L^2$-projection on the space $V_0^C$, i.e., with satisfying

(26)

(27)

for any $v\in H_0^1(\Omega )$. For any $i=1,\ldots ,N_V$, the functions $v_i$ appearing in (25) are defined as

$$\begin{aligned} v_i := I_p (\theta _i (v-v_0)), \end{aligned}$$

where $\theta _i$ is a proper partition of unity and $I_p$ is an interpolation operator, described in the following. For any $\Omega _i$, $i=1,\ldots ,N_V$, the partition of unity $\theta _i$ is such that $\theta _i\in V^C_{h1}$ and it can be defined by prescribing its values at the vertices $\{\mathsf {v} \}$ belonging to $\overline{\Omega }_i$, and imposing it to be zero on $\Omega {\setminus }\,\overline{\Omega }_i$, see Fig. 2 for $d=2$. More precisely,

with .

Fig. 2

Values of the partition of unity $\theta _i$ for $d=2$

It follows that:

$$\begin{aligned} \text {supp}(\theta _i) = \Omega _i,\qquad 0\le \theta _i\le 1,\qquad \sum _{i=1}^{N_V} \theta _i = 1,\qquad |\nabla \theta _i|\lesssim \frac{1}{h}. \end{aligned}$$

(28)

As interpolation operator $I_p$, we make use of the operator defined in [42, 43]: setting $z:=v-v_0$, we define

(29)

Notice that, despite defined locally, $I_p(\theta _i z)$ belongs to $V_{i}^C$ since the interelement continuity is guaranteed by the fact that the $(p+1)^{d-1}$ GLL points on a face uniquely determine a tensor product polynomial of degree p defined on that face. The following result holds.

Lemma 8

([42, Lemma 3.1, Lemma 3.3]) The interpolation operator $I_p:{\mathbb {Q}}^{p+1}(\hat{\kappa })\rightarrow {\mathbb {Q}}^{p}(\hat{\kappa })$, defined in (29), is bounded uniformly in the $H^1$ seminorm, i.e.,

(30)

Once the partition of unity and the interpolation operator are defined, we are able to complete the analysis of $T_C$. In analogy to Lemma 7, which is based on (17), we now use  (20) and the above auxiliary results to show the following lemma.

Lemma 9

Let $T_C$ denote the two-level overlapping additive Schwarz preconditioner defined in (19). Then there exist two positive constants ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$, independent of the discretization parameters, i.e., the granularity of the mesh h and the polynomial approximation degree p, such that

(31)

(32)

for any $v\in V_{hp}^C$.

Proof

We first prove the lower bound (31), and given the decomposition (25), we can write

We now note that only if $i=j$ and $\Omega _i\cap \Omega _j\ne \emptyset$, and since each $\Omega _i$ is overlapped by a limited number of neighboring subdomains, we conclude that

Inequality (31) follows from the bound above and (20), denoting with ${\mathsf {C}}_1^C$ the hidden constant. Note that, from (20), the upper bound  (32) is proved provided the following inequality holds

(33)

We recall that , and from (27) it follows that

(34)

For $i = 1,\ldots , N_V$, we have $v_i = I_p(\theta _i z)$, with $z=v-v_0$, and by (30), we obtain

for any . By (28) it holds that

$$\begin{aligned} |\nabla \theta _i|\lesssim \frac{1}{h},\qquad \Vert \theta _i\Vert _{L^\infty }\le 1, \end{aligned}$$

hence,

On any element $\kappa '$, a limited number of components $v_i$ are different from zero (at most four for $d=2$, and eight for $d=3$), which implies that we can sum over all the components $v_i$, $i = 1,\ldots ,N_V$, and then over all the elements, thus obtaining

where the last step follows from (26) and  (27). The addition of the above result and (34), gives (33), denoting with ${\mathsf {C}}_2^C$ the resulting hidden constant. $\square$

5.5 Condition Number Estimates: Global Preconditioner

We are now ready to prove the main result of the paper regarding the condition number of the preconditioned problem.

Theorem 2

Let $T_{DG}$ be defined as in (21). Then, for any $v\in V_{hp}$, it holds that

(35)

where the hidden constants are independent of the discretization parameters, i.e., the mesh size h, the polynomial approximation degree p, and the penalization coefficient $\alpha$.

Before proving Theorem 2, we note the following: As the operator $T_{DG}$ is symmetric and positive definite, from Theorem 2 it immediately follows that the spectral condition number of the preconditioned operator $T_{DG}$

$$\begin{aligned} \kappa (T_{DG}):=\frac{\lambda _{\text {max}}(T_{DG})}{\lambda _{\text {min}}(T_{DG})} \end{aligned}$$

(36)

is uniformly bounded, i.e. $\kappa (T_{DG})\lesssim 1$, where the hidden constant is independent of the the mesh size h, the polynomial approximation degree p, and the penalization coefficient $\alpha$. In (36) $\lambda _{\text {max}}(T_{DG})$ and $\lambda _{\text {min}}(T_{DG})$ denotes the extremal eigenvalues of $T_{DG}$ defined as

As a consequence, the conjugate gradient algorithm can be employed to solve the preconditioned linear system of equations and the number of iterations needed to reduce the norm of the (relative) residual below a given threshold is expected to be uniformly constant independently of the size of the underlying matrix, see, e.g., [46] for more details.

Proof

(Proof of Theorem 2). To prove the upper bound, we first consider the identity  (22). Recalling that, by definition (11), $v-\mathsf {Q_h} v\in V_{hp}^B$, for any $v\in V_{hp}$, we obtain

From the bounds (24) and  (32) for $\mathsf {Q_h} v$, it follows that

where the last step follows from (13). The lower bound follows from (22), the bounds (23) and (31), and a triangle inequality

$\square$

6 Numerical Experiments

In this section we present some numerical tests to verify the theoretical estimates provided in Lemma 7, Lemma 9 and Theorem 2, as well as to test the performance of our preconditioner in the case of a variable diffusion tensor. To this aim we present several tests with anisotropies and/or heterogeneities in the diffusion coefficients following the lines of those proposed in [25]. As these tests show, the preconditioner is robust for problems with tensor coefficients, even when strong anisotropies are presented, as long as the variation of these coefficients throughout the domain is bounded. As expected, a deterioration in the condition number of the preconditioned system is observed when the coefficients have large jumps. This behavior is due to the use of a standard conforming coarse space. More complex constructions of coarse spaces depending on the coefficient variation are possible, but they are beyond the scope of our considerations here.

Before presenting the numerical results assessing the practical performance of our preconditioner, we briefly provide some implementation details. The preconditioner is composed by the sum of two operators: i) a (block) Jacobi preconditioner acting on the degrees of freedom (dofs) of the DG space with the exclusion of the dofs associated to the interior of the elements (i.e., the bubble modes) and ii) a classical two-level overlapping Schwarz preconditioner acting on the space of high-order continuous polynomials vanishing on $\partial \varOmega$. Implementing the action of the first operator is straightforward as it requires only a multiplication by a (block) diagonal matrix associated to the vertex/edge/face dofs. Regarding the action of the second operator, associated to the smooth part of the space $V_{hp}$, it is easily seen that the computationally demanding part is the construction of the projector from the discontinuous space $V_{hp}$ to the conforming space. For example, in two-dimensions, it consists in constructing a matrix that averages the values at the vertex and edge dofs. Clearly, the projection matrix has a highly sparse structure. Once the conforming stiffness matrix is available, it is enough to apply the classical overlapping Schwarz preconditioner of [42, 43], with coarse space from piecewise continuous linear polynomials, for which efficient implementations are available.

Finally, let us briefly comment on the actual cost of the proposed preconditioner relative to other strategies. Since the proposed approach is based on an overlapping partition of the computational domain, each application of the preconditioner is more expensive than the Schwarz preconditioners proposed in [1, 2, 6, 8], that feature a high-level of scalability and load balancing because they are built using a non-overlapping approach. On the other hand, our preconditioner is uniform with respect to the polynomial approximation degree p whereas the preconditioner of [6, 8] exhibit spectral bounds that depend on p.

6.1 Example 1

We consider problem (2) in the two dimensional case with $\Omega =(-1,1)^2$ and SIPG and LDG discretizations. For the first experiment, we set $h = 0.0625$, the penalization parameter $\alpha = 10$ and $\varvec{\beta }=\varvec{1}$ for the LDG method. In Table 1, we show the numerical evaluation of the constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ of Lemma 7 and ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ of Lemma 9, as a function of the polynomial order employed in the discretization: the constants are independent of p, as expected from theory. With regard to the constants ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$, we observe that the values are the same for both the SIPG and LDG methods, since the preconditioner on the conforming subspace reduces to the same operator regardless of the DG scheme employed.

Table 1 Left and middle: numerical evaluation of the constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ of Lemma 7 as a function of p for the SIPG and LDG methods; right: numerical evaluation of the constants ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ of Lemma 9 as a function of p

Table 2 shows a comparison of the spectral condition number of the original system (${\mathsf {K}}(A)$) and of the preconditioned one (${\mathsf {K}}(T_{DG})$). While the former grows as $p^4$, cf. [6], the latter is constant with p, as stated in (35). The theoretical results are further confirmed by the number of iterations $N_{iter}^{PCG}$ and $N_{iter}^{CG}$ of the Preconditioned Conjugate Gradient (PCG) and the Conjugate Gradient (CG), respectively, needed to reduce the initial relative residual of a factor of $10^{-8}$.

Table 2 Condition number of the unpreconditioned (${\mathsf {K}}(A)$) and preconditioned (${\mathsf {K}}(T_{DG})$) linear systems of equations and corresponding CG ($N_{iter}^{CG}$) and PCG ($N_{iter}^{PCG}$) iteration counts as a function of p for the SIPG and LDG methods

In the second numerical experiment, we consider the same test case presented above, but we now fix the polynomial approximation degree $p=6$ and decrease the mesh-size h. The computed results obtained with the SIPG ($\varvec{\beta }=\varvec{0}$, $\alpha =10$) and LDG ($\varvec{\beta }=\varvec{1}$, $\alpha =10$) methods are shown in Table 3. For the sake of comparison, Table 3 also shows the computed spectral condition numbers of the unpreconditioned system as well as the number of CG iterations needed to reduced the relative residual below the given tolerance $10^{-8}$. As predicted from our theoretical results, the condition number of the preconditioned system is insensitive to the the mesh-size, whereas ${\mathsf {K}}(A)$ grows quadratically as h tends to zero.

Table 3 Condition number of the unpreconditioned (${\mathsf {K}}(A)$) and preconditioned (${\mathsf {K}}(T_{DG})$) linear systems of equations and corresponding CG ($N_{iter}^{CG}$) and PCG ($N_{iter}^{PCG}$) iteration counts as a function of the mesh-size h for the SIPG and LDG methods for $p=6$

The last numerical experiment of this section aims at verifying the uniformity of the proposed preconditioner with respect to the penalization coefficient $\alpha$. In this case, we consider the same test case presented above, but we now fix the polynomial approximation degree $p=2$ and increase $\alpha$. The numerical data obtained are reported in Table 4: as done before, we compare the spectral condition numbers of the unpreconditioned and preconditioned systems and the iteration counts of the CG and PCG methods. As predicted from theory, while ${\mathsf {K}}(A)$ grows like $\alpha$, the values of ${\mathsf {K}}(T_{DG})$ are constant.

Table 4 Condition number of the unpreconditioned (${\mathsf {K}}(A)$) and preconditioned (${\mathsf {K}}(T_{DG})$) linear systems of equations and corresponding CG ($N_{iter}^{CG}$) and PCG ($N_{iter}^{PCG}$) iteration counts as a function of $\alpha$ for the SIPG and LDG methods

6.2 Example 2

We now address a more general model problem by introducing a diffusion tensor $\rho$ in (1). We then rewrite the weak formulation (1) as follows: find $u\in V$, such that

where, for simplicity we assume that

with $\rho _{11}(x)$ and $\rho _{22}(x)$ (possibly discontinuous) positive constants a.e. in $\varOmega$. We also assume that there exists an initial partition ${\mathcal {T}}_{h_0}$ such that the (possible) discontinuities of $\rho _{11}(x)$ and $\rho _{22}(x)$ are aligned with ${\mathcal {T}}_{h_0}$. We then modify the bilinear form (3) as follows, restricting, for simplicity, ourselves to the SIPG bilinear form, i.e., $\theta =0$ and $\varvec{\beta }=\varvec{0}$,

where, on each face , is defined as

see, e.g., [25]. We then consider the following DG formulation:

(37)

The numerical results reported in this section have been obtained choosing piecewise quadratic elements, i.e., $p=2$ and the penalization parameter $\alpha = 10$.

For the first test we choose an elementwise discontinuous isotropic diffusion coefficient, i.e.

$$\begin{aligned} \rho (x)= \begin{bmatrix} \rho _{11}(x)&0\\ 0&{\rho _{11}}(x) \end{bmatrix}, \end{aligned}$$

where $\rho _{11}(x)$ follows an elementwise red–black partitioning of the computational domain, which means $\rho _{11}=1$ in red regions and $\rho _{11} = 10^{\gamma }$, $\gamma = 0,1,\ldots ,7$, in the black ones. In Fig. 3, we numerically evaluate the constant appearing in the inequality

(38)

which is the analogous of (13), and observe that the presence of a discontinuous diffusion coefficient introduces a linear dependence of ${\mathsf {C}}_{{{\mathsf {Q}}_h}}$ on the ratio between the maximum and minimum value of $\rho$. In Table 5 we report the estimated values of the constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ appearing in Lemma 7, and ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ appearing in Lemma 9, respectively, as a function of $\rho _{11}$. Here, we note that the two preconditioners, built on the corresponding subspaces, are robust with respect to the contrast in the diffusion tensor. From the results obtained by these numerical tests we can conclude that the condition number of the preconditioned operator $T_{DG}$ depends linearly on the jumps of the diffusion coefficient, as further confirmed by the numerical tests reported in Table 6 where the spectral condition number of $T_{DG}$ as well as the PCG iteration counts as a function of $\rho _{11}$ are shown. For the sake of comparison, the same quantities are also shown for the unpreconditioned system, showing that, as expected also the unpreconditioned operator has a spectral condition number that depends linearly on the contrast of the diffusion coefficient.

Fig. 3

Numerical evaluation of the constant ${\mathsf {C}}_{{{\mathsf {Q}}_h}}$ in (38) as a function of $\rho _{11}$. SIPG method (37) ($p=2$, $\alpha =10$)

Table 5 Left: numerical evaluation of the constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ of Lemma 7 as a function of $\rho _{11}$ for the SIPG method (37) ($p=2$, $\alpha =10$); right: numerical evaluation of the constants ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ of Lemma 9 as a function of $\rho _{11}$

Table 6 Condition number of the unpreconditioned (${\mathsf {K}}(A)$) and preconditioned (${\mathsf {K}}(T_{DG})$) linear systems of equations and corresponding CG ($N_{iter}^{CG}$) and PCG ($N_{iter}^{PCG}$) iteration counts as a function of $\rho _{11}$ for the SIPG method (37) ($p=2$, $\alpha =10$)

Next, we investigate the behavior of the proposed technique whenever the diffusion tensor features a strong anisotropy. For this set of experiments we set

$$\begin{aligned} \rho (x) = \begin{bmatrix} 1&0\\ 0&\rho _{22} \end{bmatrix}, \end{aligned}$$

where $\rho _{22}$ is a positive constant over the whole computational domain. We have repeated the same set of experiments as before, again with $p=2$. In Fig. 4 we report the estimated constant ${\mathsf {C}}_{{{\mathsf {Q}}_h}}$ in (38) as a function of $\rho _{22} = 10^{\gamma }$, $\gamma = 0,1,\ldots ,7$. We observe that ${\mathsf {C}}_{{{\mathsf {Q}}_h}}$ seems to be independent of the anisotropy of $\rho (x)$.

Fig. 4

Numerical evaluation of the constant ${\mathsf {C}}_{{{\mathsf {Q}}_h}}$ in (38) as a function of $\rho _{22}$. SIPG method (37) ($p=2$, $\alpha =10$)

The computed constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ of Lemma 7 and ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ of Lemma 9 as a function of $\rho _{22}$ are reported in Table 7. We note that ${\mathsf {C}}_2^J$ and ${\mathsf {C}}_2^C$ seem to be asymptotically independent of $\rho _{22}$.

Table 7 Left: numerical evaluation of the constants ${\mathsf {C}}_1^J$ and ${\mathsf {C}}_2^J$ of Lemma 7 as a function of $\rho _{22}$ for the SIPG method in (37) ($p=2$); right: numerical evaluation of the constants ${\mathsf {C}}_1^C$ and ${\mathsf {C}}_2^C$ of Lemma 9 as a function of $\rho _{22}$

Table 8 Condition number of the unpreconditioned (${\mathsf {K}}(A)$) and preconditioned (${\mathsf {K}}(T_{DG})$) linear systems of equations and corresponding CG ($N_{iter}^{CG}$) and PCG ($N_{iter}^{PCG}$) iteration counts as a function of $\rho _{22}$ for the SIPG method

The numerical data shown in Fig. 4 and Table 7 again suggest the expected behavior of the final preconditioner. Indeed the condition number ${\mathsf {K}}(T_{DG})$ seems to be asymptotically constant as $\rho _{22}$ grows, as confirmed by the results reported in Table 8. Notice however that also the unpreconditioned DG discretization seems to be itself asymptotically robust with respect to the anisotropy.