V-cycle Multigrid Algorithms for Discontinuous Galerkin Methods on Non-nested Polytopic Meshes

Abstract

In this paper we analyze the convergence properties of V-cycle multigrid algorithms for the numerical solution of the linear system of equations stemming from discontinuous Galerkin discretization of second-order elliptic partial differential equations on polytopic meshes. Here, the sequence of spaces that stands at the basis of the multigrid scheme is possibly non-nested and is obtained based on employing agglomeration algorithms with possible edge/face coarsening. We prove that the method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the minimum number of smoothing steps, which depends on p, is chosen sufficiently large.

1 Introduction

The discontinuous Galerkin (DG) method was introduced in 1973 by Reed and Hill for the discretization of the neutron equation [59]. Then, DG methods have been proposed to deal with elliptic and parabolic problems: some of the most relevant earlier works include Baker [15], Wheeler [65] and Arnold [12], whose contributions put the basis for the development of the interior penalty DG methods. In the last forty years the scientific and industrial community has shown a growing interest in DG methods—see for example [36, 37, 52, 60] and the references therein for an overview. On the one hand, the features of DG methods have been naturally enhanced by the recent development of High Performance Computing technologies as well as the growing request for high-order accuracy. In particular, as the discrete polynomial space can be defined locally on each mesh element, DG methods feature a high-level of intrinsic parallelism. Moreover, the local conservation properties and the possibility to use meshes with hanging nodes make DG methods interesting also from a practical point of view. Recently, it has been shown that DG methods can be extended to computational grids characterized by polytopic elements, cf. Ref. [3,4,5,6, 8, 10, 17,18,19, 34, 49, 57, 66]. In particular, the efficient approach presented in [34] is based on defining a local polynomial discrete space by making use of the bounding box of each element [48]: this technique together with a careful choice of the discontinuity penalization parameter allow for polytopic elements that can be characterized by faces of arbitrarily small measure and, as shown in [32], see also [8], possibly by an unbounded number of faces.

The development of fast solvers and preconditioners for the linear system of equations stemming from (high-order) DG discretizations has been an intensive research area in recent years. A recent strand of the literature has focused on Schwarz domain decomposition methods, cf. Ref. [1, 2, 6, 9, 31, 41, 42, 44,45,46, 54, 64], and two-level and multigrid/multilevel techniques, cf. Ref. [8, 11, 14, 18, 19, 28,29,30, 38, 50]. The efficiency of those methods can be further improved in the case of polygonal grids, because the flexibility of the element shape couples very well with the possibility of defining agglomerated meshes, which is the key ingredient for the development of multigrid algorithms. In [8] a two-level scheme and W-cycle multigrid methods are analyzed to solve the linear system of equations arising from high-order DG discretizations on polytopic grids. One iteration of the proposed methods consists of an iterative application of the smoothing Richardson operator and a recursive subspace correction step. In particular, the latter is based on a nested sequence of discontinuous discrete polynomial spaces, where the underlying polytopic grids are defined by agglomeration. While being perfectly suited for multilevel schemes, the process of element agglomeration might feature itself some limitations. Indeed, agglomeration leads to coarser grids with an increasing number of faces and this might affect the conditioning of the coarser components of the solver and the overall efficiency.

In this paper we aim at overcoming this issue by analyzing a multigrid method characterized by a sequence of non-nested agglomerated meshes in order to make sure that the number of faces of the agglomerates does not blows up as the number of levels of our multigrid method increases. This can be achieved, for example, based on employing edge-coarsening techniques in the agglomeration procedure. The flexibility in the choice of the computational sub-grids leads to the definition of a non-nested multigrid method characterized by a sequence of non-nested multilevel discrete spaces and where the discrete bilinear forms are chosen differently on each level, cf. Ref. [20, 69, 70]. The first non-nested multilevel method was introduced by Bank and Dupont in [16]; a generalized framework was developed by Bramble, Pasciak and Xu in [26], and then widely used in the analysis of non-nested multigrid iterations, cf. Ref. [21,22,23,24,25, 27, 51, 61, 67, 68]. The method of [26], to whom we will refer as the BPX multigrid framework, is able to generalize also the multigrid framework that we will develop in this paper, but the convergence analysis relies on the assumption that , which might not be guaranteed in the DG setting, as we will see in Sect. 4.2. Here and are the bilinear forms on two consecutive levels, and $I_{j-1}^j$ is the prolongation operator whose definition is not trivial, differently from the nested case. For this reason the convergence analysis will be presented based on employing the abstract setting proposed by Duan, Gao, Tan and Zhang in [43], which permits to develop a full analysis of V-cycle multigrid methods in a non-nested framework relaxing the hypothesis . We prove that our V-cycle scheme with non-nested spaces converges uniformly with respect to the discretization parameters, namely the mesh size h and the polynomial degree p, provided that the number of smoothing steps, which depends on p, is chosen sufficiently large. This result extends the theory of [8] where W-cycle multigrid methods for high-order DG methods with nested spaces have been proposed and analyzed.

The paper is organized as follows. In Sect. 2 we introduce the interior penalty DG scheme for the discretization of second-order elliptic problems on general meshes consisting of polygonal/polyhedral elements. In Sect. 3, we recall some preliminary results concerning this class of schemes. In Sect. 4 we define the multilevel BPX framework for the V-cycle multigrid solver based on non-nested grids, and present the convergence analysis of our algorithm. The main theoretical results are validated through a series of numerical experiments in Sect. 5. In Sect. 6 we propose an improved version of the algorithm, obtained by choosing a smoothing operator based on a domain decomposition preconditioner. Finally, in Sect. 7 we draw some conclusions.

2 Model Problem and Its DG Discretization

We consider the weak formulation of the Poisson problem, subject to homogeneous Dirichlet boundary conditions: find $u\in V = H^2(\varOmega )\cap H_0^1(\varOmega )$ such that

$$\begin{aligned} \mathcal {A}(u,v) =\int _\varOmega \nabla u \cdot \nabla v\ \mathrm {d}x =\int _\varOmega f v\ \mathrm {d}x \, \qquad \forall v\in V, \end{aligned}$$

(1)

with $\varOmega \subset \mathbb {R}^d$, $d = 2,3$, a convex polygonal/polyhedral domain with Lipschitz boundary and $f \in L^2(\varOmega )$. The unique solution $u \in V$ of problem (1) satisfies

(2)

In view of the forthcoming multigrid analysis, let be a sequence of tessellation of the domain , each of which is characterized by disjoint open polytopic elements of diameter , such that , $j=1,\dots ,J$. The mesh size of is denoted by . For the sake of simplicity, we assume that on each level the mesh is quasi-uniform. To each we associate the corresponding discontinuous finite element space $V_j$, defined as

where denotes the space of polynomials of total degree at most $p_j \ge 1$ on .

Remark 1

For the sake of brevity we use the notation $x \lesssim y$ to mean $x \le Cy$, where $C>0$ is a constant independent from the discretization parameters. Similarly we write $x \gtrsim y$ in lieu of $x \ge Cy$, while $x\ {\eqsim }\ y$ is used if both $x \lesssim y$ and $x \gtrsim y$ hold.

A suitable choice of and $\{ V_j \}_{j=1}^J$ leads to the non-nested hp-multigrid schemes. This method is based on employing a set of non-nested polytopic partitions , such that the coarse level is independent from , with the only constraint

(3)

We also assume that the polynomial degree varies from one level to another such that

$$\begin{aligned} p_{j-1} \le p_j \lesssim p_{j-1}\qquad \forall \ j = 2,\dots , J. \end{aligned}$$

(4)

Additional assumptions on the grids are outlined in the following paragraph.

2.1 Grid Assumptions

For any , we define the faces of the mesh , $j=1,\dots ,J$, as the intersection of the $(d-1)$-dimensional facets of neighboring elements. This implies that, for $d=2$, a face always consists of a line segment, whereas for $d=3$, the faces of are general shaped polygons. Thereby, we assume that each face of an element can be subdivided into a set of co-planar $(d-1)$-dimensional simplexes and we refer to them as faces. In order to introduce the DG formulation, it is helpful to distinguish between boundary and interior faces, denoted as $\mathcal {F}_j^B$ and $\mathcal {F}_j^I$, respectively. In particular, we observe that $F \subset \partial \varOmega$ for $F \in \mathcal {F}_j^B$, while for any $F \in \mathcal {F}_j^I$, , where are two adjacent elements in . Furthermore, we denoted by $\mathcal {F}_j = \mathcal {F}_j^I \cup \mathcal {F}_j^B$ the set of all mesh faces of . With this notation, we assume that the sub-tessellation of element interfaces into $(d-1)$-dimensional simplexes is given. Moreover, for the forthcoming analysis, we require that the following assumptions hold, cf. [32, 33].

Assumption 1

For any $j=1,\dots ,J$, given there exists a set of non-overlapping d-dimensional simplexes , , such that for any face it holds that , for some l, , and the diameter of can be bounded by

Assumption 2

For any , we assume that , where $d=2,3$ is the dimension of .

Assumption 3

Every polytopic element , admits a sub-triangulation into at most shape-regular simplexes , for some , such that and

Assumption 4

For each , $j=1,\dots ,J$, we assume that there exists a covering of consisting of shape-regular d-dimensional simplexes , such that, for any , there is satisfying and . We also assume that for any $j=1,\dots ,J,$ it holds

Remark 2

Assumption 1 is needed in order to obtain the trace inequalities of Lemmas 1 and 2 below. Assumptions 2 and 3 are required for the inverse estimates of Lemma 5 and Theorem 5 below. Assumption 4 guarantees the validity of the approximation result and error estimates of Lemma 4 and Corollary 1, respectively.

Remark 3

Assumption 1 allows to employ very general polygonal and polyhedral elements. Indeed, if is a polygonal/polyhedral element and is one of its faces, then Assumption 1 allows the size of F to be small compared to the diameter of , provided that the height of the related simplex $T_l$, with base F, is comparable to . We refer to [32] for more details.

2.2 DG Formulation

In order to introduce the DG discretization of (1), we first need to define suitable jump and average operators across the faces , $j=1,\ldots ,J$. Let $\varvec{\tau }$ and v be sufficiently smooth functions. For each internal face , such that F is shared by , let $\mathbf{n }^{\pm }$ be the outward unit normal vector to , and let $\varvec{\tau }^\pm$ and $v^\pm$ be the traces of $\varvec{\tau }$ and v on F from , respectively. The jump and average operators across F are then defined as follows:

If is a boundary face, we set accordingly cf. [13]. Let be the lifting operator defined as

cf. [13].

With this notation, the bilinear form corresponding to the symmetric interior penalty DG method on the j-th level is defined by

(5)

where, according to [39, 40], denotes the interior penalty stabilization function, which is defined by

(6)

with $C_{\sigma }^j>0$ independent of $p_j$, |F| and , and where $\{ \cdot \}_H$ is the harmonic average given by

Remark 4

Formulation (5) is based on the lifting operators $\mathcal {R}_j$ and allows to introduce the discrete gradient operator $\mathcal {G}_j: V_j \rightarrow [V_j]^d$, defined as

(7)

where $\nabla _j$ is the piecewise gradient operator on the space $V_j$. The role of $\mathcal {G}_j$ will be clear in Sect. 4.2.

The goal of this paper is to develop non-nested V-cycle multigrid schemes to solve the following problem posed on the finest level $V_J$: find $u_J\in V_J$ such that

(8)

3 Preliminary Results

In this section we recall some preliminary results that form the basis of the convergence analysis presented in the next section.

Lemma 1

Assume that the sequence of meshes satisfies Assumption 1. Let , the following bound holds

where is the diameter of and $\epsilon >0$ is a positive number.

The proof of Lemma 1 combines Assumption 1 with the idea of [37, Proof of Lemma 1.49].

Lemma 2

Assume that the sequence of meshes satisfies Assumption 1. Let , the following bound holds

We refer to [32] for the proof.

We endow each discrete space $V_j,\ j=1,\dots ,J$, with the following DG norm:

(9)

The well-posedness of the DG formulation (8) on each level $j=1,\dots ,J$ is established in the following lemma.

Lemma 3

The following continuity and coercivity bounds, respectively, hold:

The second bound holds provided that the constants $C_{\sigma }^j,\ j=1,\dots ,J$, appearing in (6) are chosen sufficiently large.

Next, we recall the following approximation result, which is an analogous bound presented in [34, Theorem 5.2]. This result exploits the properties of the extension operator , such that and , introduced in [62].

Lemma 4

Let Assumption 4 be satisfied, and let $v \in L^2(\varOmega )$ such that, for some $k \ge 0$, and for each , with as defined in Assumption 4. Then, there exists a projection operator ${\widetilde{\varPi }}_j: L^2(\varOmega )\rightarrow V_j$ such that

where $s=\min \{p_j+1,k\}$ and $p_j \ge 1.$

Remark 5

From Lemma 4, for uniform orders and $\forall j=1,\dots ,J$, we point out that, if $v \in H^k(\varOmega )$, the following bound follows:

The result presented in Lemma 4 leads to the following error bounds for the underlying interior penalty DG scheme, which follows from the energy norm error bounds that have been proved in [34], see also [32] in the general case. The corresponding $L^2$-estimates can be found in [8].

Corollary 1

Assume that Assumptions 1 and 4 hold. Let $u_j\in V_j$, $j=1,\ldots ,J$, be the DG solution of problem (8) posed on level j, i.e.,

If the solution u of (1) is sufficiently regular, i.e. $u \in H^k(\varOmega ) \cap H^1_0(\varOmega )$, $k \ge 2$, then

where $s=\min \{p_j+1,k\}$ and $p_j \ge 1$.

Remark 6

We point out that the bounds in Corollary 1 are optimal in h and suboptimal in p of a factor $p^{\frac{1}{2}}$ and p for the DG-norm and the $L^2$-norm, respectively. Optimal error estimates with respect to p can be shown, for example, by using the projector of [47] for quadrilateral meshes providing the solution belongs to a suitable augmented Sobolev space. The issue of proving optimal estimates as the ones in [47] on polytopic meshes is an open problem and it is under investigation. In the following, we will write:

where $s=\min \{p_j+1,k\}$, $p_j\ge 1$, and $\mu \in \{ 0,1 \}$ for optimal and suboptimal estimates, respectively.

We also need to introduce an appropriate inverse inequality, cf. [8].

Lemma 5

Assume that Assumptions 2 and 3 hold. Then, for any $v\in V_j$, $j=1,\ldots ,J$, the following inverse estimate holds

Thanks to the inverse estimate of Lemma 5, it is possible to obtain the following upper bound on the maximum eigenvalue of . We refer to [7] for a similar result on standard grids, and to [8] for its extension to polygonal grids.

Theorem 5

Let Assumptions 1, 2 and 3 be satisfied. Then

4 The BPX-Framework for the V-cycle Algorithms

The analysis presented in this section is based on the general multigrid theoretical framework of [26] for multigrid methods with non-nested spaces and non-inherited bilinear forms. In order to develop a geometric multigrid, the discretization at each level $V_j$ follows the one already presented in [11], where a W-cycle multigrid method based on nested subspaces is considered. The key ingredient in the construction of our proposed multigrid schemes is the inter-grid transfer operators.

First, we introduce the operators $A_j:V_j\rightarrow V_j$, defined as

(10)

and we denote by $\varLambda _j\in \mathbb {R}$ the maximum eigenvalue of $A_j$, $j=2,\dots ,J$. Moreover, let $Id _j$ be the identity operator on the level $V_j$. The smoothing scheme, which is chosen to be the Richardson iteration, is given by

$$\begin{aligned} B_j = \varLambda _j Id _j \quad j=2,\dots ,J. \end{aligned}$$

The prolongation operator connecting the coarser space $V_{j-1}$ to the finer space $V_j$ is denoted by $I_{j-1}^j$. Since the two spaces are non-nested, i.e. $V_{j-1} \not \subset V_j$, it cannot be chosen as the natural injection operator. The most natural way to define the prolongation operator is the $L^2$-projection, i.e. $I_{j-1}^j : V_{j-1}\rightarrow V_j$

(11)

The restriction operator $I_{j}^{j-1} : V_{j}\rightarrow V_{j-1}$ is defined as the adjoint of $I_{j-1}^j$ with respect to the $L^2(\varOmega )$-inner product, i.e.,

$$\begin{aligned} (I_j^{j-1} w_h,v_H)_{L^2(\varOmega )} = (w_h,I_{j-1}^j v_H)_{L^2(\varOmega )}\ \ \forall v_H \in V_{j-1}. \end{aligned}$$

For our analysis, we also need to introduce the operator $P_j^{j-1}:V_j\rightarrow V_{j-1}$

According to (10), problem (8) can be written in the following equivalent form: find $u_J \in V_J$ such that

$$\begin{aligned} A_J u_J = f_J, \end{aligned}$$

(12)

where $f_J \in V_J$ is defined as . Given an initial guess $u_0 \in V_J$, and choosing the parameters $m_1,m_2 \in \mathbb {N}$, the multigrid V-cycle iteration algorithm for the approximation of $u_J$ is outlined in Algorithm 1. In particular, ${\textsf {M}}{\textsf {G}}_\mathcal {V} (J,f_J,u_k,m_1,m_2)$ represents the approximate solution obtained after one iteration of our non-nested V-cycle scheme, which is defined by induction: if we consider the general problem of finding $z \in V_j$ such that

$$\begin{aligned} A_j z = g, \end{aligned}$$

(13)

with $j\in \{2,\dots ,J\}$ and , then ${\textsf {M}}{\textsf {G}}_\mathcal {V} (j,g,z_0,m_1,m_2)$ represents the approximate solution of (13) obtained after one iteration of the non-nested V-cycle scheme with initial guess $z_0 \in V_j$ and $m_1,\ m_2$ pre-smoothing and post-smoothing steps, respectively. The recursive procedure is outlined in Algorithm 2, where we also observe that on the level $j=1$ the problem is solved exactly.

4.1 Convergence Analysis

We first define the following norms on each discrete space $V_j$

To analyze the convergence of the algorithm, for any $j=2,\dots ,J$, we set $G_j = Id _j - B_j^{-1}A_j$ and define $G_j^*$ as its adjoint with respect to . Following [43], we make three standard assumptions in order to prove convergence of Algorithm 1:

A.1 :

Stability estimate: $\exists \ C_Q>0$ such that

A.2 :

Regularity-approximation property: $\exists \ C_A>0$ such that

A.3 :

Smoothing property: $\exists \ C_R>0$ such that

where $\mathcal {R} = \bigl ( Id _j - G_j^* G_j \bigr ) A_j^{-1}$.

The convergence analysis of the V-cycle method is stated in the following theorem that gives an estimate for the error propagation operator related to the j-th level iteration with $m_1$ and $m_2$ pre- and post-smoothing steps, respectively. The error propagation operator is defined as

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathbb {E}_{1,m_1,m_2}v &{}= 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \quad \quad \ \ \ \qquad \qquad j=1, \\ \mathbb {E}_{j,m_1,m_2}v &{}= \mathbb {G}^*_{j,m_2}( Id _j - I_{j-1}^j P_j^{j-1} + I_{j-1}^j \mathbb {E}_{j-1,m_1,m_2} P_j^{j-1} )\mathbb {G}_{j,m_1} v, \quad j >1, \end{array}\right. } \end{aligned}$$

where $\mathbb {G}_{j,m} = (G_j)^{m}$ and $\mathbb {G}^*_{j,m} = (G^*_j)^{m}$, $m \ge 1$.

Theorem 6

If Assumptions A.1, A.2 and A.3 hold, then

where $\delta _j = \frac{C_A C_R}{m - C_A C_R}<1,$ provided that $m > 2C_AC_R$.

We refer to [43] for the proof of Theorem 6 in an abstract setting. In the following, we prove the validity of Assumptions A.1, A.2 and A.3 for our algorithm. We start with a two-level approach, i.e. $J=2$, and we consider the two-level method for the solution of (8), based on two spaces $V_{J-1} \not \subset V_J$. The generalization to the V-cycle method will be given at the end of this section.

4.2 Validity of Assumption A.1

In order to verify Assumption A.1 for the two-level method we first show a stability result of the prolongation operator $I_{J-1}^J$. In the following, we also consider the $L^2$-projection operator on the space $V_J$ defined as

Remark 7

From the definition of $I_{J-1}^J$ given in (11), it holds $I_{J-1}^J = Q_J |_{V_{J-1}}$.

Moreover, we need the following approximation result which shows that any $v_j \in V_j,\ j=J-1,J,$ can be approximated by an $H^1$-function, see [9]. Let $\mathcal {G}_j$ be the discrete gradient operator (7) introduced in Remark 4, and consider the following problem: $\forall v_j \in V_j$, find such that

(14)

It is shown in [9] that $\mathcal {H}(\cdot )$ possesses good approximation properties in terms of providing an $H^1$-conforming approximant of the discontinuous function $v_j$:

Theorem 7

Let be a bounded convex polygonal/polyhedral domain in $\mathbb {R}^d$, $d=2,3$. Given $v_j \in V_{j}$, we write to be the approximation defined in (14). Then, the following approximation and stability results hold:

(15)

We make use of the previous result in order to show the following stability result of the prolongation operator:

Lemma 6

There exists a positive constant ${\textsf {C}}_{\textsf {stab}} = {\textsf {C}}_{\textsf {stab}}(p_J)$, independent of the mesh size such that

Here .

Proof

Let $v_H \in V_{J-1}$, by the definition of the DG norm (9), we need to estimate:

(16)

We next bound each of the two terms on the right hand side separately. For the first one we let $\mathcal {H}_H = \mathcal {H}(v_H)$ be defined as in (14). Then:

(17)

where we have added and subtracted the terms $\nabla _J {\widetilde{\varPi }}_{J}(\mathcal {H}_H)$ and $\nabla \mathcal {H}_H$. The second term of the right hand above side can be estimated using the interpolation bounds of Lemma 4, the Poincaré inequality for $\mathcal {H}_H \in H^1_0(\varOmega )$ and the second bound of (15):

In order to estimate the first term on the right hand side in (17) we observe that, since $I_{J-1}^J v_H - {\widetilde{\varPi }}_{J}(\mathcal {H}_H) \in V_J$, it is possible to make use of the inverse inequality of Lemma 5, that leads to the following bound:

(18)

By adding and subtracting $\mathcal {H}_H$ to we obtain

(19)

Using Lemma 4 and the Poincaré inequality (since ) we have

whereas the term can be estimate as follow:

Using Remark 7, the continuity of $Q_J$ with respect to the $L^2$-norm, Lemma 4 and (15) we have

Thanks to the previous estimates and inequality (19), we obtain

(20)

The above estimate, together with (18), (17) and the second bound of (15) lead to

(21)

Next we bound the second term on the right hand side in (16). By the definition of the jump term and remembering that since $\mathcal {H}_H \in H_0^1(\varOmega )$, it holds

(22)

where we also used the definition of $\sigma _J$. Now, we first observe that we can use the trace inequality of Lemma 2 in order to obtain

(23)

To bound the second term on the right hand side in (22), we first exploit the continuous trace inequality on polygons of Lemma 1 with $\epsilon = p_J$, obtaining

then, by summing over , using the approximation property of Lemma 4 and the Poincaré inequality, we obtain

From the previous inequality and the bound (23), (22) becomes:

where we also used inequality (20). This estimate together with (21) leads to

where $\textsf {C}_{\textsf {stab}}(p_J) = \mathcal {O}(p_J)$. $\square$

We can use the previous result in order to prove that Assumption A.1 holds. We first observe that also the operator $P_J^{J-1}$ satisfies a similar stability estimate as the one of $I_{J-1}^J$, that is

from which it follows

Proposition 1

Assumption A.1 holds with $C_Q \lesssim p_J^2$.

Proof

Let $v_H \in V_{J-1},$ making use of Lemma 3 we have

Similarly, it holds

(24)

Let $v_h \in V_{J}$ and set $v_H = P_J^{J-1} v_h$, then the following inequality holds:

(25)

By adding and subtracting $v_h$ to both arguments of on the left hand side of (25), and using (24) we obtain

that concludes the proof. $\square$

4.3 Validity of Assumption A.2

In order to show the validity of Assumption A.2 we need the following standard approximation result, which is proved in “Appendix”.

Lemma 7

Let Assumptions 1–4 hold. Then

(26)

Thanks to Lemma 7, it is possible to show the following result.

Theorem 8

The regularity-approximation property A.2 holds with $C_A \lesssim p_J^{2+\mu }$, $\mu = 0,1$.

Proof

Theorem 5 gives the following bound of the maximum eigenvalue of $A_J$: Using Lemma 7, the above bound on $\varLambda _J$, and the symmetry of we have, for all $v \in V_J$:

and the proof is complete. $\square$

4.4 Validity of Assumption A.3

Proposition 2

Assumption A.3 holds with .

Proof

We have:

$$\begin{aligned} \mathcal {R} = \bigl ( Id _J - G_J^* G_J \bigr ) A_J^{-1} = \Bigl ( \frac{2}{\varLambda _J} A_J - \frac{1}{\varLambda _J^2} A_J A_J \Bigr ) A_J^{-1} = \frac{1}{\varLambda _J} \Bigl ( Id _J + \Bigl ( Id _J - \frac{1}{\varLambda _J} A_J \Bigr ) \Bigr ), \end{aligned}$$

and so

We now prove that $\Bigl ( Id _J - \frac{1}{\varLambda _J} A_J \Bigr )$ is a positive definite operator. By contradiction, let us suppose that there exists a function $\overline{u} \in V_J$, $\overline{u} \ne 0$, such that

(27)

By Lemma 3 and the symmetry of the bilinear form , the eigenfunctions $\{ \phi ^{J}_{k} \}_{k=1}^{N_J}$ satisfy

where $0 < \lambda ^{J}_{1} \le \lambda ^{J}_{2} \le \dots \le \lambda ^{J}_{N_J} = \varLambda _J$. The set of eigenfunctions is an orthonormal basis for the space $V_J$, i.e. $(\phi ^{J}_{i},\phi ^{J}_{j})_{L^2(\varOmega )} = \delta _{ij}$, and satisfies , where $\delta _{ij}$ is the Kronecker symbol. Since $\{ \phi ^{J}_{k} \}_{k=1}^{N_J}$ is a basis of the space $V_J$, we can write $\overline{u} = \sum _{k=1}^{N_J} c_k \phi ^{J}_{k}$, so that (27) becomes

which is a contradiction. We then deduce that $\Bigl ( Id _J - \frac{1}{\varLambda _J} A_J \Bigr )$ is a positive definite operator. $\square$

Remark 8

We observe that, as we need to satisfy the condition $m > 2C_AC_R$ of Theorem 6, we can guarantee the convergence of the method based on employing a number of smoothing steps such that $m \gtrsim p_J^{2+\mu }$, which is in agreement to what proved for W-cycle algorithms in [11] and [8] in the case of nested grids.

Remark 9

The analysis of this section can be generalized to the full V-cycle algorithm with $J>2$ as follows: Assumption A.3 is verified with also on the arbitrary levels $j,j-1$, because each level j satisfies Assumption A.3 with constant . Assumptions A.2 and A.1 are satisfied with $C_A = \max _{j}\{ C_A^j \}$ and $C_Q = \max _{j}\{ C_Q^j \}$, respectively, where $C_A^j$ and $C_Q^j$ are the same as the ones defined in the previous analysis but on the level j.

Fig. 1

Sets of non-nested grids employed for numerical simulations

5 Numerical Results

In this section we present several numerical results to test the theoretical convergence estimates provided in Theorem 6 and to demonstrate the capability of our algorithm also in practical cases. We focus on a two dimensional problem posed on the unit square $\varOmega = (0,1)^2$. For the simulations, we consider the sets of polygonal grids shown in Figure 1. Each polygonal mesh is generated by using the software package PolyMesher [63]. In particular the finest grids (Level 4) of Fig. 1 consist of 512 (Set 1), 1024 (Set 2), 2048 (Set 3) and 4096 (Set 4) elements. Starting from the number of elements of each initial mesh, a sequence of non-nested partitions is generated: each coarse mesh is built independently from the finer one, with the only constrain that the number of element is approximately 1 / 4 of the corresponding finer one.

Fig. 2

Estimates of $\textsf {C}_{\textsf {stab}}(p)$ in Lemma 6 as a function of p for three couples of non-nested Voronoi meshes as shown in Fig. 1

Fig. 3

Estimates of $\delta _2$ and $\delta _3$ in Theorem 6 as a function of p, with $m_1=m_2=3p^2$ and two polygonal grids of 256 (left) and 512 (right) elements

First of all, we verify the estimate of Lemma 6, by numerically evaluating $\textsf {C}_{\textsf {stab}}(p)$, where p is the polynomial approximation degree. To this aim we consider three pairs of non-nested grids, where the number of elements of the coarser grid is the number of the finer divided by 4: for each pair, we compute the value of $\textsf {C}_{\textsf {stab}}(p)$ as a function of p. Figure 2 show that, as expected, $\textsf {C}_{\textsf {stab}}(p)$ depends linearly on p and is independent of the mesh-size h.

We now consider the grids shown in Set 1 and in Set 2 of Fig. 1 and numerically evaluate the constant $\delta _j$ in Theorem 6 based on selecting the Richardson smoother with $m_1=m_2=m=3p^2$, cf. Fig. 3. Here, we observe that $\delta _{2}$ and $\delta _3$ are asymptotically constant, as the polynomial degree p increases showing that our two-level and V-cycle algorithms are uniformly convergent also with respect to p provided that $m \ {\gtrsim }\ p^2$.

Next, we investigate the performance of the V-cycle algorithm with non-nested partitions presented in Sect. 4. In order to do that, we compute the iteration counts needed by our V-cycle algorithm to reduce the relative residual error below a given tolerance of $10^{-8}$, by varying the polynomial degree and the granularity of the finest grid. In Table 1 we report the computed convergence factor

$$\begin{aligned} \rho _J = \exp \left( \frac{1}{N_{it,J}}\ln \frac{\Vert \mathbf r _{N_{it,J}}\Vert }{\Vert \mathbf r _{0}\Vert }\right) , \end{aligned}$$

where $N_{it,J}$ is the iteration counts needed to reduce the residual below the given tolerance by the h-version of the V-cycle scheme with J levels, where $J=2,3,4$, while $\mathbf r _{N_{it,J}}$ and $\mathbf r _{0}$ are the final and initial residual vectors, respectively. Here, the polynomial approximation degree on each level is chosen as $p_j =1$, $j=1,\dots ,J$, while we vary the number of elements of the finest grid and the number of smoothing steps ($m_1=m_2=m$). According to Theorem 6, the convergence factor is independent from the spatial discretization step h. Indeed, for a fixed $J\in \{2,3,4\}$ and a fixed number of smoothing steps m, the convergence factor is roughly constant. In particular, this means that the number of iterations needed by our V-cycle method to attain convergence is independent of the granularity of the underlying grid. As expected, the convergence factor is reduced by increasing the number of smoothing step.

Table 1 Converge factor $\rho _J$ of the V-cycle multigrid method as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=1$)

Table 2 Converge factor $\rho _J$ (and iteration counts) of the V-cycle method as a function of the number m of smoothing steps ($C_\sigma ^j \equiv C_\sigma =10$, $p=3$)

We have repeated the same set of experiments employing $p_j=3,\ \forall j=1,\dots ,J$; the results are reported in Table 2 together with the corresponding iteration counts (between parenthesis). First, a comparison between Tables 1 and 2 shows that the convergence factor increases as p grows if the number of smoothing steps is kept fixed. We also observe that, if the number of smoothing step is not chosen sufficiently large, the algorithm might fail to converge. Indeed, according to Theorem 6, in order to attain a uniform convergence (also with respect to p) the number of smoothing steps m must satisfy $m > 2C_A C_Q \gtrsim p^{2+\mu }$, cf. also Fig. 3.

6 Additive Schwarz Smoother

In order to improve the performance of our V-cycle algorithm, we define in this section a domain decomposition preconditioner that can be used as a smoothing operator in place of of the Richardson one. To this aim, let and be a pair of consecutive (non-nested) coarse/fine meshes, satisfying the grid assumptions given in Sect. 2.1. We next introduce the local and coarse solvers, that are the key ingredients in the definition of the smoother on the space $V_j,\ j=2,\dots ,J$.

Local Solvers. Let us consider the finest mesh with cardinality $N_j$, then for each element , we define a local space $V_j^i$ as the restriction of the DG finite element space $V_j$ to the element :

and for each local space, the associated local bilinear form is defined by

where $R_i^T:V_j^i \rightarrow V_j$ denotes the classical extension by-zero operator from the local space $V_j^i$ to the global $V_j$.

Coarse Solver. The natural choice in our contest is to define the coarse space $V^0_j$ to be exactly the same used for the Coarse grid correction step of the V-cycle algorithm introduced in Sect. 4, that is

the bilinear form on $V^0_j$ is then given by

Here, we define the injection operator from $V_j^0$ to $V_j$ as the prolongation operator introduced in Sect. 4, that is $R_0^T:V_j^0 \rightarrow V_j,\ R_0^T = I_{j-1}^j.$ By introducing the projection operators $P_i = R_i^T \tilde{P_i}: V_j \rightarrow V_j, \text { }i=0,1,\dots ,N_j,$ where

the additive Schwarz operator is defined by $P_{ad} = \sum _{i=0}^{N_j} (R_i^T (A^i_j)^{-1} R_i) A_j \equiv B^{-1}_{ad}A_j,$ where $B^{-1}_{ad} = \sum _{i=0}^{N_j} (R_i^T (A^i_j)^{-1} R_i)$ is the preconditioner. Then, the Additive Schwarz smoothing operator with m steps consists in performing m iterations of the Preconditioned Conjugate Gradient method using $B_{ad}$ as preconditioner. In Algorithm 3 we show the V-cycle multigrid method using $P_{ad}$ as a smoother. Here, ${\textsf {MG}}_{{\mathcal {AS}}} (j,g, z_0,m_1,m_2)$ denotes the approximate solution of $A_jz=g$ obtained after one iteration, with initial guess $z_0$ and $m_1$, $m_2$ pre- and post-smoothing steps, respectively. The smoothing step is given by the algorithm ASPCG, i.e., $z = ASPCG(A, z_0, g, m)$ represents the output of m steps of Preconditioned Conjugate Gradient method applied to the linear system of equations $Ax = g,$ by using $B_{as}$ as preconditioner and starting from the initial guess $z_0$.

The computed iteration counts based on employing Algorithm 3 are reported in Tables 3, 4 and 5, for the corresponding V-cycle algorithm with $J=2,3,4$ levels. The simulations are similar to the ones described in the previous section: here we used the grids of Set 2, 3 and 4, cf. Fig. 1, and we varied the polynomial degree $p \in \{1,3,5\}$. First, we observe that, also in this case, the iteration counts seem to be independent of the number of elements in the underlying mesh for a fixed number of smoothing steps m. Moreover, the results show that a minimal number of smoothing steps is not needed to attain the convergence as p increases. Finally, Table 6 shows the computed convergence factor, where different polynomial approximation degrees are employed on different levels. Also in this case we observe that the iteration counts seem to be independent of the granularity of the underlying grid.

Table 3 Iteration counts of the V-cycle solver with the Additive Schwarz smoother as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=1$)

Table 4 Iteration counts of the V-cycle solver with the Additive Schwarz smoother as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=3$)

Table 5 Iteration counts of the V-cycle solver with the Additive Schwarz smoother as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=5$)

Table 6 Iteration counts of the hp-version of the V-cycle solver with the Additive Schwarz smoother as a function of m. Here the polynomial degree on each space is $p_j = j$ for $j = 1,2,3,4$

6.1 Applications to Domains with Curved Boundaries

In this section we consider two examples where the coarser grid does not conform to the boundary. Indeed, in these cases the agglomeration process with edge-coarsening might lead to coarse meshes whose boundary do not fit the geometry, cf. Fig. 4 for an example.

In the following we present two examples showing that the convergence properties of our multigrid method seems not to deteriorate for such problems and that our approach seems to be competitive in practical cases. The results of this section have been obtained with the AS smoother, cf. Sect. 6. First, we consider problem (1) with a constant forcing term $f=1$, and choose the computational domain to be a circular crown $\varOmega = \varOmega _1 \setminus \varOmega _2$, where $\varOmega _1$ and $\varOmega _2$ are two concentric circles of radius $r_1 = 2$ and $r_2 = \frac{2}{3}$, respectively. We have tested the V-cycle method by defining three sequences of uniform Voronoi grids (set 1, set 2, set 3) as the ones reported in Fig. 5, where, for each set of grids, the first three levels of refinement are shown. Here, each polygonal mesh at different levels is defined independently from the previous one with the only constrain that the cardinality of each coarser grid is approximately $\frac{1}{4}$ of that of the finer level. Tables 7 and 8 show the computed convergence factors for $p=1$ and $p=2$, respectively, by choosing $m = 3,5,8$ smoothing steps. As expected, the results confirm that the convergence rate depends on p but it is independent of the granularity of the underlying grid as well as the number of levels employed.

Fig. 4

Examples of fine (solid line) and coarse (dashed line) grids for a domain with a curved boundary

Fig. 5

Circular crown test case: for any set of grids the first three levels of non-nested meshes are shown

Next, we consider the airfoil geometry of [35], which is characterized by a more complicated geometry $\varOmega = \varOmega _1 \setminus \varOmega _2$, where $\varOmega _1$ is the circle of radius $r_1 = \frac{3}{2}$, and $\varOmega _2$ is the airfoil profile NACA0015 [56]. As before, we consider three sequences of non-nested polygonal meshes (set 1, set 2, set 3), cf. Fig. 6. The grids have been obtained by firstly defining a non-uniform triangular mesh on $\varOmega$ with the tool DistMesh [58], and then by agglomerating based on employing METIS [55]. The results for $p=1$ and $p=2$ are shown in Tables 9 and 10, respectively. Also in this case we observe that, by fixing the number of smoothing steps m and the polynomial degree p, the convergence factor seems to be independent of the mesh size. Moreover, the performance of the method seems not to deteriorate even if the underlying mesh is characterized by elements of different size, and suggest that our algorithm seems to be well suited for the solution of problems characterized by a local refinement or applications with mesh adaptation.

Table 7 Convergence factor of the h-version of the V-cycle solver with the Additive Schwarz smoother as a function of m (circular crown test case, $p=1$)

Table 8 Convergence factor of the h-version of the V-cycle solver with the Additive Schwarz smoother as a function of m (circular crown test case, $p=2$)

Fig. 6

Airfoil profile test case: for any set of grids the first three levels of non-nested grids are shown

Table 9 Convergence factor of the h-version of the V-cycle solver with the Additive Schwarz smoother as a function of m (airfoil profile test case, $p=1$)

Table 10 Convergence factor of the h-version of the V-cycle solver with the Additive Schwarz smoother as a function of m (airfoil profile test case, $p=2$)

7 Conclusions

In this paper we have extended the W-cycle multigrid convergence analysis on nested polygonal/polyhedral grids of [8] to V-cycle algorithms with non-nested meshes. We have focused on the solution of the linear systems of equations stemming from high-order discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polytopic meshes. Here, the possibility of employing non-nested polytopic meshes allows to choose the sequence of grids standing at the basis of the multigrid method based on employing agglomeration procedures together with edge-coarsening. The key aspect of our method is the projection operator which is defined as the $L^2$-projection between two consecutive (non-nested) partitions. By following the general framework introduced in [26] for non-nested multigrid methods, we have proved that our non-nested multigrid method converges uniformly with respect of the number of degree of freedom and the number of multigrid levels, provided that the number of smoothing steps is chosen sufficiently large. More precisely we have proved that the convergence rate is independent of the granularity of the underlying (fine) grid, the polynomial approximation degree p and the number of levels, provided that the number of smoothing steps is chosen of order $p^{2+\mu }$, $\mu \in \{ 0,1 \}$. We have also proposed a further improvement of the method by considering a Schwarz-type smoother. We demonstrated through several numerical experiments the effectiveness of the proposed algorithm, also for geometries with curved boundaries, where the coarser grid does not fit the geometry. From the implementation point of view, we point out that the assembly of the prolongation and projection matrices needs the knowledge of the intersections between elements of two consecutive levels. Our computations make use of the tool PolygonClipper [53], but its extension to the three dimensional case could be expensive. In three dimensions, agglomeration-based procedures which make use of edge-coarsening techniques can also be used to generate the sequence of meshes in the three dimensional case.

Appendix: Proof of Lemma 7

In order to show Lemma 7, we follow the analysis presented in [43]. We first show two preliminary results making use of the properties of Sect. 3.

Lemma 8

Let Assumptions 1–4 hold and let ${\widetilde{\varPi }}_j$ be the projection operator on $V_j$ as defined in Lemma 4, for $j=J,J-1$. Then

Proof

Using the triangular inequality, Remark 7 and the approximation estimates of Lemma 4 we have:

where in the last inequality we also used hypotheses (3) and (4). $\square$

Lemma 9

Let Assumptions 1–4 hold. Let and denote by $w_j \in V_j$ the solution of $\forall v \in V_j$ with $j=J-1,J$. Then the following inequality holds:

(28)

Proof

Consider the unique solution $w \in V$ of the problem

$$\begin{aligned} \mathcal {A}(w,v) = (g,v)_{L^2(\varOmega )} \quad \forall v \in V. \end{aligned}$$

Using Corollary 1, we have

(29)

Using the triangular inequality and Remark 7 we have:

Using (29), Lemmas 4 and 8, we have

From the elliptic regularity assumption (2) and hypotheses (3) and (4), we can write

(30)

Now, let $z_j \in V_j$ be the solution of:

Using (30) we get the following estimate:

Then, we have:

from which, together with (30), inequality (28) follows. $\square$

Proof (of Lemma 7)

For any $v_J \in V_J$ we consider the following equality:

(31)

Next, consider the solution $z_j$ of the following problems

By using the definition of $P_J^{J-1}$ and Lemma 9, we have:

Using the last inequality together with (31) we get (26). $\square$