Multigrid algorithms for $\varvec{hp}$-version interior penalty discontinuous Galerkin methods on polygonal and polyhedral meshes

Abstract

In this paper we analyze the convergence properties of two-level and W-cycle multigrid solvers for the numerical solution of the linear system of equations arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polygonal/polyhedral meshes. We prove that the two-level method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the number of smoothing steps, which depends on p, is chosen sufficiently large. An analogous result is obtained for the W-cycle multigrid algorithm, which is proved to be uniformly convergent with respect to the mesh size, the polynomial approximation degree, and the number of levels, provided the number of smoothing steps is chosen sufficiently large. Numerical experiments are presented which underpin the theoretical predictions; moreover, the proposed multilevel solvers are shown to be convergent in practice, even when some of the theoretical assumptions are not fully satisfied.

1 Introduction

The original articles concerned with the construction and mathematical analysis of Discontinuous Galerkin (DG) methods date back over 50 years ago. For hyperbolic partial differential equations, in 1973 Reed and Hill, cf. [53], developed the first DG discretization of the neutron transport equation. Independently, DG methods were constructed for elliptic problems based on weakly enforcing Dirichlet boundary conditions; see, for example, [18, 19, 47, 50]. In particular, we highlight the works of Nitsche [50], Baker [20], Wheeler [61] and Arnold [16], which form the basis of the class of interior penalty DG methods. Since the very early work, DG methods were partially abandoned, in part due to the increase in the number of degrees of freedom compared, for instance, with their conforming counterparts. However, in the last two decades there has been a renewed interest in the field of discontinuous discretizations both from a theoretical and computational viewpoint, cf. [38, 39, 45, 54], for example. This resurgence is due to the inherent advantages offered by DG schemes, such as, for example, the limited interelement communication, which is restricted only to neighbouring elements, the local conservativity property, the simplicity in treating meshes with hanging nodes, and the development of efficient hp-adaptivity refinement strategies. Moreover, recently in [21,22,23, 36] it has been shown that the underlying DG polynomial bases may be efficiently constructed in the physical frame, without needing to map local polynomial spaces defined in a given reference/canonical frame. In this way, DG methods can easily deal with general-shaped elements, including polygonal/polyhedral elements, cf. [3, 4, 6, 8, 21, 33,34,35,36] and the recent review paper [5]. The flexibility of DG methods in handling general meshes has no immediate counterpart in the conforming framework, where the design of suitable finite element spaces for meshes of polygons/polyhedra is far from being a trivial task. Several examples include the Composite Finite Element Method [43, 44], the Polygonal Finite Element Method [58, 59], the Extended Finite Element Method [40], the Mimetic Finite Difference Method [7, 28, 30,31,32, 46] and the most recent Virtual Element Method [1, 2, 25,26,27].

At present, the design of solvers and preconditioners for DG discretizations on nonstandard grids lends itself to huge developments in the field of numerical analysis. Indeed, to the best of our knowledge, the only study regarding solution techniques for this class of problems is reported in [9], where a nonoverlapping Schwarz preconditioner for composite DG finite element methods on complicated domains is analyzed, see also the recent paper [12] where optimal bounds for nonoverlapping Schwarz preconditioners for hp-version DG methods on standard shape-regular grids have been obtained. In the current article we exploit the theoretical framework developed in [36] to study the performance of a two-level and W-cycle multigrid solver. The possibility to employ general-shaped elements in the physical framework makes the choice of multilevel schemes natural. The flexibility afforded by this approach allows us to define the set of grids needed in the multigrid algorithm by agglomeration; thereby, the definition of the associated subspaces is straightforward, since inter-element continuity is not required. This property overcomes the usual difficulties encountered in the construction of agglomeration multigrid schemes in the conforming framework, where the agglomeration strategy must be followed by a proper definition of the conforming subspaces. In [37], for example, the sublevels are obtained by combining a graph based agglomeration algorithm and re-triangulations, thus resulting in a set of non-nested grids, while the associated nested subspaces are defined by introducing suitable interpolation operators. The resulting V-cycle multigrid algorithm converges uniformly with respect to the meshsize h provided that the number of levels is kept fixed.

In this paper we analyze the convergence of a two-level scheme and W-cycle multigrid method for the solution of the linear system of equations arising from the hp-version of the interior penalty DG scheme on polygonal/polyhedral meshes [36], thereby, extending the theoretical framework developed in [13] for standard quasi-uniform triangular/quadrilateral meshes, cf. also [14] for three-dimensional numerical experiments. Our analysis is based on the smoothing and approximation properties associated with the proposed method: the former corresponds to a Richardson iteration, whose study requires a result concerning the spectral properties of the stiffness matrix, while the latter is inherent to the interior penalty DG scheme itself and exploits the error estimates derived in [36]. We show that, under suitable assumptions on the agglomerated coarse grid, both the two-level and the W-cycle multigrid schemes converge uniformly with respect to the granularity of the underlying partition and the polynomial approximation degree p, provided that the number of smoothing steps is chosen of order $p^{2+\mu }$, with $\mu =0,1$. Throughout the analysis, we also track the dependence of the error reduction factor of the two solvers on the geometric properties of the agglomerated grids, thereby recovering a similar result to the case when standard quasi-uniform triangular and/or quadrilateral meshes are employed.

The rest of this 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. Then in Sect. 3, we recall some preliminary analytical results concerning this class of schemes. In Sect. 4 we define the multilevel framework and introduce several technical results. We then focus first on the analysis of the two-level method, followed by the extension to the W-cycle multigrid solver. The main theoretical results are investigated through a series of numerical experiments presented in Sect. 6, where we also present a comparison with an unsmoothed Algebraic Multigrid method. Finally, in Sect. 7 we draw some conclusions.

2 Model problem and discretization

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

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

(1)

with ${\varOmega }\in \mathbb {R}^d$, $d = 2,3$, a convex polygonal/polyhedral domain with Lipschitz boundary and f a given function in $L^2({\varOmega })$.

For the sake of brevity, throughout this article, we write $x\lesssim y$ and $x\gtrsim y$ in lieu of $x\le C y$ and $x\ge C y$, respectively, for a positive constant C 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 required, the constants will be written explicitly.

In view of the forthcoming multigrid analysis, we denote by a sequence of partitions of the domain ${\varOmega }$, each of which consists of disjoint open polygonal/polyhedral elements $\kappa$ of diameter $h_{\kappa }$, such that , $j=1,\ldots ,J$. We denote the mesh size of , $j=1,\ldots ,J$, by . To each , $j=1,\ldots ,J$, we associate the corresponding DG finite element space $V_j$, $j=1,\ldots ,J$, defined as

where denotes the space of polynomials of total degree at most $p_j\ge 1$ on . A suitable choice of the sequences and $\{V_j\}_{j=1}^J$ leads to the so-called h- and p-multigrid schemes. In particular, the $h-$multigrid method is based on employing a constant polynomial approximation degree for each j, $j=1,\ldots ,J$, (i.e., $p_j=p$), on a set of nested partitions , such that the coarse level , $j=2,\ldots ,J$, is obtained by agglomeration from in such a way that

$$\begin{aligned} h_{j-1} \lesssim h_{j} \le h_{j-1} \qquad \forall j = 2,\ldots , J, \end{aligned}$$

(2)

i.e., we assume a bounded variation hypothesis between subsequent levels. In the p-multigrid method, the partition is kept fixed for any j, $j=1,\ldots ,J$, while we assume that the polynomial degrees vary moderately from one level to another, i.e.,

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

(3)

Note that with the above choices we obtain nested finite element spaces $V_j$, $j=1,\ldots ,J$, i.e., $V_1\subseteq V_2\subseteq \cdots \subseteq V_J$.

2.1 Grid assumptions

In this section, we outline some key definitions and assumptions. For any , $j=1,\ldots ,J$, when no hanging nodes/edges are included in the partition, we define the interfaces of the mesh as the set of $(d-1)$-dimensional facets of the elements . The presence of hanging nodes/edges, on the other hand, can be handled by defining the interfaces of as the intersection of the $(d-1)$-dimensional facets of neighboring elements. This implies that, for $d=2$, an interface will always consist of a piecewise linear line segment, i.e., they consist of a set of $(d-1)$–dimensional simplices. However, in general for $d=3$, the interfaces of will consist of general polygonal surfaces. Thereby, we assume that each planar section of each interface of an element may be subdivided into a set of co-planar triangles ($(d-1)$–dimensional simplices). We refer to these $(d-1)$–dimensional simplices, whose union form the interfaces of , as faces. With this notation, we assume that the sub-tessalation of element interfaces into $(d-1)$–dimensional simplices is given. We denote by the set of all mesh faces; moreover, we have that , where is the set of interior element faces of , such that $F \subseteq \partial \kappa ^+ \cap \partial \kappa ^-$ for any , where $\kappa ^\pm$ are two adjacent elements in . The set contains the boundary element faces, i.e., $F\subset \partial {\varOmega }$ for .

We are now ready to introduce the following assumptions on the partitions , $j=1,\ldots ,J$; cf. [33]. In the case of the h-multigrid scheme, these assumptions must be satisfied for the meshes generated by the underlying agglomeration process.

Assumption 1

Given , there exists a set of nonoverlapping (not necessarily shape-regular) d–dimensional simplices $T_{\ell }\subseteq \kappa$, $\ell =1,2,\ldots ,n_\kappa$, such that, for any face $F \subset \partial \kappa$, $\overline{F}= \partial \overline{\kappa }\cap \partial \overline{T_{\ell }}$, for some $\ell$,

$$\begin{aligned} \begin{aligned}&\cup _{\ell =1}^{n_\kappa }\overline{T}_{\ell } \subseteq \overline{\kappa }, \end{aligned} \end{aligned}$$

and the diameter $h_{\kappa }$ of $\kappa$ can be bounded by

$$\begin{aligned} \begin{aligned} h_{\kappa } \lesssim \frac{d | T_{\ell } |}{| F |},\quad \ell =1,2, \ldots ,n_\kappa . \end{aligned} \end{aligned}$$

Remark 1

We point out that Assumption 1 does not put a restriction on either the number of faces that an element possesses, or indeed the measure of a face of an element , relative to the measure of the element itself. This will be particularly important in the agglomeration procedure employed within our h-multigrid method, since as the number of levels increases, the number of faces that the resulting agglomerated elements may contain grows, while their measure, relative to the element measure, may degenerate.

Remark 2

As pointed out in [33], meshes obtained by agglomeration of a finite number of polygons that are uniformly star-shaped with respect to the largest inscribed ball will automatically satisfy Assumption 1. Therefore, from the practical point of view, given a fine-level mesh consisting of uniformly star-shaped elements, a finite number of agglomeration steps will produce a sequence of admissible grids. To allow the number of agglomeration levels to increase arbitrarily one can either (i) ensure that each of the agglomerated meshes satisfy Assumption rm 1; (ii) check, at each level, that the (slightly more restrictive) shape-regularity criterion on the agglomerates is satisfied.

Assumption 2

For any , $j=1,\ldots ,J$, we assume that $h_\kappa ^d\ge |\kappa |\gtrsim h_\kappa ^d,$ with $d=2,3$.

We next introduce the following additional mesh condition, cf. [35], which will be required in order to obtain the inverse estimates presented in Lemma 4.

Assumption 3

Every polytopic element , admits a sub-triangulation into at most $m_\kappa \in \mathbb {N}$ non-overlapping, shape-regular simplices $\mathfrak {s}_i$, $i=1,2,\ldots , m_\kappa$, such that $\bar{\kappa } = \cup _{i=1}^{m_\kappa } \bar{\mathfrak {s}}_i$ and

$$\begin{aligned} |\mathfrak {s}_i| \gtrsim |\kappa | \end{aligned}$$

for all $i=1,\ldots , m_\kappa$. The hidden constant is independent of $\kappa$ and .

In view of the approximation result that will be presented in the next section we also introduce the following additional assumption.

Assumption 4

Let , denote a covering of ${\varOmega }$ consisting of shape-regular d-dimensional simplices . We assume that, for any , there exists such that , , and

$$\begin{aligned} {\max _{\kappa \in \mathcal{T}_j} \,} \text {card} \left\{ \kappa ^\prime \in \mathcal{T}_j : \kappa ^\prime \cap \mathcal {K} \ne \emptyset , ~\mathcal {K}\in \mathcal {T}_j^{\sharp } ~ \text{ such } \text{ that } ~\kappa \subset \mathcal {K} \right\} \lesssim 1. \end{aligned}$$

We also need the following assumption on the quality of agglomerated grids.

Assumption 5

For any , $j=2,\ldots ,J$, we denote by $\kappa ^\pm _{j}$ and $\kappa ^\pm _{j-1}$ the neighboring elements sharing the face F in and , respectively. We assume that there exists ${\varTheta }>0$ such that

We remark that Assumption 5 is satisfied if the agglomeration algorithm preserves the shape-regularity of the elements. In Fig. 1, we show two examples of possible macroelements: the agglomerate on the left is not suitable to guarantee Assumption 5 due to the presence of a dominant dimension, while the element on the right can be considered appropriate. Moreover, we note that the fulfilment of Assumption 5 can be considered a good criterion in evaluating the quality of the agglomerated grids employed in the multigrid algorithm, cf. Fig. 1 for an illustration.

Fig. 1

Examples of agglomerated elements. The agglomerated element on the left violates Assumption 5 whereas the one on the right satisfies Assumption 5

Finally, to keep the notation as simple as possible, in the forthcoming analysis we will assume that, for any $j=1,\ldots ,J$, the decompositions are quasi-uniform.

Assumption 6

For any $j=1,\ldots ,J$, it holds $h_j \approx \min _{\kappa \in \mathcal {T}_j} h_{\kappa }$.

We remark that the above assumption can be weakened and only a local bounded variation property is needed for our theoretical analysis; see Remark 4 below for details.

2.2 DG formulation

The definition of the proceeding DG method is based on employing suitable jump and average operators. To this end, for (sufficiently smooth) vector- and scalar-valued functions $\varvec{\tau }$ and v, respectively, we define jumps and averages across , $j=1,\ldots ,J$, as follows:

where $v^\pm$ and $\varvec{\tau }^\pm$ denote the traces of v and $\varvec{\tau }$ on F taken from the interior of $\kappa ^\pm$, respectively, and $\mathbf {n}^\pm$ the outward unit normal vectors to $\partial \kappa ^\pm$, respectively, cf. [17]. On any level j, $j=1,\ldots ,J$, we consider the bilinear form , corresponding to the symmetric interior penalty DG method, defined by

where denotes the interior penalty stabilization function , which is defined by

(5)

with $C_{\sigma }^j>0$ independent of $p_j$, |F| and $|\kappa |$.

In this article, we develop two-level and W-cycle multigrid schemes to compute the solution of the following problem on the finest level J: find $u_J\in V_J$ such that

(6)

3 Preliminary results

We first recall the following trace-inverse inequality for polygonal/polyhedral elements.

Lemma 1

Assume that the sequence of meshes , $j=1,\ldots ,J$, satisfies Assumption 1. Let , $j=1,\ldots ,J$, be a polygonal/polyhedral element, then the following bound holds

(7)

where ${ \mathsf {C}^{j}_{\mathsf {inv}}}$ is independent of $|\kappa |$, $p_j$ and v.

The proof can be obtained with trivial modifications with respect to the ones given in [33, 34]. For the sake of completeness we report it and refer to [33, 34] for further details.

Proof

From Assumption 1, there exists a set of nonoverlapping (not necessarily shape-regular) d-simplicial elements $T_{\ell }\subseteq \kappa$ such that, given a face $F\subset \partial \kappa$, for some $\ell$, $1\le \ell \le n_\kappa$, $\overline{F}=\partial \overline{\kappa } \cap \partial \overline{T_{\ell }}$. Therefore,

as required. Here, in the first inequality we have employed the following classical trace-inverse estimate on d-simplicial elements

cf. [41, 56], for example; the second bound exploits Assumption 1, namely, that $| F |{| T_\ell |}^{-1} \lesssim dh^{-1}_{\kappa }$.

Next, we endow the finite element spaces $V_j$, $j=1,\ldots ,J$, with the following DG norm:

The well–posedness of the DG formulation is established in the following lemma

Lemma 2

Assume that the sequence of meshes , $j=1,\ldots ,J$, satisfies Assumption 1 and that the constant $C_\sigma ^j$, $j=1,\ldots ,J$, appearing in the definition (5) of the stabilization function is chosen sufficiently large. Then, the following continuity and coercivity bounds, respectively, hold

where ${\mathsf {C}_{\mathsf {cont}}}$ and ${\mathsf {C}_{\mathsf {coer}}}$ are positive constants, independent of the discretization parameters.

The proceeding error estimates are based on the following approximation result, which is a simplified version of the analogous bound presented in [36, Proof of Theorem 5.2]. To this end, we define $\mathcal {E}:H^s({\varOmega }) \rightarrow H^s({\mathbb R}^d)$, $s \in {\mathbb N}_0$, such that $\mathcal {E}v|_{{\varOmega }}=v$, to denote the extension operator presented in Stein [57].

Lemma 3

Assume that Assumptions 1 and 4 hold. Let $v|_\kappa \in H^{k}(\kappa )$, $k>d/2$, such that $\mathcal {E}v|_{\mathcal {K}}\in H^{k}(\mathcal {K})$, for each , $j=1,\ldots ,J$, where $\kappa \subset \mathcal {K}$, $\mathcal {K}\in \mathcal {T}_j^{\sharp }$. 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 the constant ${\mathsf {C}^{j}_{\mathsf {interp}}}$ depends on the shape-regularity constant of the covering $\mathcal {T}_j^{\sharp }$, but is independent of the discretization parameters, as well as the number of faces per element and the relative measure of the faces. Here, $\mu =0$ whenever a $p-$optimal interpolant can be constructed and $\mu =1$ otherwise.

Next, we state error bounds for the underlying interior penalty DG scheme in terms of both the DG and $L^2({\varOmega })$-norms.

Theorem 7

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

If the solution u of (1) satisfies $u|_\kappa \in H^k(\kappa )$, $k>1+d/2$, such that $\mathcal {E}u|_{\mathcal {K}}\in H^{k}(\mathcal {K})$, for each , $j=1,\ldots ,J$, where $\kappa \subset \mathcal {K}$, $\mathcal {K}\in \mathcal {T}_j^{\sharp }$, then the following bounds hold

where $s = \min \{p_j+1,k\}$ and the constants ${\mathsf {G}^{j}}$ and ${\mathsf {C}^{j}_{L^2}}$ are independent of the discretization parameters. Here, $\mu =0$ whenever a $p-$optimal interpolant can be constructed and $\mu =1$ otherwise.

Before proceeding with the proof, we point out that the above error bounds hold provided Assumptions 1 and 4 are satisfied; however, we stress that no limitation is placed on the maximum number of faces that each polygonal/polyhedral element may possess. Moreover, there is no restriction on the relative size of each face of an element compared to its diameter.

Proof

The error bound (10) stems from the general result derived in [36, Theorem 5.2] under the condition that Assumptions 1 and 4 hold. Thereby, we now proceed with the proof of the bound on the $L^2({\varOmega })$-norm of the error, cf. (11). To this end, we employ a standard duality argument: let $w\in V$, be the solution of the problem

$j=1,\ldots ,J$. Exploiting a standard elliptic regularity assumption, we note that

According to Galerkin orthogonality, we immediately obtain

for all $w_I\in V_j$. Hence, selecting $w_I=\tilde{{\varPi }}_j w$, employing (9) gives

which together with (10) gives the desired result.

Equipped with Assumption 3, we now quote the following result from [35]; for brevity the proof is omitted. However, we point out that the proof presented in [35] holds under slightly weaker mesh conditions; for simplicity of presentation, this level of detail is omitted.

Lemma 4

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

where ${\mathsf {C}_{\mathsf {I}}^{j}}>0$ is independent of the discretization parameters.

The inverse estimate presented in Lemma 4 is fundamental to the proof of the following upper bound on the maximum eigenvalue of . We recall that the analogous result on standard grids can be found in [10], cf. also [11].

Theorem 8

Given that Assumptions 1, 2, 3, and 6 hold, then for any $u\in V_j$, $j=1,\ldots ,J$, we have that

where the constant ${\mathsf {C}^{j}_{\mathsf {eig}}}$ is independent of the discretization parameters.

Proof

Given the continuity of the bilinear forms stated in Lemma 2, we restrict ourselves to estimate the two terms involved in the DG norm. The local contributions of the $H^1$ seminorm can be simply bounded by applying Lemma 4 and the quasi-uniformity of the partition, i.e.,

To bound the norm of the jump across , we employ the inverse inequality (7); thereby, we get

The statement of the theorem immediately follows based on summing the above bounds.

The theoretical results derived in this section form the basis of the analysis of the proposed multigrid algorithms presented in the following section.

4 Two-level and W-cycle multigrid algorithms

The forthcoming analysis is based on the classical multigrid theoretical framework already employed in [13] for high-order DG schemes on standard quasi-uniform meshes. The two key ingredients in the construction of our proposed multigrid schemes are the inter-grid transfer operators and the smoothing scheme. The prolongation operator connecting the space $V_{j-1}$ to $V_{j}$, $j=2,\ldots ,J$, is denoted by $I^{j}_{j-1}:V_{j-1}\rightarrow V_{j}$, while its adjoint with respect to the $L^2({\varOmega })$-inner product $(\cdot ,\cdot )$ is the restriction operator $I^{j-1}_{j}:V_{j}\rightarrow V_{j-1}$ defined by

$$\begin{aligned} \left( I^{j}_{j-1}v,w\right) = \left( v,I^{j-1}_{j}w\right) \qquad \forall v\in V_{j-1},w\in V_{j}. \end{aligned}$$

As a smoothing scheme, we choose a Richardson iteration, whose operator is defined as:

$$\begin{aligned} B_j = {\varLambda }_j\text {Id}_j, \end{aligned}$$

(12)

with $\text {Id}_j$ the identity operator on level $V_j$, and ${\varLambda }_j\in \mathbb {R}$ is an upper bound for the spectral radius of the operator $A_j:V_j\rightarrow V_j$, defined by

(13)

For the definition of the solvers, we first address the two-level method. Given the problem $A_J u_J = f_J$ with $A_J:V_J\rightarrow V_J$ defined according to (13), and $f_J\in V_J$ such that

$$\begin{aligned} (f_J,v) = \int _{\varOmega } f v\ dx\quad \forall v\in V_J, \end{aligned}$$

in Algorithm 1 we outline the two-level cycle, where $\mathsf {MG_{2lvl}} (z_0,m_1,m_2)$ denotes the approximate solution obtained after one iteration, with initial guess $z_0$ and $m_1$, $m_2$ pre- and post-smoothing steps, respectively.

As a multilevel extension of Algorithm 1, we consider a standard W-cycle scheme. On level j, we consider $A_j z=g$, for a given $g\in V_j$. The approximate solution obtained by applying the j-th level iteration to the above linear system, with initial guess $z_0$ and $m_1$, $m_2$ pre- and post-smoothing steps, respectively, is denoted by $\mathsf {MG}_\mathcal {W} (j,g,z_0,m_1,m_2)$. On the coarsest level $j = 1$, the corresponding subproblem is solved based on employing a direct method, i.e.,

$$\begin{aligned} \mathsf {MG}_\mathcal {W} (1,g,z_0,m_1,m_2) = A_1^{-1}g, \end{aligned}$$

while for $j>1$ we apply the recursive procedure outlined in Algorithm 2. We observe that Algorithm 1 can be considered as a special case of Algorithm 2, corresponding to $J=2$.

4.1 Convergence analysis of the two-level method

We first define the following norms based on the operator $A_j$, $j=1,\ldots ,J$,

Hence,

In order to undertake the convergence analysis of the two-level solver outlined in Algorithm 1, we follow the approach developed in [13]. We then provide an estimate based on the error propagation operator, which is defined by

$$\begin{aligned} \mathbb {E}_{m_1,m_2}^{\mathsf {2lvl}}v = G_J^{m_2} \left( \text {Id}_J-I_{J-1}^JP_J^{J-1}\right) G_J^{m_1}, \end{aligned}$$

(14)

with $G_J = \text {Id}_J-B_J^{-1}A_J$, and the operator $P_{J}^{J-1}:V_{J}\rightarrow V_{J-1}$ defined as

(15)

We now study separately the smoothing property and the approximation property. We also point out that that by Theorem 8, we can bound ${\varLambda }_j$, $j=1,\ldots ,J$, in (12) as follows

$$\begin{aligned} {\varLambda }_j\lesssim {\mathsf {C}^{j}_{\mathsf {eig}}}\frac{p_j^4}{h_{j} ^2}. \end{aligned}$$

The last result is employed to prove the smoothing property in the next lemma; see [13, Lemma 4.3] for the proof.

Lemma 5

(Smoothing property) Given that Assumptions 1, 2, 3 and 6 hold. for any $v\in V_j$, $j=1,\ldots ,J$, we have

(16)

The approximation property stems from exploiting the $L^2({\varOmega })$ error estimates stated in (11) on levels J and $J-1$.

Lemma 6

(Approximation property) Assume that Assumptions 1 and 4 hold. Let $\mu$ be defined as in Lemma 3. For any $v\in V_J$, the following inequality holds

(17)

Proof

For any $v\in V_J$, we consider the following equality

Next, we consider the solution $\eta$ of the following problem

$$\begin{aligned} \begin{aligned} \int _{{\varOmega }} \nabla \eta \cdot \nabla v\ dx&= \int _{{\varOmega }}\phi v\ dx&\forall v\in V, \end{aligned} \end{aligned}$$

for $\phi \in L^2({\varOmega })$, and let $\eta _J\in V_J$ and $\eta _{J-1}\in V_{J-1}$ be the corresponding DG approximations in $V_J$ and $V_{J-1}$, respectively, given by

(19)

By Theorem 7 and the hypotheses (2) and (3), we deduce that

and from a standard elliptic regularity assumption, it follows that

(20)

Recalling the definition of $P_{J}^{J-1}$, cf. (15), and (19), for any $w\in V_{J-1}$, we get

Hence,

$$\begin{aligned} \eta _{J-1} = P_J^{J-1}\eta _J. \end{aligned}$$

(21)

According to [13, Lemma 4.1], the following generalized Cauchy–Schwarz inequality holds

(22)

for any $v,w\in V_J$. We now employ (19) and the definition of $P^{J-1}_J$ in (15), followed by (21), the Cauchy–Schwarz inequality (22) and the error estimates (20), to get

(23)

Substituting (23) into (18) gives the desired result.

The convergence result for the two-level method, involving the error propagation operator $\mathbb {E}^{\mathsf {2lvl}}_{m_1,m_2}$ defined in (14), is obtained by combining Lemma 5 and Lemma 6.

Theorem 9

Assume that Assumptions 1, 2, 3, 4, and 6 hold. Let $\mu$ be defined as in Lemma 3. Then, there exists a positive constant ${\mathsf {C}_{\mathsf {2lvl}}}$ independent of the mesh size and the polynomial approximation degree, such that

(24)

for any $v\in V_J$, with

$$\begin{aligned} {\varSigma }_J={\widetilde{\mathsf {C}}_{J,J-1}}\frac{p_{J}^{2{+\mu }}}{(1+m_1)^{1/2}(1+m_2)^{1/2}}, \end{aligned}$$

where ${\widetilde{\mathsf {C}}_{J,J-1}} = {\mathsf {C}^{J}_{\mathsf {eig}}}({\mathsf {C}^{J}_{L^2}}+{\mathsf {C}^{J-1}_{L^2}})$. Therefore, the two-level method converges uniformly provided the number of pre- and post-smoothing steps satisfy

$$\begin{aligned} (1+m_1)^{1/2}(1+m_2)^{1/2}\ge \chi {\widetilde{\mathsf {C}}_{J,J-1}}p_{J}^{2{+\mu }}, \end{aligned}$$

for a positive constant $\chi >{\mathsf {C}_{\mathsf {2lvl}}}$.

Proof

The statement of the theorem follows in a straightforward manner by applying the smoothing property (16) twice, the approximation property (17) and exploiting the bounded variation assumptions (2) and (3).

We observe that the geometric properties of the partitions are hidden in the constant ${\widetilde{\mathsf {C}}_{J,J-1}}$. As a consequence, a good quality agglomerated coarse grid is fundamental to guarantee a mild condition on the minimun number of smoothing steps.

4.2 Convergence of the W-cycle multigrid algorithm

We first need to establish the equivalence between DG norms on subsequent grid levels. We point out that, in contrast to the case of standard quasi-uniform grids presented in [13], such an equivalence result does not follow in a straightforward manner; indeed, here we need to exploit Assumption 5 introduced in the previous section. Under these assumptions, the proof of the following result follows immediately.

Lemma 7

Assuming Assumption 5 holds, then for any $v\in V_{j-1}$, $j = 2,\ldots ,J$, we have that

(25)

where ${\mathsf {C}_{\mathsf {equiv}}}= {\mathsf {C}_{\mathsf {equiv}}}({\varTheta })$, in general, depends on the quality of the agglomerated grids.

Lemma 7 is essential to deduce the stability of the operators $I_{j-1}^j$ and $P_{j}^{j-1}$, $j = 2,\ldots ,J$. In particular, we state the following bounds.

Lemma 8

Assuming Assumption 5 holds, then there exists a constant ${\mathsf {C}_{\mathsf {stab}}}\ge 1$, independent of the mesh size, the polynomial approximation degree and the level j, $j = 2,\ldots ,J$, such that

The proof of Lemma 8 is based on employing inequality (25); for details, see [13, Lemma 4.6].

Remark 3

We stress that the constant ${\mathsf {C}_{\mathsf {stab}}}$ depends on ${\mathsf {C}_{\mathsf {equiv}}}$ in (25), which means that the quality of the agglomerated meshes plays a crucial role in keeping this constant bounded, thus resulting in the uniformity with respect to the mesh size and the number of levels as shown in Theorem 10 below.

The error propagation operator associated to Algorithm 2 is defined as

$$\begin{aligned} \left\{ \begin{aligned} \mathbb {E}_{1,m_1,m_2}v&= 0\\ \mathbb {E}_{j,m_1,m_2}v&= G_j^{m_2} \left( \text {Id}_j-I_{j-1}^j \left( \text {Id}_j- \mathbb {E}_{j-1,m_1,m_2}^2\right) P_j^{j-1}\right) G_j^{m_1}v, \ j = 2,\ldots ,J, \end{aligned} \right. \end{aligned}$$

(28)

where $G_j = \text {Id}_j-B_j^{-1}A_j$ and $P_j^{j-1}$ is defined analogously to (15), cf. [29, 42]. Then the convergence estimate for the W-cycle multigrid scheme follows from Theorem 9 and the stability estimates (26) and (27).

Theorem 10

Assume that Assumptions 1, 2, 3, 4, 5, and 6 hold. Let $\mu$ be defined as in Lemma 3. Let ${\mathsf {C}_{\mathsf {2lvl}}}$ and ${\mathsf {C}_{\mathsf {stab}}}$ be defined as in Theorem 9 and Lemma 8, respectively, and let ${\widetilde{\mathsf {C}}_{j,j-1}}$ be defined as in Theorem 9, but on the level j, i.e., ${\widetilde{\mathsf {C}}_{j,j-1}}={\mathsf {C}^{j}_{\mathsf {eig}}}({\mathsf {C}^{j}_{L^2}}+{\mathsf {C}^{j-1}_{L^2}})$, $j=2,\ldots , J$. Then, there exists a constant ${\widehat{\mathsf {C}}}>{\mathsf {C}_{\mathsf {2lvl}}}$, independent of the mesh size, the polynomial approximation degree and the level j, $j = 1,\ldots ,J$, such that, if the number of pre- and post-smoothing steps satisfy

$$\begin{aligned} (m_1+1)^{1/2}(m_2+1)^{1/2}\ge \left\{ \begin{aligned}&p_{j}^{2{+\mu }}{\widetilde{\mathsf {C}}_{j,j-1}}\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}\quad&\text {if } {\widetilde{\mathsf {C}}_{j-1,j-2}}\le {\widetilde{\mathsf {C}}_{j,j-1}},\\&p_{j}^{2{+\mu }}\frac{({\widetilde{\mathsf {C}}_{j-1,j-2}})^2}{{\widetilde{\mathsf {C}}_{j,j-1}}}\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}\quad&\text {otherwise,} \end{aligned}\right. \end{aligned}$$

(29)

then

(30)

with

$$\begin{aligned} {\varSigma }_j={\widetilde{\mathsf {C}}_{j,j-1}}\frac{p_{j}^{2{+\mu }}}{(1+m_1)^{1/2}(1+m_2)^{1/2}}. \end{aligned}$$

(31)

Proof

The proof follows the derivation of the analogous result presented in [13, Theorem 4.7]. For $j = 1$, the statement of the theorem trivially holds. For $j>1$, by an induction hypothesis, we assume that (30) holds for $j-1$. By the definition of the error propagation operator $\mathbb {E}_{j,m_1,m_2}v$ in (28), it follows that

The first term corresponds to a two-level method between level j and $j-1$. We now observe that the smoothing property of Lemma 5 and the approximation property of Lemma 6 can be extended to any level $V_j$, $j=2,\ldots ,J$, and we therefore have, by Theorem 9, that

The bound on the second term is obtained by applying the smoothing property (16) for $j=2,\ldots ,J$, the stability estimates (26) and (27) and the induction hypothesis; thereby, we get

We then obtain

We now observe that the following relation between ${\varSigma }_{j-1}$ and ${\varSigma }_{j}$ holds

$$\begin{aligned} {\varSigma }_{j-1}={\varSigma }_{j}\left( \frac{p_{j-1}}{p_j} \right) \left( \frac{{\widetilde{\mathsf {C}}_{j-1,j-2}}}{{\widetilde{\mathsf {C}}_{j,j-1}}} \right) \le {\varSigma }_{j}\left( \frac{{\widetilde{\mathsf {C}}_{j-1,j-2}}}{{\widetilde{\mathsf {C}}_{j,j-1}}} \right) . \end{aligned}$$

Using the above identity we have that

$$\begin{aligned}&{\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_j+({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2{\varSigma }_{j-1}^2 \\&\quad \le \left( {\mathsf {C}_{\mathsf {2lvl}}}+({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2 \frac{({\widetilde{\mathsf {C}}_{j-1,j-2}})^2}{{\widetilde{\mathsf {C}}_{j,j-1}}} \frac{p_{j}^{2{+\mu }}}{(1+m_1)^{1/2}(1+m_2)^{1/2}}\right) {\varSigma }_j. \end{aligned}$$

We then observe that if $m_1$ and $m_2$ are such that

$$\begin{aligned} (1+m_1)^{1/2}(1+m_2)^{1/2} \ge p_{j}^{2{+\mu }}\frac{({\widetilde{\mathsf {C}}_{j-1,j-2}})^2}{{\widetilde{\mathsf {C}}_{j,j-1}}}\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}, \end{aligned}$$

it follows that ${\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_j+({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2{\varSigma }_{j-1}^2\le {\widehat{\mathsf {C}}}{\varSigma }_j$. Notice that for ${\widetilde{\mathsf {C}}_{j-1,j-2}}\le {\widetilde{\mathsf {C}}_{j,j-1}}$ the above condition on $m_1$ and $m_2$ can be simplified as follows

$$\begin{aligned} (1+m_1)^{1/2}(1+m_2)^{1/2}\ge p_{j}^{2{+\mu }}{\widetilde{\mathsf {C}}_{j,j-1}}\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}, \end{aligned}$$

and therefore we obtain ${\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_j+({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2{\varSigma }_{j-1}^2\le {\widehat{\mathsf {C}}}{\varSigma }_j$, and the proof is complete.

As in the two-level case, inequality (30) implies that the convergence of the method is guaranteed if the number of smoothing steps is chosen sufficiently large, cf. (29). Moreover, compared to the case of standard quasi-uniform grids, cf. [13], the bound (29) on the number of smoothing steps involves a dependence on the geometric properties of the underlying agglomerated meshes, which in principle, could lead to shape-regularity conditions on the hierarchy of grids employed. However, we remark that, in practice, the numerical simulations indicate that the proposed multigrid algorithms converge uniformly, even when low quality agglomerated grids are employed; moreover, an increase in the polynomial order does not seem to require a higher number of smoothing steps to obtain a convergent iteration, cf. Sect. 6 for details.

Remark 4

Whenever the agglomerated grids are not quasi-uniform, i.e., Assumption 6 does not hold, Theorems 9 and  10 still hold. More precisely, we need to introduce the ratio $\theta _j$ between the maximum and minimum element size on level j, i.e.,

Assuming there exists a constant ${\mathsf {C}_{\mathsf {mesh}}}$, independent of the granularity of the mesh, such that

$$\begin{aligned} \theta _j\le {\mathsf {C}_{\mathsf {mesh}}}, \quad j=1,\ldots ,J, \end{aligned}$$

then the results in Theorem 9 and Theorem 10 hold with

$$\begin{aligned} {\varSigma }_j=\theta _j^2{\widetilde{\mathsf {C}}_{j,j-1}}\frac{p_{j}^{2{+\mu }}}{(1+m_1)^{1/2}(1+m_2)^{1/2}}, \end{aligned}$$

cf. (31). Moreover, the bound (29) is modified as follows

$$\begin{aligned} (1+m_1)^{1/2}(1+m_2)^{1/2}\ge \left\{ \begin{aligned}&\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}\frac{({\mathsf {C}_{\mathsf {mesh}}})^4}{\theta _j^2}{\widetilde{\mathsf {C}}_{j,j-1}}p_{j}^{2{+\mu }}&\quad \text {if}\, {\widetilde{\mathsf {C}}_{j-1,j-2}}\le {\widetilde{\mathsf {C}}_{j,j-1}},\\&\frac{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}^2}{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}} \frac{({\mathsf {C}_{\mathsf {mesh}}})^4}{\theta _j^2}\frac{({\widetilde{\mathsf {C}}_{j-1,j-2}})^{2}}{{\widetilde{\mathsf {C}}_{j,j-1}}}p_{j}^{2{+\mu }}\quad&\text {otherwise.} \end{aligned}\right. \end{aligned}$$

(32)

Remark 5

We recall that in Theorem 10 and Remark 4, in order to guarantee the convergence of the method, we require a lower bound on the number of smoothing steps, cf. (29) and (32). Such a condition guarantees that the resulting W-cycle method is uniformly convergent with respect to the mesh size, the polynomial approximation degree, and the number of levels. In fact, for ${\widetilde{\mathsf {C}}_{j-1,j-2}}\le {\widetilde{\mathsf {C}}_{j,j-1}}$, from (32) and using that $\theta _j\le {\mathsf {C}_{\mathsf {mesh}}}$, $j=1,\ldots ,J$, we obtain

$$\begin{aligned} \begin{aligned} {\widehat{\mathsf {C}}}{\varSigma }_j =\,&{\widehat{\mathsf {C}}}\theta _j^2{\widetilde{\mathsf {C}}_{j,j-1}} \frac{p_{j}^{2{+\mu }}}{(1+m_1)^{1/2}(1+m_2)^{1/2}} \\ \le&\frac{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}}\frac{\theta _j^4}{({\mathsf {C}_{\mathsf {mesh}}})^4} \le \frac{{\widehat{\mathsf {C}}}-{\mathsf {C}_{\mathsf {2lvl}}}}{({\mathsf {C}_{\mathsf {stab}}})^2{\widehat{\mathsf {C}}}}< 1. \end{aligned} \end{aligned}$$

An analogous result can be obtained for ${\widetilde{\mathsf {C}}_{j-1,j-2}}> {\widetilde{\mathsf {C}}_{j,j-1}}$. Moreover, we note that we have considered the general setting of (32), since (29) can be regarded as a particular case.

5 Weaker geometric assumptions on the quality of the agglomerates

In this section we briefly provide some details regarding the minimal regularity requirements needed to guarantee that our geometric $h-$multigrid method is convergent. Indeed, the theoretical analysis of our two-level and W-cycle multigrid algorithms solver can be undertaken under weaker mesh assumptions on the shape of the elements and the quality of the agglomerated grids than those satisfying Assumptions 1 and 3.

Definition 1

For each , $j=1,\ldots ,J$, we denote by the set of all possible d-simplices contained in $\kappa$ and having at least one face in common with $\kappa$. Moreover, we denote by $\kappa _F^\flat$, an element in sharing a face F with .

Secondly, as an alternative to Assumption 1, we may consider the following condition.

Assumption 11

(Weaker mesh regularity assumptions) For any $j=1, \ldots , J$, the mesh satisfies the following regularity properties.

11.a :

The number of faces of any , $j=1,\ldots ,J$, is uniformly bounded;

11.b :

For any , $j=2,\ldots ,J$, we denote by $\kappa ^\pm _{j}$ and $\kappa ^\pm _{j-1}$ the neighboring elements sharing the face F in and , respectively. We assume that there exists ${\varTheta }>0$ such that

Assumption 11.a might in principle be critical in our multilevel framework, because the number of faces grows with the number of levels due to the agglomeration process. As a consequence, this assumption is only satisfied if the number of levels is kept limited. However, it will be demonstrated in Sect. 6, that this assumption only seems to be required from a theoretical point of view.

A key step in the weakening of the mesh conditions is establishing an inverse inequality of the form outlined in Lemma 1, which holds for general polygonal/polyhedral elements. Indeed, assuming Assumption 11.a is satisifed, then following inverse inequality holds, cf. [36, Lemma 4.4].

Lemma 9

Let , $j=1,\ldots ,J$, be a polygonal/polyhedral element, and let $F\subset \partial \kappa$ be one of its faces. Then, for each , we have

with

$$\begin{aligned} { \mathsf {C}_{\mathsf {INV}}(j,p_j, \kappa , F)}=C\min \left\{ \frac{|\kappa |}{\sup _{\kappa _F^\flat \subset \kappa }|\kappa _F^\flat |},p_j^{2d}\right\} . \end{aligned}$$

and as in Definition 1. The positive constant C is independent of $|\kappa |/\sup _{\kappa _F^\flat \in \kappa }|\kappa _F^\flat |$, $p_j$ and v.

Equipped with Lemma 9, the interior penalty stabilization function $\sigma _j$, must be appropriately redefined; see [36] for details. Finally, we observe that Assumption 11.b, together with (3), implies that

6 Numerical results

In this section we present several numerical simulations to verify the theoretical estimates provided in Theorems 9 and  10 in the case of a two dimensional problem on the unit square ${\varOmega }= (0,1)^2$. For the numerical tests, we consider the two sets of meshes shown in Figs. 2 and 3. The first set of initial grids are shown in Fig. 2 (top line) and consist of 512 (Set 1), 1024 (Set 2), 2048 (Set 3) and 4096 (Set 4) polygonal elements. These meshes have been generated using the software package PolyMesher [60]. We also consider an initial set of decompositions constisting of 582 (Set 1), 1086 (Set 2), 2198 (Set 3) and 4318 (Set 4) shape-regular triangles as depicted in Fig. 3 (top line). Each initial grid is then subsequently coarsened in order to obtain a sequence of nested partitions by employing the software package MGridGen [48, 49].

Fig. 2

Sequences of agglomerated grids employed for numerical simulations. Top line fine grids consisting of 512 (Set 1), 1024 (Set 2), 2048 (Set 3) and 4096 (Set 4) polygonal elements

Fig. 3

Sequences of agglomerated grids employed for numerical simulations. Top line fine grids consisting of 582 (Set 1), 1086 (Set 2), 2198 (Set 3) and 4318 (Set 4) triangular elements

Before testing the performance of the two-level and W-cycle multigrid solvers presented in Algorithm 1 and Algorithm 2, respectively, we first address the issue of the choice of the penalization coefficient $C_{\sigma }^j$ in (4). According to Lemma 2, the bilinear form is coercive provided that $C_\sigma ^j$ is chosen large enough. In Table 1, we report the coercivity constant ${\mathsf {C}_{\mathsf {coer}}}$ of (8) for a fixed value of $C_\sigma ^j \equiv C_\sigma = 10$ for $j=1,\ldots ,4$. We observe that the bilinear form is uniformly coercive for a constant value of the penalization coefficient, which is of the same magnitude as the one typically employed on standard shape-regular triangular meshes. As a consequence, in the following, we set $C_\sigma ^j \equiv C_\sigma = 10$ for $j=1,\ldots ,4$.

Table 1 Value of the coercivity constant ${\mathsf {C}_{\mathsf {coer}}}$ for the sets of grids considered in Fig. 2 with $C_{\sigma }^j = C_{\sigma } = 10$, $j = 1,\ldots$,4

We now consider the sequence of the grids shown in Fig. 2, Set 1, and numerically evaluate the constant ${\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_J$, $J=2$, in Theorem 9 and the constant ${\widehat{\mathsf {C}}}{\varSigma }_3$ in Theorem 10, for the h-version of the two solvers, based on selecting $m_1=m_2=m=2p^2$, cf. Fig. 4. Here, we observe that ${\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_2$ and ${\widehat{\mathsf {C}}}{\varSigma }_3$ are roughly (asymptotically) constant, as the polynomial degree p increases; thereby, this implies that ${\widetilde{\mathsf {C}}_{J,J-1}}$, $J=2,3$, respectively, is approximately $\mathcal {O}(1)$, as p increases. Notice also that, in practice, the parameter $\mu =0$, even whenever a p–optimal interpolant cannot be explicetely constructed.

Fig. 4

Estimates of ${\mathsf {C}_{\mathsf {2lvl}}}{\varSigma }_J$ and ${\widehat{\mathsf {C}}}{\varSigma }_3$ in (24) and (30), respectively, as a function of p, and $m_1=m_2=m=2p^2$. Sequence of agglomerated meshes shown in Fig. 2, Set 1

Next, we investigate the performance of the two-level and W-cycle multigrid schemes in terms of the convergence factor

$$\begin{aligned} \rho = \exp \left( \frac{1}{N}\ln \frac{\Vert \mathbf {r}_{N}\Vert _2}{\Vert \mathbf {r}_{0}\Vert _2}\right) , \end{aligned}$$

where N denotes the number of iterations required to attain convergence up to a (relative) tolerance of $10^{-8}$ and $\mathbf {r}_{N}$ and $\mathbf {r}_{0}$ are the final and initial residual vectors, respectively. In Table 2, we report the iteration counts and the convergence factor (in parenthesis), needed to attain convergence of the h-version of the two-level (TL) method and W-cycle multigrid scheme (with 3 and 4 levels), as a function of the number of elements (given by the choice of different grid sets), and the number of smoothing steps ($m_1=m_2=m$). Here, we have fixed the polynomial approximation order on each level $p_j \equiv p=1$. We first observe that, although the agglomerated grids, in general, do not necessarily strictly satisfy Assumption 2, the number of iterations, for fixed m, does not significantly increase with the number of elements in the underlying mesh; moreover, for the W-cycle solver, the number of iterations remains bounded with the number of levels. As expected, the convergence is faster for larger values of m and the solvers are convergent provided the number of smoothing steps is sufficiently large. For each grid, we have also reported the iteration counts ${\mathsf {N}_{\mathsf {it}}^{\mathsf {CG}}}$ for the Conjugate Gradient (CG) method, which shows that the two proposed solvers outperform the CG scheme in terms of the number of iterations required to attain convergence, even when a small number of smoothing steps are employed. For the sake of comparison, we also report the iteration counts ${\mathsf {N}_{\mathsf {it}}^{\mathsf {PCG}}}$ for the Preconditioned Conjugate Gradient (PCG) method, based on employing a simple block Jacobi preconditioner. The extension to polytopic grids of the domain decomposition preconditioning techniques, such as, for example, the ones proposed in [10, 12, 15], in the DG setting, or in [52, 55], in the conforming setting, are currently under investigation and will be the subject of future research. Table 3 presents analogous results for the first three sets of meshes, in the case when $p=3$. Here, we observe that, as expected, the convergence factor increases, but the increase in p does not require an increase in the minimal number of smoothing steps needed to ensure that the underlying multilevel solvers are convergent.

Table 2 Iteration counts and converge factor (in parenthesis) of the h-version of the two-level and W-cycle solvers and iteration counts of the CG/PCG methods as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=1$)

Table 3 Iteration counts of the h-version of the two-level and W-cycle solvers as a function of m and the number of levels and iteration counts of the CG/PCG methods ($C_\sigma ^j \equiv C_\sigma =10$, $p=3$)

Next, we consider the sets of nested grids obtained by agglomerating the shape-regular triangular meshes shown in Fig. 3, first row. The initial triangular decompositions constist of 528 (Set 1), 1086 (Set 2), 2198 (Set 3) and 4318 (Set 4) elements, cf. Fig. 3, first row. In Table 4, we show the iteration counts needed to attain convergence with respect to a fixed tolerance of $10^{-8}$ as a function of the set (i.e., the number of elements) and the number of smoothing steps of the h-version of the two-level and W-cycle multigrid solvers, with $p_j=p=1$. We recall that, as in the previous numerical test, we have considered $C_\sigma ^j \equiv C_\sigma =10$, for each j. The results are similar to the case of initial polygonal meshes, with uniform convergence with respect to the granularity of the mesh and, in the case of the W-cycle solver, also with respect to the number of levels. We again attain improved performance, compared to the standard CG and PCG methods, in terms of the number of iterations required to attain convergence.

Table 4 Iteration counts and converge factor (in parenthesis) of the h-version of the two-level and W-cycle solvers and iteration counts of the CG and PCG methods as a function of m ($C_\sigma ^j \equiv C_\sigma =10$, $p=1$)

Finally, we present a more exhaustive investigation of the effect of increasing p while keeping fixed the number of smoothing steps. For this set of experiments, we consider a fine grid of 1024 elements and the corresponding agglomerated meshes (Set 2 in Fig. 2). In Table 5 we report the iteration counts of the h-version of the two-level and W-cycle solvers as a function of p, employing $m=5$ pre- and post- smoothing steps. We observe that, as expected, even though both multilevel solvers converge for a fixed value of m, the number of iterations required to reduce the relative residual below the given tolerance grows with increasing p. However, the two-level and W-cycle multigrid solvers still employ less iterations, than the number required by both the CG and PCG methods, cf. the last two columns of Table 5. As a numerical comparison, we have solved the correspoding linear systems of equations employing an unsmoothed aggregation Algebraic Multigrid (AMG) algorithm based on three popular algebraic agglomeration strategies. More precisely, in the considered AMG methods the agglomerates are formed, at a purely algebraic level, by using either the maximal independent set, the (approximate) maximum weighted matching or the greedy aggregation algorithms, and the resulting coarse levels are then employed as before within a W-cycle iteration with a Richardon smoother with $m=5$ pre- and post-smoothing steps. In Table 6 we report, for each of the considered agglomeration strategies, the number of agglomeration levels (N. levels), as well as the computed convergence factors $\rho$. As it is clear from the results reported in Table 6, classical algebraic agglomeration procedures are not efficient when applied to the matrices arising from high-order DG approximations; indeed in all the cases the resulting algorithm is not able to reduce the (relative) residual below the given tolerance within 5000 iterations, cf. last column of Table 6 where the iteration counts (${\mathsf {N}_{\mathsf {it}}^{\mathsf {AMG}}}$) are shown. Such behaviour strongly suggests that the geometric information needs to be taken into account in the construction of the solver and/or more sophisticated (aggressive) aggregation-based algebraic algorithms, as well as Schwarz-type smoothers, such as the ones proposed, for example, in [24, 51], should be considered. Such developments are currently under investigation and will be the subject of future research.

Table 5 Iteration counts of the h-version of the two-level and W-cycle solvers as a function of p and the number of levels and corresponding CG/PCG iteration counts ($C_\sigma ^j \equiv C_\sigma =10$, $m=5$)

Table 6 Number of agglomeration levels (N. levels) and computed convergce factors ($\rho$) of Algebraic W-cycle multigrid method (Richardon smoother, $m=5$ pre- and post-smoothing steps) as a function of p

7 Conclusions

We have presented and analyzed two-level and multigrid schemes for the efficient solution of the linear system of equations arising from the hp-version of the interior penalty DG scheme on polygonal/polyhedral meshes. The attractive feature of the proposed algorithms is that the auxiliary sequence of meshes needed by the multilevel solver can be generated by a (successive) general geometric agglomeration procedure starting from an initial grid made of (possibly arbitrarily-shaped) elements. Such an approach fully exploits the flexibilty of DG methods in terms of their ability to handle arbitrarily-shaped elements, including polytopic elements, see [4, 6, 8, 21, 33, 35, 36], and the recent review paper [5]. Extending the theoretical results recently presented in [13] on quasi-uniform meshes, we have proved that, under mild geometric assumptions on the quality of the agglomerates, both the two-level and W-cycle multigrid schemes converge uniformly with respect to the discretization parameters (namely, the granularity of the underlying partition and the polynomial approximation degree p) and, for the multigrid scheme, the number of levels, provided that the number of smoothing steps is chosen sufficiently large. We have also demonstrated through numerical experiments that the theoretical assumption concerning the need to employ a sufficiently large number of smoothing steps is not needed in practice, i.e., our algorithms converge even if the number of smoothing steps is kept fixed independently of the polynomial approximation degree p. However, in this latter case, the performance of the iterative solvers deteriorates, as expected, when increasing p.