Multigrid Algorithms for High Order Discontinuous Galerkin Methods

Abstract

In this paper we study the performance of h- and p-multigrid algorithms for high order Discontinuous Galerkin discretizations of elliptic problems. We test the performance of the multigrid schemes employing a wide class of smoothers and considering both two- and three-dimensional test cases.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In the framework of multigrid solvers for Discontinuous Galerkin (DG) schemes, the first contributions are due to [10, 16]. In [16] a V-cycle preconditioner for a Symmetric Interior Penalty (SIP) discretization of an elliptic problem is analyzed. They prove that the condition number of the preconditioned system is uniformly bounded with respect to the mesh size and the number of levels. In [10] V-cycle, F-cycle and W-cycle multigrid schemes for SIP discretizations are presented and analyzed, employing the additive theory developed in [8, 9]. A uniform bound for the error propagation operator is shown provided the number of smoothing steps is large enough. All the previously cited works focus on low order, i.e., linear, DG approximations. With regard to high order DG discretizations, h- and p-multigrid schemes are successfully employed for the numerical solution of many different kinds of problems, see e.g. [6, 14, 20–22, 24], even if only few theoretical results are available that show the convergence properties of the underlying algorithms. In the context of fast solution techniques for high order DG methods, we mention [1, 11, 12], see also [3] were a substructuring preconditioner is analyzed for an hp domain decomposition method with interior penalty mortaring. Recently, in [2] a convergence analysis of W-cycle h- and p-multigrid algorithms for a wide class of high order DG schemes is provided. More precisely, it is shown that, if a Richardson smoother is employed, the W-cycle algorithms converge uniformly with respect the granularity of the underlying mesh and the number of levels; but the contraction factor of the scheme deteriorates when increasing the polynomial order. As a further development of the results contained in [2], the aim of this paper is to investigate the performance of h- and p-multigrid algorithms for high order DG methods, considering a wide class of smoothers and addressing both two- and three-dimensional test cases. The paper is organized as follows. In Sect. 2 we briefly introduce the model problem and its DG discretization. The h- and p-multigrid methods are described in Sect. 3. The numerical experiments are presented in Sect. 4, where the W-cycle schemes are tested on two- and three-dimensional problems.

2 Model Problem and DG Methods

Given an open, bounded polygonal/polyhedral domain Ω and a given function f ∈ L ²(Ω), we consider the weak formulation of the Poisson problem with homogeneous boundary conditions: find $u \in H_{0}^{1}(\varOmega )$ such that

$$\displaystyle{ (\nabla u,\nabla v)_{\varOmega } = (\,f,v)_{\varOmega }\,\qquad \forall v \in H_{0}^{1}(\varOmega ), }$$

(1)

where (⋅ , ⋅ ) _Ω denotes the standard L ² product. We consider a sequence of discontinuous finite dimensional spaces V _k , k = 1, …, K, defined as

$$\displaystyle{ \begin{array}{rlll} &V _{k} =\{ v \in L^{2}(\varOmega ): v\vert _{E} \in \mathbb{M}^{p_{k}}(T)\quad \forall \,T \in \mathcal{T}_{ k}\}&&k = 1,\ldots,K, \end{array} }$$

where $\mathbb{M}^{p_{k}}$ is a suitable space of polynomials of degree p _k  ≥ 1 and $\mathcal{T}_{k}$ is a partition of Ω with granularity h _k .

The sequence of spaces V _k is generated with two different approaches, depending on whether we are interested in h- or p-multigrid algorithms. In the h-multigrid algorithm, we fix the polynomial approximation degree p _k  = p for all k = 1, …, K, and the spaces V _k are associated to a sequence of nested partitions $\left \{\mathcal{T}_{k}\right \}_{k=1,\ldots,K}$ obtained from successive uniform refinements of an initial (coarse) shape regular and quasi-uniform partition $\mathcal{T}_{1}$, cf. Fig. 1 (left). In p-multigrid schemes, the grid is kept fixed on all the levels and from the level k to the level k − 1 the polynomial degree is lowered down, i.e., $p_{k-1} \leq p_{k}$ for any k = 2, …, K, cf. Fig. 1 (right). Notice that, with such a construction the spaces V _k are nested, i.e., $V _{1} \subseteq V _{2} \subseteq \ldots \subseteq V _{K}$. For the sake of simplicity, we will also suppose that the polynomial degrees p _k satisfy the following local bounded variation among levels: there exists a constant C > 0 such that $p_{k} \leq Cp_{k-1}$, for any k = 2, …, K.

Fig. 1

Sample of the space V _k and V _k−1 in the h- (left) and p- (right) multigrid schemes

For any level k, we denote by $\mathcal{F}_{k}^{I}$ and $\mathcal{F}_{k}^{B}$ the sets of interior and boundary faces of $\mathcal{T}_{k}$, respectively, set $\mathcal{F}_{k} = \mathcal{F}_{k}^{I} \cup \mathcal{F}_{k}^{B}$, and define the lifting operators

$$\displaystyle{ \begin{array}{rlll} (\mathcal{R}_{k}(\boldsymbol{\tau }),\boldsymbol{\eta })_{\varOmega }& = -\sum _{F\in \mathcal{F}_{k}}(\boldsymbol{\tau },\{\boldsymbol{\eta }\})_{F} &&\forall \boldsymbol{\eta }\in [V _{k}]^{d},\quad k = 1,\ldots,K, \\ (\mathcal{L}_{k}(v),\boldsymbol{\eta })_{\varOmega }& = -\sum _{F\in \mathcal{F}_{k}^{I}}(v,[\![\boldsymbol{\eta }]\!])_{F}&&\forall \boldsymbol{\eta }\in [V _{k}]^{d},\quad k = 1,\ldots,K, \end{array} }$$

where the jump and average trace operators are defined as in [5].

We next define the DG bilinear forms $\mathcal{A}_{k}(\cdot,\cdot ): V _{k} \times V _{k} \rightarrow \mathbb{R}$, k = 1, …, K, as

$$\displaystyle\begin{array}{rcl} \mathcal{A}_{k}(w,v)& =& (\nabla w + \mathcal{R}_{k}([\![w]\!]) + \mathcal{L}_{k}(\boldsymbol{\beta }\cdot [\![w]\!]),\nabla v + \mathcal{R}_{k}([\![v]\!]) + \mathcal{L}_{k}(\boldsymbol{\beta }\cdot [\![v]\!]))_{\varOmega } \\ & & \qquad \qquad \qquad -\theta (\mathcal{R}_{k}([\![w]\!]),\mathcal{R}_{k}([\![v]\!]))_{\varOmega } +\sum _{F\in \mathcal{F}_{k}}(\sigma _{k}[\![w]\!],[\![v]\!])_{F} {}\end{array}$$

(2)

where, for a constant α _k  > 0, the stabilization function $\sigma _{k}$ is defined as

$$\displaystyle\begin{array}{rcl} \sigma _{k}\vert _{F} = \frac{\alpha _{k}p_{k}^{2}} {\min \left \{\text{diam}(T^{+}),\text{diam}(T^{-})\right \}}\quad F \in \mathcal{F}_{k}^{I},\sigma _{ k}\vert _{F} = \frac{\alpha _{k}p_{k}^{2}} {\text{diam}(T)}\quad F \in \mathcal{F}_{k}^{B},& & {}\\ \end{array}$$

T ^± being the two neighboring elements sharing the face $F \in \mathcal{F}_{k}^{I}$. For $\theta = 1$ and $\boldsymbol{\beta }= \mathbf{0}$, the bilinear form (3) correspond to the SIP method [4], whereas for $\theta = 1$ and $\boldsymbol{\beta }$ a uniformly bounded (and possibly null) vector in $\mathbb{R}^{d}$ we obtain the LDG bilinear form [13].

We are interested in solving the following problem on the finest level K:

$$\displaystyle{ \begin{array}{rlllll} &\mbox{ find $u_{K} \in V _{K}$ such that}&&\mathcal{A}_{K}(u_{K},v_{K}) = (\,f,v_{K})_{\varOmega }&&\forall v_{K} \in V _{K},\end{array} }$$

(3)

with a W-cycle multigrid method. Fixing a basis for V _K , Eq. (3) is equivalent to the following linear system of equations

$$\displaystyle{ A_{K}u_{K} = F_{K}, }$$

(4)

where A _K and F _K are the matrix representations of the bilinear form $\mathcal{A}_{K}(\cdot,\cdot )$ and of the right hand side in (3), respectively, and where, with a slight abuse of notation, we used to the same symbol to denote both a function in the finite element space V _K and the vector of its expansion coefficients in a given basis.

It can be shown that the bilinear form $\mathcal{A}_{K}(\cdot,\cdot )$ defined in (3) is continuous and coercive with respect to the following (mesh-dependent) DG norm

$$\displaystyle{ \|v\|_{\text{DG},K}^{2} =\sum _{ T\in \mathcal{T}_{K}}\|\nabla v\|_{L^{2}(T)}^{2} +\sum _{ F\in \mathcal{F}_{K}}\|\sigma _{K}^{1/2}[\![v]\!]\|_{ L^{2}(F)}^{2}, }$$

(5)

and that the following error estimates are satisfied, cf. [18, 23, 25] for example.

Theorem 1

Let u be the exact solution of problem (1) such that $u \in H^{s+1}(\mathcal{T}_{K})$ , s ≥ 1, and let $u_{K} \in V _{K}$ be the DG solution of problem (3) . Then,

$$\displaystyle{ \begin{array}{rl} \|u - u_{K}\|_{\text{DG},K}& \lesssim \frac{h_{K}^{\min (p_{K},s)}} {p_{K}^{s-\mu /2}} \|u\|_{H^{s+1}(\mathcal{T}_{K})}, \end{array} }$$

(6)

with μ = 0 whenever a continuous interpolant can be built, cf. [25], or the projector of [15] can be employed and μ = 1 otherwise.

3 W-Cycle h- and p-Multigrid Algorithms

As usual in the multigrid framework, we will employ a recursive algorithm to describe the multigrid scheme. To this aim, we define on each level k the problem

$$\displaystyle{A_{k}z_{k} = b_{k},}$$

where A _k is the matrix representation of the bilinear form (3), and z _k , b _k are vectors of dimension dim(V _k ).

Algorithm 1 $u_{k} = \mathsf{MG}_{\mathcal{W}}(k,b_{k},u_{k}^{(0)},m_{1},m_{2})$

The first ingredient to build a multigrid algorithm are the intergrid transfer operators, which we denoted by $R_{k-1}^{k}$ (prolongation from V _k−1 to V _k ) and by $R_{k}^{k-1}$ (restriction from V _k to V _k−1). Given we are considering nested spaces, we can simply take $R_{k-1}^{k}$ as the classical embedding operator and $R_{k}^{k-1}$ as its adjoint with respect to the L ² scalar product. The second ingredient is a suitable smoother, which we denote by B _k . Denoting by $u_{k}^{(0)} \in V _{k}$ the initial guess, and by m ₁ and m ₂ the number of pre- and post-smoothing steps, respectively, the W-cycle multigrid algorithm $u_{k} = \mathsf{MG}_{\mathcal{W}}(k,b_{k},u_{k}^{(0)},m_{1},m_{2})$ is defined recursively as shown in Algorithm 1. We then employ Algorithm 1 to solve the linear system (4), i.e.,

$$\displaystyle{ u_{K} = \mathsf{MG}_{\mathcal{W}}(K,b_{K},u_{K}^{(0)},m_{ 1},m_{2}). }$$

Notice that if the spaces V _k are associated to a sequence of grids $\mathcal{T}_{k}$ with variable mesh size and the polynomial degree is kept fixed on all the levels we obtain the W-cycle h-multigrid scheme, whereas if the mesh is kept fixed and the polynomial degree is lower down from one level to a coarser one we then have a W-cycle p-multigrid algorithm.

We next introduce the following operator $P_{k}^{k-1}: V _{k} \rightarrow V _{k-1}$

$$\displaystyle{ \begin{array}{rlll} & \mathcal{A}_{k-1}(P_{k}^{k-1}v,w) = \mathcal{A}_{k}(v,R_{k-1}^{k}w)&&\forall v \in V _{k},w \in V _{k-1},\end{array} }$$

and the following discrete norm

$$\displaystyle{ \vert \!\vert \!\vert v\vert \!\vert \!\vert _{1,k}^{2} = (A_{ k}v,v)_{k} = \mathcal{A}_{k}(v,v)\quad \forall v \in V _{k}. }$$

The error propagation operator associated to the W-cycle multigrid scheme is given by

$$\displaystyle{ E_{k,m_{1},m_{2}}v = \left \{\begin{array}{@{}l@{\quad }l@{}} 0 \quad &k = 1, \\ G_{k}^{m_{2}}(\text{I}_{k} - R_{k-1}^{k}(\text{I}_{k} - E_{k-1,m_{ 1},m_{2}}^{2})P_{ k}^{k-1})G_{ k}^{m_{1}}v\qquad \quad &k> 1, \end{array} \right. }$$

where I _k is the identity operator, and $G_{k} = \text{I}_{k} - B_{k}^{-1}A_{k}$, cf. [7, 17]. The following result, which is proved in [2], state that, whenever a Richardson smoother is employed, the W-cycle algorithms converge uniformly with respect to the granularity of the underlying mesh and the number of levels, provided the number of smoothing steps is chosen sufficiently large, but the contraction factor of the scheme deteriorates when increasing the approximation order.

Theorem 2

For any k, let B _k be the Richardson smoother, i.e., $B_{k} =\varLambda _{k}I_{k}$ , where $\varLambda _{k}$ is an upper bound for the maximum eigenvalue of A _k . Then, there exist a constant C _W > 0 and an integer m _W that are independent of the mesh size, but dependent on the polynomial degree, such that

$$\displaystyle{ \vert \!\vert \!\vert E_{k,m_{1},m_{2}}v\vert \!\vert \!\vert _{1,k} \leq C_{\text{W}} \frac{p_{k}^{2+\mu }} {(1 + m_{1})^{1/2}(1 + m_{2})^{1/2}}\vert \!\vert \!\vert v\vert \!\vert \!\vert _{1,k}\quad \forall v \in V _{k},\quad k = 2,\ldots,K, }$$

provided $m_{1} + m_{2} \geq m_{\text{W}} = m_{\text{W}}(p_{k})$ .

4 Numerical Results

In this section we test the performance of the W-cycle h- and p-multigrid schemes in both two- and three-dimensional test cases and with different choices of smoothers. We compute the convergence factor as

$$\displaystyle{ \rho =\exp \left ( \frac{1} {N}\ln \frac{\|\mathbf{r}_{N}\|_{2}} {\|\mathbf{r}_{0}\|_{2}} \right ), }$$

with N denoting the iteration counts needed to achieve convergence up to a relative tolerance of 10⁻⁸ and r _N and r ₀ denoting the final and initial computed residuals, respectively. Throughout the section we have employed an equal number of pre- and post-smoothing steps, i.e., $m_{1} = m_{2} = m$, and we have set the penalty parameter α _k appearing in the definition of the DG bilinear form as α _k  = 10, for any level k = 1, …, K.

We first consider a two-dimensional example with Ω = (0, 1)² and focus on the performance of the h-multigrid algorithm. To this aim, we fix a coarse (triangular/Cartesian) grid $\mathcal{T}_{1}$ with granularity h ₁ = 0. 25 and consider a sequence of nested grids $\mathcal{T}_{k}$, k = 2, …, K, obtained from successive uniform refinements of $\mathcal{T}_{1}$. In Table 1 we report the computed convergence factors as a function of the number of smoothing steps m and the number of levels K, fixing the polynomial degree $p_{k} = p = 1,2$ for all the levels k = 1, …, K. The results reported in Table 1 have been obtained with the SIP method on structured triangular grids and with the LDG scheme on Cartesian grids, and employing a Richardson smoother. The symbol “-” means that the maximum number of 1000 iterations has been reached without achieving the desired tolerance. We have repeated the same set of experiments employing p = 3, 4, and the same behavior as been observed; for brevity these results have been omitted. As expected from Theorem 2, the convergence factor is independent of the number of levels K, decreases when m increases, and the performance of the algorithm deteriorates as p grows up.

Table 1 2D test case, SIP and LDG methods, h-multigrid scheme

We next fix the number of pre- and post-smoothing steps m = 6, and investigate how the performance of the h-multigrid algorithm depends on the polynomial degree, always employing a Richardson smoother. Table 2 shows the computed convergence factors as a function of the polynomial degree p = 1, 2, …, 6 and the number of levels K = 2, 3, 4, for both the SIP and LDG methods. We observe that, as predicted by Theorem 2, the performance of the h-multigrid algorithm are independent of the number of levels but deteriorates as p increases.

Table 2 2D test case, SIP and LDG methods, h-multigrid scheme

We next test the performance of the h-multigrid scheme employing different smoothers as the Gauss-Seidel smoother of [16], an (elementwise) block Gauss-Seidel smoother and the polynomial smoother proposed in [19]. In Table 3 we report the computed convergence factors as a function of the number of pre- and post-smoothing steps m = 2, 4, 10, the number of levels K = 2, 3, 4 and the polynomial approximation degree p = 1, 2, 3, 4. These results have been obtained with the SIP method and employing triangular grids. In all the cases the performance of the h-multigrid algorithm seems to be fairly independent of the number of levels. Moreover, as expected, the convergence factor decreases as the number of smoothing steps increases, but still deteriorates as p grows up (even if the dependence of the convergence factor on p seems to be weaker than for the Richardson smoother). Moreover, all the smoothers outperform the Richardson smoother and the polynomial smoother seems to provide the best convergence factors. The extension of the convergence analysis presented in [2] to h-multigrid algorithms based on these (more effective) smoothers is currently under investigation.

Table 3 2D test case, SIP method (triangular grids), h-multigrid scheme

We next turn our attention to the performance of the p-multigrid scheme. To this aim, we fix the finest computational level K, the mesh $\mathcal{T}_{K}$ and the polynomial approximation degree p _K  ≥ K employed therein. Then, for each level k, we set $p_{k-1} = p_{k} - 1$, $k = K,K - 1,\ldots,2$. In Table 4 we report the computed convergence factors obtained with p _K  = 5 and varying the number of smoothing steps m and the number of levels K. The results reported in Table 4 have been obtained with the LDG and SIP methods and employing a Richardson smoother. Next, we fix the number of smoothing steps m = 6 and vary the polynomial approximation degree p _K employed on the finest level. The results obtained with the SIP method and employing the Richardson smoother are reported in Table 5. From the results reported in Table 4 and in Table 5, we can conclude that the p-multigrid scheme seems to be asymptotically uniform with respect to the number of levels (notice that in this case the ratio $p_{k}/p_{k-1}$ is not constant from one level to the other), and that, as expected, the performance of the algorithm improves as m increases.

Table 4 2D test case, SIP and LDG methods, p-multigrid scheme

Table 5 2D test case, SIP and LDG methods, p-multigrid scheme

We finally address the performance of the p-multigrid method when employing a different smoother. For this set of experiments we have considered the SIP formulation and tested the Gauss-Seidel smoother. The results reported in Table 6 show the computed convergence factors as a function of the number of levels K, the number of smoothing steps m and the polynomial degree p _K employed on the finest level. The computed convergence factor seems to be fairly insensitive to the number of levels employed in the algorithm and it improves as the number of pre- and post-smoothing steps increases (notice that, no restriction on the minimum number of smoothing steps seems to be needed in this case). Nevertheless, the convergence factor still depends on the polynomial degree even if such a dependence seems to be weaker than that observed employing the Richardson smoother (cf. Table 5). Finally, comparing these results with the ones reported in Table 5 it is clear that, as for the h- multigrid algorithm, the Gauss-Seidel smoother outperforms the Richardson smoother.

Table 6 2D test case, SIP method (triangular grid), p-multigrid scheme

We next present some three-dimensional numerical experiments. We have employed an h-multigrid scheme to solve the linear system of equations arising from the SIP discretization of model problem (1) posed on Ω = (0, 1)³. We employ a sequence of tetrahedral meshed obtained by successive uniform refinements of an initial coarse grid with granularity h ₁ = 0. 25. As before, we fix p _k  = p for all the levels k = 1, 2, …, K and consider the Richardson, the Gauss-Seidel and the symmetric Gauss-Seidel smoothers. The computed convergence factors varying the number of levels K, the number of pre-and post-smoothing steps m as well as the polynomial degree p are reported in Table 7. We observe that the performance of the h-multigrid schemes are completely analogous to the one observed in the two-dimensional test case.

Table 7 3D test case, SIP method (tetrahedral grids), h-multigrid scheme