A Domain Decomposition Method for Discretization of Multiscale Elliptic Problems by Discontinuous Galerkin Method

Abstract

In this paper boundary value problems for second order elliptic equations with highly discontinuous coefficients are considered on a 2D polygonal region. The problems are discretized by a discontinuous Galerkin (DG) with finite element method (FEM) on triangular elements using piecewise linear functions.

The goal is to design and analyze a parallel algorithm for solving the discrete problem whose rate of convergence is independent of the jumps of the coefficients. The method discussed is an additive Schwarz method (ASM) which belongs to a class of domain decomposition methods and is one of the most efficient parallel algorithm for solving discretizations of PDEs.

It turns out that the convergence of the method presented here is almost optimal and only weakly depends on the jumps of coefficients. The suggested method is very well suited for parallel computations.

This work was supported in part by the Polish National Science Centre Grant no 2011/01/B/ST1/01179.

1 Introduction

We consider boundary value problems (BVPs) for second order elliptic equations with highly discontinuous coefficients posed on a 2D polygonal region. The problem is discretized by a discontinuous Galerkin (DG) method with FEM on triangular elements and piecewise linear functions, see [1, 3], and references therein. The goal of this paper is to design and analyze a parallel algorithm for solving the discrete problem with rate of convergence independent of the jumps of coefficients.

The proposed algorithm is an additive Schwarz method (ASM) with overlaps and belongs to a class of domain decomposition methods and it is one of the most efficient parallel algorithms for solving discretizations of PDEs, see [5].

In the paper the results obtained in [4] for continuous piecewise linear finite element discretization are extended to DG discretization. They are more general comparising to the results of [4].

The presented ASM is two-level with a special coarse space defined on large triangles of coarse triangulation, i.e. a multiscale coarse space. This is a space of continuous functions which are discrete harmonic on edges of the coarse triangles and inside of them in the sense of corresponding bilinear forms. The local spaces are defined in a standard way, on the fine triangulation, on extensions of coarse triangles; these spaces contain discontinuous functions. For literature on the topic see [4, 5], and references therein.

It turns out that the convergence of the discussed ASM is dependent of the jumps of the coefficients on the boundary of coarse triangles only. For some distributions of jumps, the convergence of the ASM is also independent of these jumps.

The paper is organized as follows. In Sect. 2, differential and discrete problems are formulated. In Sect. 3, a two level ASM for solving the discrete problem is designed and analyzed. The main result is Theorem 5, which guarantees the optimality of the method. Section 4 is devoted to an implementation of the method discussed.

2 Differential and Discrete DG Problems

We consider the following elliptic problem:

Find $u^* \in H^1_0(\varOmega )$ such that

$$\begin{aligned} a(u^*,v) = f(v), \qquad \forall v \in H^1_0(\varOmega ) \end{aligned}$$

(1)

where

$$ a(u,v) = \int _{\varOmega } \rho (x)\nabla u \cdot \nabla v dx, \qquad f(v) = \int _{\varOmega }f v dx. $$

We assume that $\varOmega$ is a polygonal region, $f \in L^2(\varOmega )$ and $\rho (x) \ge \rho _0 > 0$, and $\rho \in L^{\infty }(\varOmega )$. Under these assumptions problem (1) is well posed.

We will also assume that $\rho _0 \ge 1$. This can be fulfilled by scaling (1). It is used in the analysis of preconditioner discussed in Sect. 3.

Let $\mathcal{{T}}^h(\varOmega )$ be a triangulation of $\varOmega$ with triangular elements $K_i$ and the mesh parameter $h$. It is constructed as a refinement of the coarse triangulation of $\varOmega$ consisting of large triangles $\varOmega _l$ of diameter $H_l, l = 1,\cdots ,L, H_l = diam (\varOmega _l)$ and $H=\max H_l$. The refinement procedure is repeated several times, where one step of the process is to split each triangle into four smaller ones, obtained by connecting the midpoints of its edges. Let $X_i(K_i)$ denote a space of linear functions on $K_i$ and

$$ X_h(\varOmega ) = \Pi ^N_{i=1}X_i(K_i), \qquad \bar{\varOmega } = \cup ^N_{i=1}K_i, $$

be the space in which problem (1) is approximated. Note that $X_h(\varOmega )\not \subset H^1(\varOmega )$ and its elements do not vanish on $\partial \varOmega$, in general.

The discrete problem for (1) is of the form:

Find $u^*_h\in X_h(\varOmega )$ such that

$$\begin{aligned} \hat{a}_h(u^*_h,v_h)=f(v_h), \qquad v_h\in X_h(\varOmega ), \end{aligned}$$

(2)

where for $u,v \in X_h(\varOmega ), u=\{u_i\}^N_{i=1}, u_i\in X_i(K_i),$

$$ \hat{a}_h(u,v)=\sum ^N_{i=1} \hat{a}_i(u,v), \qquad f(v)= \sum ^N_{i=1} \int _{K_i}fv_idx. $$

Since we use linear elements, we can assume without loss of generality that $\rho _{|_{K_i}} = \rho _i$ is constant on $K_i$. Here

$$ \hat{a}_i(u,v)=a_i(u,v)+s_i(u,v)+p_i(u,v), $$

$$ a_i(u,v)=\int _{K_i}\rho _i\nabla u_i \cdot \nabla v_i dx, $$

$$ s_i(u,v) = \sum _{E_{ij}\subset \partial K_i} \int _{E_{ij}} \omega _{ij}[n^T_i \rho _i\nabla u_i(v_j - v_i)+ n^T_i \rho _i \nabla v_i(u_j-u_i)]\,ds, $$

$$ p_i(u,v)= \sum _{E_{ij} \subset \partial K_i} \frac{\sigma }{h} \int _{E_{ij}}\gamma _{ij}(u_i-u_j)(v_i-v_j)\,ds $$

where $E_{ij}=E_{ji}=\partial K_i \cap \partial K_j, E_{ij} \subset \partial K_i$ and $E_{ji} \subset \partial K_j$; $n_i = n_{E_{ij}}$ is the unit normal vector to $E_{ij}$ pointing from $K_i$ to $K_j$;

$$ \omega _{ij} \equiv \omega _{E_{ij}} = \frac{\rho _j}{\rho _i+\rho _j},\qquad \omega _{ji} \equiv \omega _{E_{ji}} = \frac{\rho _i}{\rho _i+\rho _j} $$

and

$$ \gamma _{ij} \equiv \gamma _{E_{ij}} = \frac{2\rho _i \rho _j}{\rho _i + \rho _j}; $$

$\sigma$ is a positive penalty parameter (sufficiently large, see below Lemma 1). For boundary egdes these definitions extend straightforwardly, setting for $E_{ij} \subset \partial \varOmega$: $\omega _{ij} = 1$, $\omega _{ji} = 0$, $v_j = u_j = 0$ and $\gamma _{ij} = \rho _i$.

To analyze problem (2) we introduce some auxiliary bilinear forms and a broken norm. Let

$$\begin{aligned} d_h(u,v)=\sum ^N_{i=1}d_i(u,v),\quad d_i(u,v)=a_i(u,v)+p_i(u,v) \end{aligned}$$

(3)

and let the weighted broken norm in $X_h(\varOmega )$ be defined by

$$\begin{aligned} \parallel u\parallel ^2_{1,h}\equiv d_h(u,u){=}\sum ^N_{i=1}\big \{\!\parallel (\rho _i)^{1/2}\nabla u_i \parallel ^2_{L^2(K_i)} {+}\sum _{E_{ij}\subset \partial K_i}\frac{\sigma }{h}\gamma _{ij}\parallel u_i-u_j\parallel ^2_{L^2(E_{ij)}}\}. \end{aligned}$$

(4)

Lemma 1

There exists $\sigma _0 > 0$ such that for $\sigma \ge \sigma _0$ there exist positive constants $C_0$ and $C_1$ independent of $\rho _i$ and $h$ such that for any $u \in X_h$ hold

$$ C_0 d_i(u,u) \le \hat{a}_i(u,u) \le C_1 d_i(u,u) $$

and

$$ C_0 d_h(u,u)\le \hat{a}(u,u)\le C_1d_h(u,u). $$

For the proof we refer the reader to [2]; see also [3] or [1].

Lemma 1 implies that the discrete problem (2) is well posed if the penalty parameter $\sigma \ge \sigma _0$. Below $\sigma$ is fixed and assumed to satisfy the above condition.

The error bound is given by

Theorem 2

Let $u^*$ and $u^*_h$ be the solutions of (1) and (2). For $u^*_{|_{K_i}}\in H^2(K_i)$ holds

$$ \parallel u^* - u^*_h\parallel ^2_{1,h} \le Mh^2 \sum ^N_{i=1} \rho _i|u^*|^2_{H^2(K_i)} $$

where $M$ is independent of $h,u^*$ and $\rho _i$.

The proof follows from Lemma 1; for details see, for example, [3].

3 ASM with a Multiscale Coarse Space

We design and analyze a two-level additive Schwarz method (ASM) for solving the discrete problem (2). For that the general theory of ASMs is used, see [5]. The decomposition of $X_h(\varOmega )$ consists of the local spaces defined on subdomains extended from the coarse triangles $\varOmega _l$, and the global space of continuous discrete harmonic functions related to the coarse triangulation.

3.1 Decomposition of $X_h(\varOmega )$

Let

$$\begin{aligned} X_h(\varOmega ) = V^{(0)}(\varOmega )+ \sum ^L_{l=1} V^{(l)}(\varOmega ) \end{aligned}$$

(5)

where $V^{(0)}(\varOmega )$ is a coarse space while $V^{(l)}(\varOmega ), l=1, \ldots L$, are local spaces associated with $\varOmega _l$. They are defined as follows. For $l = 1,\ldots ,L$, $\varOmega _l$ is extended to $\varOmega '_l$ by adding triangles from the fine triangulation around $\partial \varOmega _l$ which intersect $\partial \varOmega _i$ by vertex and/or edge. In this way we get an overlapping partitioning of $\varOmega$,

$$ \bar{\varOmega } = \bigcup \limits _{l=1}^{L} \bar{\varOmega }'_l $$

with overlap $\delta _l \approx 2h$ defined as

$$ \delta _l = dist(\partial \varOmega '_l \setminus \partial \varOmega ,\,\partial \mathop {\varOmega }\limits ^o{}_{l} \setminus \partial \varOmega ) $$

where ${\mathop {\varOmega }\limits ^{o}}_l$ denotes the interior part of $\varOmega _l$ which is not overlapped by any other $\varOmega _p$ for $p \ne l$; see [5, p. 198] for figures which exemplify such decomposition.

The local spaces $V^{(l)}(\varOmega )$ for $l=1,\ldots ,L$ are defined as

$$\begin{aligned} V^{(l)}(\varOmega ) =\{\{v_i\}^N_{i=1} \in X_h(\varOmega ): v_i = 0 \; \text{ on }\; K_i \not \subset \bar{\varOmega }'_l\}. \end{aligned}$$

(6)

Thus $V^{(l)}(\varOmega )$ is the restriction of $X_h(\varOmega )$ to $\bar{\varOmega }'_l$ and zero outside of $\bar{\varOmega }'_l$.

The coarse space $V^{(0)}(\varOmega )$ is defined in a special way. The functions in $V^{(0)}(\varOmega )$ are going to be piecewise linear continuous on the fine triangulation and discrete harmonic on $\partial \varOmega _l$ and in $\varOmega _l$. Let $\nu$ be the set of all vertices of $\bar{\varOmega }_l$. With each $x^{(k)}\in \nu$, a function $\varPhi _k(x)$ is associated with support on a union of coarse triangles $\varOmega _l$ for which $x^{(k)}$ is a common vertex. On the set $\nu$, we set $\varPhi _k(x^{(k)})=1$ and $\varPhi _k(x)=0$ otherwise. Next we define $\varPhi _k$ on the boundary of each $\varOmega _l$. Let $x^{(k)}$ be a vertex of $\varOmega _l$ and let $F_{lp}$ denote an edge of $\varOmega _l$ shared with $\varOmega _p$, $F_{lp}=\partial \varOmega _l\cap \partial \varOmega _p$. Let $a_{\varOmega _l}(\cdot , \cdot )$ be the restriction of $a(\cdot , \cdot )$ to $\bar{\varOmega }_l$, i.e.

$$\begin{aligned} a_{\varOmega _l}(u,v)= \sum _{K_i\subset \bar{\varOmega }_l}(\rho _i\nabla u, \nabla v)_{L^2(K_i)} = (\rho ^{(l)}\nabla u, \nabla v)_{L^2(\varOmega _l)}, \end{aligned}$$

(7)

where by definition $\rho ^{(l)} = \rho _i$ on $K_i\subset \bar{\varOmega }_l$. Then the restriction of $a_{\varOmega _l}(\cdot , \cdot )$ to $F_{lp}$ is defined as

$$\begin{aligned} a_{F_{lp}}(u,v)=(\rho _{lp} D_\tau u, D_\tau v)_{L^2(F_{lp})} \end{aligned}$$

(8)

where $D_\tau$ is the tangential derivative and $\rho _{lp}$, on $F_{lp}$, is the harmonic average of the coefficients on $\varOmega _l$ and $\varOmega _p$, i.e. $\rho _{lp} = 2\rho ^{(l)}\rho ^{(p)}/(\rho ^{(l)}+\rho ^{(p)})$. Note that in this way $\rho _{lp} = \rho _{pl}$. On $F_{lp}$, we define the values of $\varPhi _k$ as the solution of the one-dimensional problem:

$$\begin{aligned} a_{F_{lp}}(\varPhi _k,v)=0 \qquad \forall v \in {\mathop {V}\limits ^{o}}_h(F_{lp}) \end{aligned}$$

(9)

with Dirichlet boundary conditions $\varPhi _k(x^{(k)})= 1$ and $\varPhi _k(x^{(m)})=0$ at the other end, $x^{(m)}$, of $F_{lp}$. Above, ${\mathop {V}\limits ^{o}}_h(F_{lp})$ is the set of piecewise linear continuous functions with zero values on $\partial F_{lp}$. In addition we set $\varPhi _k(x)=0$ on those edges of $\varOmega _l$ which do not end at $x^{(k)}$.

Finally we extend $\varPhi _k$, already defined on $\partial \varOmega _l$, into $\varOmega _l$ as a discrete harmonic function in the sense of $a_{\varOmega _l}(\cdot , \cdot )$, i.e.

$$\begin{aligned} \left\{ \begin{array}{l} a_{\varOmega _l}(\varPhi _k,v)= 0, \qquad \forall v \in {\mathop {V}\limits ^{o}}_h (\varOmega _l) \\ \text{ with } \varPhi _k(x) \; \text{ on }\; \partial \varOmega _l \; \text{ defined } \text{ in } \text{(9) }. \end{array} \right. \end{aligned}$$

(10)

Here $v \in {\mathop {V}\limits ^{o}}_h (\varOmega _l)$ is a set of piecewise linear continuous functions defined on $\bar{\varOmega }_l$ with zero values on $\partial \varOmega _l$.

Using these functions, the coarse space $V^{(0)}(\varOmega )$ is defined as

$$\begin{aligned} V^{(0)}= span\{\varPhi _k(x)\}_{x^{(k)}\in \nu }. \end{aligned}$$

(11)

Of course $V^{(0)} \subset X_h(\varOmega )$.

Remark 3

This space is called a multiscale coarse space and at the beginning it was used to obtain more accurate approximation. In [4], $V^{(0)}(\varOmega )$ was used also as a coarse space in ASM for the conforming (continuous) finite element method in the case when the coefficients are piecewise constant across $\partial \varOmega _l$, $l=1,\ldots ,L$.

3.2 Inexact Solver

For $u^{(0)}, v^{(0)} \in V^{(0)}(\varOmega )$, let

$$\begin{aligned} b_0(u^{(0)},v^{(0)})= d_h(u^{(0)},v^{(0)}), \end{aligned}$$

(12)

where $d_h(\cdot , \cdot )$ is defined in (3).

For $l=1,\dots ,L$ we set

$$\begin{aligned} b_l(u^{(l)}, v^{(l)})= d_{\varOmega '_l}(u^{(l)},v^{(l)}), \quad u^{(l)},v^{(l)}\in V^{(l)}(\varOmega ) \end{aligned}$$

(13)

where for $u^{(l)}=\{u^{(l)}_i\}^N_{i=1},\;\; v^{(l)}=\{v^{(l)}_i\}^N_{i=1}$

$$\begin{aligned} d_{\varOmega '_l}(u^{(l)},v^{(l)})&= \sum _{K_i\subset \bar{\varOmega }'_l}\{(\rho _i\nabla u^{(l)}_i,\nabla v^{(l)}_i)_{L^2(K_i)} + \nonumber \\&+ \sum _{E_{ij}\subset \partial K_i} \gamma _{ij} \frac{\sigma }{h}(u^{(l)}_j-u^{(l)}_i, v^{(l)}_j- v^{(l)}_i)_{L^2(E_{ij})}\}. \end{aligned}$$

(14)

3.3 The Operator Equation

For $l=0,1,\ldots ,L$ let $T_l:X_h(\varOmega )\rightarrow V^{(l)}(\varOmega )$ be defined by

$$\begin{aligned} b_l(T_l u,v)= \hat{a}_h(u,v), \qquad v \in V^{(l)}(\varOmega ). \end{aligned}$$

(15)

Note that $T_l u$ is defined uniquely for given $u \in X_h(\varOmega )$ as the solution of local problems defined on $\varOmega '_l$ for $l=1,\ldots ,L$, and the global one for $l=0$.

Let

$$\begin{aligned} T = T_0 + T_1 + \cdots + T_L. \end{aligned}$$

(16)

We replace (2) by the following operator equation

$$\begin{aligned} Tu^*_h = g_h \end{aligned}$$

(17)

where $g_h = \sum ^L_{l=0}g_l, g_l \equiv T_lu^*_h$. Note that to compute $g_l$ we do not need to know $u^*_h$, the solution of (1).

Problems (2) and (17) are equivalent, what follows from the theorem below.

To formulate the convergence theorem for the discussed ASM we have to introduce some notation. Let us for each $\varOmega _l$ define

$$\begin{aligned} \bar{\rho }_l = \sup _{K_i \subset \varOmega _l^h} \rho _i \end{aligned}$$

(18)

where $\varOmega _l^h$ is a union of triangles $K_i \subset \bar{\varOmega }_l$ which intersect $\partial \varOmega _l$ by vertex and/or edge.

Theorem 4

The operator $T$ defined in (16) satisfies $T=T^*>0$. Moreover, for any $u \in X_h(\varOmega )$ there holds

$$\begin{aligned} C_0\beta ^{-1}\hat{a}_h(u,u)\le \hat{a}_h(Tu,u)\le C_1\hat{a}_h(u,u) \end{aligned}$$

(19)

where

$$\begin{aligned} \beta = \max _{l=1,\ldots ,L} \bar{\rho }_l\,\frac{H_l}{h}\left( 1+\log \frac{H_l}{h}\right) ^2, \end{aligned}$$

(20)

with $\bar{\rho }_l$ defined in (18), and $C_0$ and $C_1$ are positive constants independent of $H$, $h$ and the jumps of $\rho (x)$.

Remark 5

The proof of Theorem 5 needs to check three key assumptions of abstract theory of ASMs, see for example the book [5]. For that we need several auxiliary lemmas, some of them are new. The proof is omitted here due to the limit of pages. It will be published elsewhere together with supporting numerical tests.

4 Implementation

Equation (17) can be solved efficiently by the conjugate gradient method. To simplify the presentation we discuss here the Richardson’s method instead. The latter is of the form: given $u^{(0)}$, iterate for $n=0,1,\ldots$

$$\begin{aligned} u^{(n+1)}= u^{(n)} - \tau ^*(Tu^{(n)}-g_h) \end{aligned}$$

(21)

where we can set $\tau ^*=2/(C_1+C_0\beta ^{-1})$ according to Theorem 5. Since

$$\begin{aligned} r^{(n)}\equiv (Tu^{(n)}-g_h)=\sum ^L_{l=0}(T_l u^{(n)}-g_h)=\sum ^L_{l=0}T_l(u^{(n)}-u^*_h) \equiv \sum ^L_{l=0}r^{(n)}_l, \end{aligned}$$

(22)

we need to compute $r^{(n)}_l \equiv T_l(u^{(n)}-u^*_h)$ for $l=0,1,\ldots ,L$. Note that these problems, see (15), are independent of each other, therefore, they can be solved in parallel. Problems for $l=1,\ldots ,L$ are local, and they are defined on $\varOmega '_l$.

The problem for $l=0$ is global and it is defined on the coarse triangulation with piecewise linear continuous functions. The solution of the coarse problem requires finding the coarse basis functions $\{\varPhi _k\}$ for all the vertices $x^{(k)}$ of the coarse triangles. This is a precomputation step and it should be carried out before starting the iterative process (21).

The above implementation shows that the proposed algorithm is very well suited for parallel computations.