Operator Bounds and Time Step Conditions for the DG and Central DG Methods

Abstract

Discontinuous Galerkin (DG) and central DG methods are two related families of finite element methods. They can provide high order spatial discretizations that are often combined with explicit high order time discretizations to solve initial boundary value problems. In this context, it has been observed that the central DG method allows larger time steps, especially for schemes with high accuracy. In this paper, we estimate bounds for the DG and central DG spatial operators for the linear advection equation. Based on these estimates and Kreiss-Wu theory, we obtain time step conditions to ensure the numerical stability of the DG and central DG methods when the methods are combined with locally stable time discretizations. In particular, for a fixed time discretization, the time step allowed for the DG method is proportional to $h/k^2$, while the time step allowed for the central DG method is proportional to $h/k$, where $h$ is the spatial mesh size and $k>0$ is the polynomial degree of the discrete space of the spatial discretization. In addition, the analysis provides new insight into the role of a parameter in the central DG formulation. We verify our results numerically, and we also discuss extensions of our analysis to some related discretizations.

1 Introduction

Since their introduction in 1973 [11], discontinuous Galerkin (DG) methods have undergone extensive development for many applications. This development reflects a variety of attractive properties of the methods. For example, DG methods can be systematically designed to have any order of accuracy. They are natural candidates for adaptive simulations through local approximations or local meshing. Being compact, the methods are highly efficient in parallel computations, such as on many-core CPUs and more recently on GPUs. The methods have provable results in terms of stability, error estimates, and conservation for many linear and nonlinear problems. With their excellent dispersive and dissipative properties, DG methods also perform well in long-term computations, such as in the simulation of wave phenomena.

However, with higher accuracy, DG spatial discretizations coupled with explicit time discretizations can encounter relatively restrictive conditions on the time step size necessary to ensure numerical stability (see [14], or Theorem 11 in Sect. 3.3). This restriction is especially pronounced when the methods are compared with finite difference spatial discretizations with the same designed accuracy, and it is closely related to the spectral properties of the DG spatial operator. Various strategies have been proposed in order to improve this situation. In [14], a co-volume mesh filter was introduced, while in [1], flux modifications were explored. By requiring the DG solution in a cell satisfy additional conservation constraints in adjacent cells, a new DG method was formulated in [13] with an improved time step condition for conservation laws.

Central DG methods, as a family of high order methods closely related to DG methods, are observed to allow larger time steps than DG methods under numerical stability restrictions (except when the schemes are first order accurate) [9, 10]. Such methods involve two copies of the numerical solution defined on overlapping meshes. In this paper, we will show that it is exactly the use of two approximations on two overlapping meshes that reduces the spatial operator norm and therefore the allowable time step restriction when the method is further coupled with a time discretization. Indeed, the co-volume mesh filter strategy in [14] also relies on the use of overlapping meshes. Central DG methods, though less flexible than DG methods, do not need numerical fluxes. They also share many properties of DG methods, such as high order accuracy, flexibility in local approximations, and compactness. Moreover, by exploiting the presence of two numerical solutions, central DG discretizations can provide opportunities to design new methods. One example is the exactly divergence free methods of arbitrary accuracy in MHD simulations [8].

There are various frameworks to study the time step conditions for methods of lines approaches (see [7] and references therein). In this paper, we follow Kreiss and Wu’s analysis [5, 6]. We first establish the operator bounds of DG and central DG spatial discretizations for an advection equation in Sect. 3.2. In particular, we prove that the norm of the DG spatial operator grows at most quadratically with $k$, while the norm of the central DG operator grows at most linearly with $k$. In both cases, $k$ is the polynomial degree of the discrete spaces associated with the spatial operator, and it is related to the accuracy order of the scheme. By applying Kreiss-Wu theory, we obtain time step conditions in Sect. 3.3 that ensure the numerical stability of the fully discrete schemes found by pairing the spatial discretizations with locally stable temporal methods. In addition, our analysis also provides new insight into the role of a parameter, $\tau _{\mathrm {max}}$, in the central DG method (see Sect. 3.4). In Sect. 4, we conduct a set of numerical experiments to verify our theoretical results, to gain better understanding of $\tau _{\mathrm {max}}$, to further examine the values of the constants in the inverse inequalities used in our analysis, to investigate the maximum stable time steps with standard Runge–Kutta time discretizations, and to compare the computational efficiencies of the DG and central DG methods. Finally, in Sect. 5, we discuss the extension of our analysis to a couple of related discretizations.

2 Formulations of DG and Central DG Methods

Consider the one-dimensional linear advection equation,

$$\begin{aligned} u_t+au_x=0, \qquad x\in (0,1), \end{aligned}$$

(1)

where $a>0$, with an initial condition $u(x,0)=u_0(x)$ for $x\in \Omega =[0,1]$ and periodic boundary conditions. The focus of this paper is to study two numerical methods for solving equation (1): the DG and central DG methods [2, 9]. These methods are spatially discrete, and they can be further coupled with temporal discretizations to form fully discrete schemes.

We begin with notation. Let $0=x_{\frac{1}{2}}<x_{\frac{3}{2}}<\cdots < x_{N+\frac{1}{2}}=1$ be a partition of $\Omega$. Setting $x_{j}=\frac{1}{2}(x_{j-\frac{1}{2}}+x_{j+\frac{1}{2}})$, we define $I_j=(x_{j-\frac{1}{2}},x_{j+\frac{1}{2}})$ and $I_{j+\frac{1}{2}}=(x_j,x_{j+1})$ so that $\{I_j\}_j$ and $\{I_{j+\frac{1}{2}}\}_j$ provide two overlapping meshes for $\Omega$. In addition, let $h_j=x_{j+\frac{1}{2}}-x_{j-\frac{1}{2}}$, $h_{\min }=\min _{j=1}^N h_{j}$, and $h=\max _{j=1}^N h_{j}$. Associated with these meshes, we introduce two finite dimensional discrete spaces,

$$\begin{aligned} U_h^k=\{v: v|_{I_j}\in P^k(I_j),\,\forall j\}, \qquad V_h^k=\{v: v|_{I_{j+\frac{1}{2}}}\in P^k(I_{j+\frac{1}{2}}),\,\forall j\}, \end{aligned}$$

where $P^k(I)$ is the set of polynomials of degree less than or equal to $k$ over an interval $I$. Note that functions in $U_h^k$ and $V_h^k$ are possibly discontinuous at mesh points. We denote $v^\pm (x)=\lim _{\epsilon \rightarrow 0^+}v(x\pm \epsilon )$, and define the average $\{\cdot \}$ and jump $[\cdot ]$ as

$$\begin{aligned} \{v\}=\frac{1}{2}\left( v^-+v^+\right) ,\qquad [v]=v^+-v^-\;. \end{aligned}$$

The semi-discrete version of the DG method for (1) is given as follows: find $u_h(\cdot ,t)\in U_h^k$ such that, for any $\varphi \in U_h^k$ and all $j$,

$$\begin{aligned} \int \limits _{I_j}\partial _tu_h\varphi dx = \int \limits _{I_j}au_h\partial _x\varphi dx -a{u_h}_{j+\frac{1}{2}}^-{\varphi }_{j+\frac{1}{2}}^- +a{u_h}_{j-\frac{1}{2}}^-{\varphi }_{j-\frac{1}{2}}^+ , \end{aligned}$$

(2)

where $\hat{f}(u^-,u^+)=au^{-}$ is the upwind numerical flux which is monotone [2] and approximates the flux function $f(u)=au$ at grid points. By summing (2) over $j$, we have

$$\begin{aligned} \int \limits _\Omega \partial _tu_h\varphi dx = \int \limits _\Omega {\mathcal {L}_{dg,k}}(u_h)\varphi dx \end{aligned}$$

(3)

where the spatial operator ${\mathcal {L}_{dg,k}}:U_h^k\rightarrow U_h^k$ of the DG method with the upwind flux satisfies

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{dg,k}}(w)\varphi dx = a\sum _j\left( \int \limits _{I_j} w\partial _x\varphi dx -{w}_{j+\frac{1}{2}}^-{\varphi }_{j+\frac{1}{2}}^- +{w}_{j-\frac{1}{2}}^-{\varphi }_{j-\frac{1}{2}}^+\right) . \end{aligned}$$

(4)

The semi-discrete version of the central DG method, on the other hand, is defined as follows: find $u_h(\cdot ,t)\in U_h^k$ and $v_h(\cdot ,t)\in V_h^k$ such that, for any $\varphi \in U_h^k$, any $\psi \in V_h^k$, and all $j$,

$$\begin{aligned} \int \limits _{I_j}\partial _tu_h\varphi dx&= \frac{1}{\tau _{\mathrm {max}}}\int \limits _{I_j}(v_h-u_h)\varphi dx\nonumber \\&+\int \limits _{I_j}av_h\partial _x\varphi dx -a{v_h}_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +a{v_h}_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+,\end{aligned}$$

(5a)

$$\begin{aligned} \int \limits _{I_{j+\frac{1}{2}}}\partial _tv_h\psi dx&= \frac{1}{\tau _{\mathrm {max}}}\int \limits _{I_{j+\frac{1}{2}}}(u_h-v_h)\psi dx \nonumber \\&+\int \limits _{I_{j+\frac{1}{2}}}au_h\partial _x\psi dx -a{u_h}_{j+1}{\psi }_{j+1}^- +a{u_h}_{j}{\psi }_{j}^+\;, \end{aligned}$$

(5b)

where $\tau _{\mathrm {max}}>0$ is a parameter which is customarily taken as an upper bound of the time step allowed for numerical stability restrictions [9, 10]. We will further examine $\tau _{\mathrm {max}}$ in Sects. 3.4 and 4.4. By summing (5) over $j$, we have

$$\begin{aligned} \int \limits _\Omega \left( \partial _tu_h\varphi + \partial _tv_h\psi \right) dx = \int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}(u_h, v_h)\cdot \left( \begin{array}{c}\varphi \\ \psi \end{array} \right) dx \end{aligned}$$

where

$$\begin{aligned} {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}(w, v)=\left( {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w, v),{\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w, v)\right) ^T: U_h^k\times V_h^k\rightarrow U_h^k\times V_h^k \end{aligned}$$

(6)

denotes the spatial operator of the central DG method, defined as

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w, v)\varphi dx&= \frac{1}{\tau _{\mathrm {max}}}\int \limits _{\Omega }(v-w)\varphi dx \nonumber \\&+a\sum _j\left( \int \limits _{I_j}v \partial _x\varphi dx -{v}_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +{v}_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+ \right) ,\end{aligned}$$

(7a)

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w, v)\psi dx&= \frac{1}{\tau _{\mathrm {max}}}\int \limits _{\Omega }(w-v)\psi dx \nonumber \\&+ a \sum _j\left( \int \limits _{I_{j+\frac{1}{2}}}w\partial _x\psi dx -{w}_{j+1}{\psi }_{j+1}^- +{w}_{j}{\psi }_{j}^+\right) . \end{aligned}$$

(7b)

Unlike the DG method, the central DG method does not require a numerical flux because the two numerical solutions are defined to be piecewise smooth with respect to the two meshes.

3 Main Results: Operator Bounds, Time Step Conditions, and the Parameter $\tau _{\mathrm {max}}$

In this section, we will establish the main results in Theorems 5 and 7 to estimate bounds on the DG and central DG spatial operators for the linear advection equation. Based on these estimates and Kreiss–Wu theory, we will obtain sufficient time step conditions in Theorem 11 for the numerical stability of the DG and central DG spatial discretizations coupled with locally stable time discretizations. In addition, we will examine the parameter $\tau _{\mathrm {max}}$ in the central DG method from the perspective of accuracy and stability.

3.1 Polynomial Inverse Inequalities

We begin with several lemmas providing inverse inequalities for polynomials on a bounded domain. Inequalities of this kind are commonly used in numerical analysis, such as for finite element methods. For the present work, it is important to systematically track, as tightly as possible, the explicit dependence of the estimates on the degree $k$ of the polynomial. In particular, Lemmas 1 and 3 bound the $L^2$ norm of the derivative of a polynomial by the $L^2$ norm of the polynomial itself, and Lemmas 2 and 4 bound the point value of a polynomial by the $L^2$ norm of the polynomial. Lemmas 3 and 4 differ from Lemmas 1 and 2 in that the functions in the upper bounds are defined on relatively larger intervals than the functions being estimated.

In our analysis, we use the Legendre polynomials $\{L_j\}_j$, which are normalized to satisfy $L_j(\pm 1)=(\pm 1)^j$ [12]. Recall that $\{L_j\}_{j=0}^k$ forms an orthogonal basis for $P^k([-1,1])$ with

$$\begin{aligned} {\left\| L_j\right\| }_{L^2([-1,1])}=\sqrt{\frac{2}{2j+1}}, \qquad \forall j\ge 0, \end{aligned}$$

(8)

and

$$\begin{aligned} {\left\| L_j\right\| }_{L^\infty ([-1, 1])}= 1, \qquad \forall j\ge 0. \end{aligned}$$

(9)

Lemma 1

(Markov’s inequality). There exists a positive constant $C_{1}\le \sqrt{3}$ such that

$$\begin{aligned} {\left\| \frac{d^{}p}{dx^{}}\right\| }_{L^2([-1,1])} \le C_{1}k^2{\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

(10)

for any $p\in P^k([-1,1])$ and any nonnegative integer $k$.

Proof

See [14]. $\square$

Lemma 2

There exists a positive constant $C_{2}\le \frac{\sqrt{2}}{2}$ such that

$$\begin{aligned} {\left| {p(x)}\right| }\le C_{2}(k+1){\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

(11)

for any $p\in P^k([-1,1])$, any $x\in [-1,1]$, and any nonnegative integer $k$.

Proof

We can represent any given $p\in P^k([-1,1])$ uniquely as $p(x)=\sum _{j=0}^k\alpha _jL_j(x)$. By applying the Cauchy-Schwarz inequality and the properties of the Legendre polynomials in (8) and (9), we find that

$$\begin{aligned} {\left| {p(x)}\right| }&\le \sum _{j=0}^k{\left| {\alpha _j}\right| }{\left| {L_j(x)}\right| } \le \sum _{j=0}^k{\left| {\alpha _j}\right| }=\sum _{j=0}^k\left( \frac{{\left| {\alpha _j}\right| }}{\sqrt{j+\frac{1}{2}}}\sqrt{j+\frac{1}{2}}\right) \\&\le \left( \sum _{j=0}^k j+\frac{1}{2}\right) ^\frac{1}{2}\left( \sum _{j=0}^k \frac{{\left| {\alpha _j}\right| }^2}{j+\frac{1}{2}} \right) ^\frac{1}{2}\\&= \frac{\sqrt{2}}{2}(k+1) \left( \sum _{j=0}^k {\left| {\alpha _j}\right| }^2 {\left\| L_j\right\| }_{L^2([-1,1])}^2 \right) ^\frac{1}{2}\\&= \frac{\sqrt{2}}{2}(k+1) {\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

for any $x\in [-1,1]$, so the result follows. $\square$

Lemma 3

(Bernstein’s inequality). For any $s\in [0,1)$, there exists a positive constant

$$\begin{aligned} C_{3,s}\le \frac{\sqrt{3}+s}{1-s^2} \end{aligned}$$

such that

$$\begin{aligned} {\left\| \frac{d^{}p}{dx^{}}\right\| }_{L^2([-s,s])} \le C_{3,s}k{\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

(12)

for any $p\in P^k([-1,1])$ and any nonnegative integer $k$.

Proof

See [14]. $\square$

Lemma 4

For any $s\in [0,1)$, there exists a positive constant

$$\begin{aligned} C_{4,s}\le 4\sqrt{\frac{3}{\pi }}(1-s^2)^{-\frac{1}{4}} \end{aligned}$$

such that

$$\begin{aligned} {\left| {p(\pm s)}\right| } \le C_{4,s}\sqrt{k+1}{\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

(13)

for any $p\in P^k([-1,1])$ and any nonnegative integer $k$.

Proof

Our argument is similar to the one used in [14], and it will provide a relatively tighter bound. We can again represent any given $p\in P^k([-1,1])$ uniquely as $p(x)=\sum _{j=0}^k\alpha _jL_j(x)$. Recall the Stieltjes’ bound [12] for the Legendre polynomial $L_j(x)$, given by

$$\begin{aligned} {\left| {L_j(\pm s)}\right| } \le 4\sqrt{\frac{2}{\pi }}\left( 1-s^2\right) ^{-\frac{1}{4}}j^{-\frac{1}{2}}, \quad \forall \; s\in [0, 1), \;\; \forall \; j\ge 1. \end{aligned}$$

Since $j^{-\frac{1}{2}}\le \sqrt{\frac{3}{2}}(j+\frac{1}{2})^{-\frac{1}{2}}$ for any $j\ge 1$, the Stieltjes’ bound can be relaxed to

$$\begin{aligned} {\left| {L_j(\pm s)}\right| } \le 4\sqrt{\frac{3}{\pi }}\left( 1-s^2\right) ^{-\frac{1}{4}}\left( j+\frac{1}{2}\right) ^{-\frac{1}{2}}, \quad \forall \; s\in [0, 1), \;\; \forall \; j\ge 0. \end{aligned}$$

(14)

By applying the bound in (14), the Cauchy-Schwarz inequality, and the properties of Legendre polynomials in (8) and (9), we find that

$$\begin{aligned} {\left| {p(\pm s)}\right| }&\le \sum _{j=0}^k{\left| {\alpha _j}\right| }{\left| {L_j(\pm s)}\right| }\\&\le 4\sqrt{\frac{3}{\pi }}\left( 1-s^2\right) ^{-\frac{1}{4}}\sum _{j=0}^k{\left| {\alpha _j}\right| }\left( j+\frac{1}{2}\right) ^{-\frac{1}{2}}\\&\le 4\sqrt{\frac{3}{\pi }}(1-s^2)^{-\frac{1}{4}}\sqrt{k+1} \left( \sum _{j=0}^k{\left| {\alpha _j}\right| }^2\frac{1}{j+\frac{1}{2}}\right) ^{\frac{1}{2}}\\&= 4\sqrt{\frac{3}{\pi }}(1-s^2)^{-\frac{1}{4}}\sqrt{k+1}{\left\| p\right\| }_{L^2([-1,1])} \end{aligned}$$

for any $s\in [0, 1)$, and this completes the proof. $\square$

The inverse inequalities in Lemmas 1–4 hold for polynomials of arbitrary degree, and the constants $C_1$, $C_2$, $C_{3,s}$, and $C_{4,s}$ in the upper bounds are independent of $k$. The universality of these constants is essential for establishing the theoretical bounds for the DG and central DG spatial operators of arbitrary order. In practice, sharper inverse inequalities can often be derived for each fixed $k$. This will be investigated numerically in Sect. 4.1.

3.2 Estimation of the Operator Bounds

In this section, we will establish bounds for the DG and central DG spatial operators for the linear advection equation (1). To make the presentation of the proofs concise, we will assume the use of uniform meshes. The estimates for general meshes will be given in Remark 8.

Theorem 5

For the DG spatial operator ${\mathcal {L}_{dg,k}}$ defined in (4) with the upwind numerical flux, the following estimate holds:

$$\begin{aligned}&{\left\| {\mathcal {L}_{dg,k}}\right\| } :=\sup _{\begin{array}{c} w,\varphi \in V_h^k\\ w,\varphi \ne 0 \end{array}} \frac{\int _\Omega {\mathcal {L}_{dg,k}}(w) \varphi dx}{{\left\| w\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}}} = \sup _{\begin{array}{c} w\in V_h^k\\ w\ne 0 \end{array}}\frac{{\left\| {\mathcal {L}_{dg,k}}(w)\right\| }_{{L^2(\Omega )}}}{{\left\| w\right\| }_{{L^2(\Omega )}}}\nonumber \\&\le a \left( 2C_{1}\frac{k^2}{h}+4C_{2}^2\frac{(k+1)^2}{h}\right) . \end{aligned}$$

(15)

The constants $C_1$ and $C_2$ are given in Lemmas 1 and 2, and they are positive and independent of $a$, $k$, and $h$.

Proof

Let $w, \varphi \in U_h^k$ be arbitrary. First, by applying the triangle and Cauchy-Schwarz inequalities, we have

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{dg,k}}(w)\varphi dx&\le a \sum _j \left( \int \limits _{I_j}{\left| {w\partial _x\varphi }\right| }dx +{\left| {w_{j+\frac{1}{2}}^-\varphi _{j+\frac{1}{2}}^-}\right| } +{\left| {w_{j-\frac{1}{2}}^-\varphi _{j-\frac{1}{2}}^+}\right| }\right) \\&\le a \sum _j \left( {\left\| w\right\| }_{L^2(I_{j})}{\left\| \partial _x\varphi \right\| }_{L^2(I_{j})} +{\left| {w_{j+\frac{1}{2}}^-}\right| }{\left| {\varphi _{j+\frac{1}{2}}^-}\right| } +{\left| {w_{j-\frac{1}{2}}^-}\right| }{\left| {\varphi _{j-\frac{1}{2}}^+}\right| }\right) . \end{aligned}$$

Then, by using Lemmas 1 and 2 scaled from $[-1,1]$ to $I_j$, we find that

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{dg,k}}(w)\varphi dx&\le a \sum _j \left( 2C_{1}\frac{k^2}{h}{\left\| w\right\| }_{L^2(I_{j})}{\left\| \varphi \right\| }_{L^2(I_{j})} \right. \\&\qquad \qquad \left. +2C_{2}^2\frac{(k+1)^2}{h}\left( {\left\| w\right\| }_{L^2(I_{j})}+{\left\| w\right\| }_{L^2(I_{j-1})}\right) {\left\| \varphi \right\| }_{L^2(I_{j})}\right) . \end{aligned}$$

Finally, by applying the Cauchy–Schwarz inequality again, we see that

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{dg,k}}(w)\varphi dx \le a \left( 2C_{1}\frac{k^2}{h}+4C_{2}^2\frac{(k+1)^2}{h}\right) {\left\| w\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}}. \end{aligned}$$

Therefore, we have

$$\begin{aligned} {\left\| {\mathcal {L}_{dg,k}}(w)\right\| }_{{L^2(\Omega )}} \le a \left( 2C_{1}\frac{k^2}{h}+4C_{2}^2\frac{(k+1)^2}{h}\right) {\left\| w\right\| }_{{L^2(\Omega )}} \end{aligned}$$

and hence the estimate (15). $\square$

Remark 6

An estimate identical to (15) can be found if the upwind numerical flux is replaced by the central numerical flux in the DG formulation. That is, if we define the DG operator by

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{dg,k}}(w)\varphi dx = a\sum _j\left( \int \limits _{I_j} w\partial _x\varphi dx -\{w\}_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +\{w\}_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+\right) \end{aligned}$$

instead of by (4), the same estimate follows. Other numerical fluxes lead to similar estimates as well.

Theorem 7

For the central DG spatial operator ${\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}$ defined in (6) and (7), the following estimate holds:

$$\begin{aligned} {\left\| {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}\right\| }&:= \sup _{\begin{array}{c} w,\varphi \in U_h^k, \;v,\psi \in V_h^k \\ w\;\mathrm or \, v\ne 0,\;\varphi \;\mathrm or \; \psi \ne 0 \end{array}} \frac{\int _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w,v)\varphi dx+\int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w,v)\psi dx}{({\left\| w\right\| }^2_{{L^2(\Omega )}}+{\left\| v\right\| }^2_{{L^2(\Omega )}})^\frac{1}{2}({\left\| \varphi \right\| }^2_{{L^2(\Omega )}}+{\left\| \psi \right\| }^2_{{L^2(\Omega )}})^\frac{1}{2}} \nonumber \\&= \sup _{\begin{array}{c} w \in U_h^k, \;v\in V_h^k\\ w\;\mathrm or \; v\ne 0 \end{array}} \left( \frac{{\left\| {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w,v)\right\| }^2_{{L^2(\Omega )}}+{\left\| {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w,v)\right\| }^2_{{L^2(\Omega )}}}{{\left\| w\right\| }^2_{{L^2(\Omega )}}+{\left\| v\right\| }^2_{{L^2(\Omega )}}}\right) ^{\frac{1}{2}} \nonumber \\&\le \frac{2}{\tau _{\mathrm {max}}}+a\left( 4C_{3,\frac{1}{2}}\frac{k}{h}+4C_{4,\frac{1}{2}}^2\frac{k+1}{h}\right) . \end{aligned}$$

(16)

The constants $C_{3,\frac{1}{2}}$ and $C_{4,\frac{1}{2}}$ are given in Lemmas 3 and 4 with $s=\frac{1}{2}$, and they are positive and independent of $a, k$, and $h$.

Proof

Let $w,\varphi \in U_h^k$ and $v,\psi \in V_h^k$ be arbitrary, and consider the notation for the sub-intervals

$$\begin{aligned} J_j=(x_{j-\frac{1}{4}},x_{j+\frac{1}{4}}) ,\qquad J_{j+\frac{1}{2}}=(x_{j+\frac{1}{4}},x_{j+\frac{3}{4}}), \end{aligned}$$

with $x_{j\pm \frac{1}{4}}=\frac{1}{2}(x_j\pm x_{j-\frac{1}{2}})$. By applying the Cauchy-Schwarz inequality to (7a), we have

$$\begin{aligned}&\int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w, v)\varphi dx \le \frac{1}{\tau _{\mathrm {max}}}{\left\| v-w\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}} \nonumber \\&+ a {\left| {\sum _j\left( \int \limits _{I_j}v \partial _x\varphi dx -{v}_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +{v}_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+\right) }\right| }. \end{aligned}$$

(17)

We can estimate the second term on the right, which is denoted as $\Lambda$, by first integrating by parts over $(x_{j-\frac{1}{2}},x_{j-\frac{1}{4}})$ and $(x_{j+\frac{1}{4}},x_{j+\frac{1}{2}})$ and then recombining the appropriate terms. In doing so, we find that

$$\begin{aligned} \Lambda&:= \sum _j\left( \int \limits _{I_j}v\partial _x\varphi dx -v_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +v_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+\right) \nonumber \\&= \sum _j\left( \int \limits _{x_{j-\frac{1}{2}}}^{x_{j-\frac{1}{4}}} v\partial _x\varphi dx +\int \limits _{x_{j-\frac{1}{4}}}^{x_{j+\frac{1}{4}}} v\partial _x\varphi dx +\int \limits _{x_{j+\frac{1}{4}}}^{x_{j+\frac{1}{2}}} v\partial _x\varphi dx -v_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- +v_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+\right) \nonumber \\&= \sum _j \left( \int \limits _{J_j}v\partial _x\varphi dx-\int \limits _{J_{j+\frac{1}{2}}}\partial _x v \varphi dx -v_{j+\frac{1}{4}}{\varphi }_{j+\frac{1}{4}} +v_{j-\frac{1}{4}}{\varphi }_{j-\frac{1}{4}}\right) . \end{aligned}$$

(18)

By applying the triangle and Cauchy–Schwarz inequalities, we see that

$$\begin{aligned} {\left| {\Lambda }\right| }&\le \sum _j \left( \int \limits _{J_j}{\left| {v\partial _x\varphi }\right| }dx +\int \limits _{J_{j+\frac{1}{2}}}{\left| {\partial _x v\varphi }\right| }dx +{\left| {v_{j+\frac{1}{4}}{\varphi }_{j+\frac{1}{4}}}\right| } +{\left| {v_{j-\frac{1}{4}}{\varphi }_{j-\frac{1}{4}}}\right| }\right) \\&\le \sum _j \left( {\left\| v\right\| }_{L^2(J_{j})}{\left\| \partial _x\varphi \right\| }_{L^2(J_{j})} \!+\!{\left\| \partial _xv\right\| }_{L^2(J_{j\!+\!\frac{1}{2}})}{\left\| \varphi \right\| }_{L^2(J_{j\!+\!\frac{1}{2}})} \!+\!{\left| {\!}\right| }{v_{j\!+\!\frac{1}{4}}}\!{\left| {\!}\right| }{{\varphi }_{j\!+\!\frac{1}{4}}} \!+\!{\left| {\!}\right| }{v_{j\!-\!\frac{1}{4}}}\!{\left| {\!}\right| }{{\varphi }_{j\!-\!\frac{1}{4}}}\right) . \end{aligned}$$

We can now apply the inverse inequalities to the terms with derivative and point values. By first using Lemmas 3 and 4 scaled from $[-1,1]$ to either $I_{j-\frac{1}{2}}$, $I_j$, or $I_{j+\frac{1}{2}}$ and then applying Cauchy–Schwarz inequality again, we find that

$$\begin{aligned} {\left| {\Lambda }\right| }&\le \sum _j \left( 2C_{3,\frac{1}{2}}\frac{k}{h}{\left\| v\right\| }_{L^2(J_{j})}{\left\| \varphi \right\| }_{L^2(I_{j})} +2C_{3,\frac{1}{2}}\frac{k}{h}{\left\| v\right\| }_{L^2(I_{j+\frac{1}{2}})}{\left\| \varphi \right\| }_{L^2(J_{j+\frac{1}{2}})} \right. \nonumber \\&\qquad \qquad \left. +2C_{4,\frac{1}{2}}^2\frac{k+1}{h}{\left\| v\right\| }_{L^2(I_{j+\frac{1}{2}})}{\left\| \varphi \right\| }_{L^2(I_{j})} +2C_{4,\frac{1}{2}}^2\frac{k+1}{h}{\left\| v\right\| }_{L^2(I_{j-\frac{1}{2}})}{\left\| \varphi \right\| }_{L^2(I_{j})} \right) \nonumber \\&\le \left( 4C_{3,\frac{1}{2}}\frac{k}{h}+4C_{4,\frac{1}{2}}^2\frac{k+1}{h}\right) {\left\| v\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}}. \end{aligned}$$

(19)

Now, we can combine (17) and (19), and have

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w, v)\varphi dx&\le \frac{1}{\tau _{\mathrm {max}}}{\left\| v-w\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}} \\&+ a \left( 4C_{3,\frac{1}{2}}\frac{k}{h}+4C_{4,\frac{1}{2}}^2\frac{k+1}{h}\right) {\left\| v\right\| }_{{L^2(\Omega )}}{\left\| \varphi \right\| }_{{L^2(\Omega )}}. \end{aligned}$$

Similarly, by applying the same procedure to (7b), we have

$$\begin{aligned} \int \limits _\Omega {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w, v)\psi dx&\le \frac{1}{\tau _{\mathrm {max}}}{\left\| w-v\right\| }_{{L^2(\Omega )}}{\left\| \psi \right\| }_{{L^2(\Omega )}} \\&+ a \left( 4C_{3,\frac{1}{2}}\frac{k}{h}+4C_{4,\frac{1}{2}}^2\frac{k+1}{h}\right) {\left\| w\right\| }_{{L^2(\Omega )}}{\left\| \psi \right\| }_{{L^2(\Omega )}}. \end{aligned}$$

By combining these two estimates and using the Cauchy-Schwarz inequality once more, we have

$$\begin{aligned}&\int \limits _\Omega \left( {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(1)}}(w, v)\varphi +{\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}},(2)}}(w, v)\psi \right) dx\\&\quad \le \! \left( \frac{2}{\tau _{\mathrm {max}}}\!+\!4aC_{3,\!\frac{1}{2}}\frac{k}{h}\!+\!4aC_{4,\frac{1}{2}}^2\frac{k\!+\!1}{h}\right) \left( {\left\| w\right\| }_{{L^2(\Omega )}}^2\!+\!\!{\left\| v\right\| }_{{L^2(\Omega )}}^2\right) ^\frac{1}{2}\left( {\left\| \varphi \right\| }_{{L^2(\Omega )}}^2\!+\!{\left\| \!\right\| }{\psi }_{{L^2(\Omega )}}^2\right) ^\frac{1}{2}\!. \end{aligned}$$

and hence the estimate in (16). $\square$

Remark 8

The estimates in Theorems 5 and 7 are given for uniform meshes. One can follow the proofs to establish the operator bounds of ${\mathcal {L}_{dg,k}}$ and ${\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}$ when the meshes are more general. These estimates are given below with the details omitted:

$$\begin{aligned} {\left\| {\mathcal {L}_{dg,k}}\right\| }&\le a\left( 2C_{1}\frac{k^2}{h_{\min }}+4C_{2}^2\frac{(k+1)^2}{h_{\min }}\right) ,\end{aligned}$$

(20)

$$\begin{aligned} {\left\| {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}}}\right\| }&\le \frac{2}{\tau _{\mathrm {max}}} + a\left( \left( 2C_{3,\frac{1}{2}}+2C_{3,\star }\right) \frac{k}{h_{\min }}+4C_{4,\frac{1}{2}}C_{4,\star }\frac{k+1}{h_{\min }}\right) . \end{aligned}$$

(21)

Here $C_{3,\star }:=\max _j C_{3,s_{j+\frac{1}{2}}}$, $C_{4,\star }:=\max _j\left( C_{4,s_{j+\frac{1}{2}}},C_{4, 1-s_{j+\frac{1}{2}}}\right)$, where $s_{j+\frac{1}{2}}=\frac{1}{1+\rho _{j+\frac{1}{2}}}$, with the parameter $\rho _{j+\frac{1}{2}}=\frac{\min \left( h_j,h_{j+1}\right) }{\max \left( h_j,h_{j+1}\right) }$ characterizing the local mesh regularity. The estimates in (20) and (21) will reduce to those in Theorems 5 and 7 when the mesh is uniform. In “Appendix 2”, we illustrate that the local mesh regularity does not affect dramatically the upper bound of the central DG spatial operator.

3.3 Implication for Time Steps in the Fully Discrete Schemes

The bounds on the DG and central DG operators in Sect. 3.2 provide provable time step restrictions for numerical stability when these spatial discretizations are combined with a particular class of time discretizations, namely, the locally stable methods.

Definition 9

An ODE solver, either one-step or multi-step, is locally stable if there exists ${\mathcal R}>0$ such that the half circle

$$\begin{aligned} \mathcal {H}=\left\{ z\in \mathbb {C}:{\left| {z}\right| }<{\mathcal R},\,\text {Re}(z)>0\right\} \end{aligned}$$

is included within the region of the absolute stability of the method. The largest such value of ${\mathcal R}$ for an ODE solver is its stability radius.

While the first-order and second-order Runge-Kutta (RK) methods are not locally stable, the standard three-stage, third-order and four-stage, fourth-order RK methods are, with stability radii ${\mathcal R}_3=\sqrt{3}$ and ${\mathcal R}_4=2.615$, respectively. Many higher-order methods are not locally stable, but the fifth-order, seven-stage Dormand–Prince RK method is a notable exception [5].

We first recall a result by Kreiss and Wu and then provide the stable time step restrictions for the DG and central DG methods.

Theorem 10

Consider a well-posed initial boundary value problem. Let the problem be semi-discretized by a stable scheme with a spatial operator $\mathcal {L}$ such that

$$\begin{aligned} U_t=\mathcal {L}(U), \end{aligned}$$

and let the resulting semi-discrete scheme be fully-discretized by a locally stable scheme with stability radius ${\mathcal R}$. If the time step $\Delta t$ satisfies

$$\begin{aligned} {\left\| \Delta t\mathcal {L}\right\| }<{\mathcal R}, \end{aligned}$$

then the fully-discrete scheme is stable.

Proof

See [6]. $\square$

Theorem 11

When the DG spatial discretization given in (4) with polynomial degree $k$ is combined with a locally stable time discretization with stability radius ${\mathcal R}$, the overall method is stable if the time step $\Delta t$ satisfies

$$\begin{aligned} a\frac{\Delta t}{h} < \frac{{\mathcal R}}{2C_{1}k^2+4C_{2}^2(k+1)^2}\;. \end{aligned}$$

(22)

Similarly, when the central DG spatial discretization given in (6) and (7) with polynomial degree $k$ is combined with a locally stable time discretization with stability radius ${\mathcal R}$, the overall method is stable if the time step $\Delta t$ satisfies

$$\begin{aligned} a\frac{\Delta t}{h} < \frac{{\mathcal R}}{2h\left( a\tau _{\mathrm {max}}\right) ^{-1}+\left( 4C_{3,\frac{1}{2}} k +4C_{4,\frac{1}{2}}^2 (k+1)\right) }\; . \end{aligned}$$

(23)

Proof

The results follow immediately from Theorems 5, 7, and 10 and the $L^2$ stability of the semi-discrete versions of the DG and central DG methods [2, 10]. $\square$

Remark 12

For the linear advection equation (1) with a general constant $a\in {\mathbb R}$, estimates similar as (22) and (23) can be obtained, with $a$ being replaced by ${\left| {a}\right| }$. In addition, one can combine the operator bounds in Remark 8 to obtain sufficient conditions for the stable time step size on general meshes.

When we combine a DG or central DG spatial discretization with a given locally stable time discretization, Theorem 11 shows that the DG method admits time steps of $O(\frac{h}{k^2}$) while the central DG method (with $\tau _{\mathrm {max}}=\infty$) admits time steps of $O(\frac{h}{k})$, where $k$ is the polynomial degree of the spatial discretization. This result implies that central DG methods allow larger time steps due to numerical stability consideration for schemes especially with high spatial accuracy. In practice, non-locally stable time discretizations are often paired with DG and central DG methods, and while our analytical results do not address these schemes, we will investigate them numerically in Sect. 4.3.

The bounds on $\Delta t$ obtained in Theorem 11 provide sufficient conditions for the numerical stability of the fully discrete methods. Naturally, they are no larger than the necessary conditions obtained from von Neumann analysis. We present some sufficient and necessary bounds in Tables 1 and 2, where DG discretizations in space with the polynomial degree $k$ are coupled with the third-order and fourth-order RK methods in time. In particular, the bounds for $a\frac{\Delta t}{h}$ in Table 1 are based on Theorem 11 and the later results of Table 3, while those in Table 2 are taken from [3].

Table 1 Bound for $a\frac{\Delta t}{h}$ based on (22) in Theorem 11 for DG spatial discretizations with polynomial degree $k$ coupled with the $\nu$-th order RK method

Table 2 Bound for $a\frac{\Delta t}{h}$ based on von Neumann analysis [3] for DG spatial discretizations with polynomial degree $k$ coupled with the $\nu$-th order RK method

Table 3 Constants in the inverse inequalities (10)–(13) derived by solving eigenvalue problems for each given $k$

3.4 The Parameter $\tau _{\mathrm {max}}$ in the Central DG Methods

When central DG methods were introduced [9], they were first given in a fully discrete formulation from which the semi-discrete schemes were proposed. This is different from the standard procedure to derive method of lines approaches for initial boundary value problems. The derivation of central DG methods particularly suggests that the parameter $\tau _{\mathrm {max}}$ is an upper bound of the time step allowed for the stability. Related to this, when the error estimate was established in [10] for the semi-discrete central DG methods, an assumption, $\tau _{\mathrm {max}}=O(h)$, was made. On the other hand, by itself, the semi-discrete central DG method is less suggestive, leading to an understanding of $\tau _{\mathrm {max}}$ simply as a parameter in $(0,\infty ]$ whose choice should be governed by the stability and accuracy of the overall scheme. With the result in Theorem 11, we can gain additional insight into the role and choice of $\tau _{\mathrm {max}}$.

At first glance, it might seem that $\tau _{\mathrm {max}}=\infty$ would be a good choice as the resulting scheme will become parameter free, and the theoretically estimated upper bound for the time step in (23) can also be larger. However, when $\tau _{\mathrm {max}}=\infty$ and $k$ is odd, we numerically observe $k$th order spatial accuracy for the central DG method. In comparison, when $\tau _{\mathrm {max}}=O(h)$, an optimal $(k+1)$th order spatial accuracy is observed for all $k$. Motivated by this, and also to balance the stability, accuracy, and computational efficiency of the overall methods, we require that the terms in the central DG operator in (7) make comparable contributions to the operator bound in Theorem 7, hence the time step restriction in Theorem 11. More succinctly, we require that

$$\begin{aligned} \frac{2}{\tau _{\mathrm {max}}}\sim a\left( 4C_{3,\frac{1}{2}}\frac{k}{h}+4C_{4,\frac{1}{2}}^2\frac{k+1}{h}\right) . \end{aligned}$$

(24)

From (24), we see that $\tau _{\mathrm {max}}=O(\frac{h}{k})$, which confirms the previous assumption in [10] that $\tau _{\mathrm {max}}=O(h)$ for a fixed $k$. We consider a particular choice of $\tau _{\mathrm {max}}$, denoted as $\tau _{\mathrm {max}}^*$ and defined below,

$$\begin{aligned} \tau _{\mathrm {max}}^* :=\frac{h}{2a(C_{3,\frac{1}{2}} k+ C_{4,\frac{1}{2}}^2 (k+1))}. \end{aligned}$$

(25)

With this choice, the two terms on both sides of (24) are equal. Note that in general ${\Vert {\mathcal {L}_{cdg,k}^{\tau _{\mathrm {max}}^*}}\Vert }\le 2{\Vert {\mathcal {L}_{cdg,k}^{\infty }}\Vert }$, and the strict inequality often holds due to cancelation because all the terms in central DG spatial operator contribute collectively to the operator bound. In Sect. 4.4, we will further examine the parameter $\tau _{\mathrm {max}}$ numerically.

4 Numerical Results

In this section, we will present a set of numerical experiments to verify the theoretical results in Sect. 3, to examine the estimates in Sects. 3.1 and 3.2 in closer detail, to report the maximum time step allowed for stability when standard Runge–Kutta time discretizations are used, to investigate the effect of $\tau _{\mathrm {max}}$ on the actual performance of the central DG method, and to compare the computational efficiencies of the DG and central DG methods. Uniform meshes are considered when needed.

4.1 The Constants in the Polynomial Inverse Inequalities (10)–(13)

Each of the inverse inequalities in Sect. 3.1 holds for all $k$, with generic constants such as $C_1, C_2, C_{3,s}$, and $C_{4,s}$ in the upper bound independent of $k$. Such results are crucial for systematically establishing bounds for DG and central DG spatial operators of arbitrary order of accuracy. They are also important for revealing the essential difference in the dependence of these bounds on the polynomial degree $k$, namely, the quadratic dependence for the DG operator and the linear dependence for the central DG operator.

On the other hand, the estimates in Lemmas 1–4 are not necessarily sharp for each individual polynomial degree $k$. For example, when $k=0$ and $s=\frac{1}{2}$, the right-hand side of (13) is almost six times as large as the left-hand side. This lack of sharpness follows from the use of (14), which provides the desired dependence on $k$ at the expense of a larger bound. To illustrate the lack of sharpness, we compute the constants in each of the inequalities (10)–(13) for any given $k$, and the results are reported in Table 3. These constants are denoted in the form of $\tilde{C}$ with the appropriate subscripts, and each can be obtained to any desired accuracy by finding the largest eigenvalue of a $(k+1)\times (k+1)$ symmetric positive semi-definite matrix, as illustrated in “Appendix 1”.

In Table 3, $\tilde{C}_{2,k}$ is for the estimate as in (11) with $x=\pm 1$, while $\tilde{C}_{3,\frac{1}{2},k}$ and $\tilde{C}_{4,\frac{1}{2},k}$ are for the estimates as in (12)–(13) with $s=\frac{1}{2}$. In Table 4, we give the analytical values of $C_1$, $C_2$, $C_{3,\frac{1}{2}}$, and $C_{4,\frac{1}{2}}$ obtained in the lemmas from Sect. 3.1 which work for all $k$. On one hand, $C_1$ and $C_2$ are sharp, namely, $C_1=\max _k\tilde{C}_{1,k}$ and $C_2=\max _k\tilde{C}_{2,k}$, so they cannot be improved further. Indeed, $\tilde{C}_{2,k}$ is independent of $k$. On the other hand, $C_{3,\frac{1}{2}}$ and $C_{4,\frac{1}{2}}$ are considerably larger than $\tilde{C}_{3,\frac{1}{2},k}$ and $\tilde{C}_{4,\frac{1}{2},k}$, respectively. In particular, since $C_{4,\frac{1}{2}}$ appears in Theorems 7 and 11 as the coefficient $C_{4,\frac{1}{2}}^2$, using $\tilde{C}_{4,\frac{1}{2},k}$ instead of $C_{4,\frac{1}{2}}$ substantially improves the estimate of the stable time step for the central DG methods.

Table 4 Constants in inverse inequalities (10)–(13) derived analytically for all $k$

4.2 Comparison of the Bounds for the DG and Central DG Operators

In this subsection, we will numerically demonstrate the bounds of the DG and central DG operators. For each operator, we report three bounds labeled as Case I, Case II, and Case III. The bound in Case I is the result of Theorems 5 and 7 with the constants found analytically in Lemmas 1–4 and listed in Table 4. The bound in Case II is the result of Theorems 5 and 7 instead with the constants found from solutions of the appropriate eigenvalue problems described in “Appendix 1” and listed in Table 3. The bound in Case III is the result of the implementation of the spatial discretization. More specifically, with the choice of a local Legendre basis for the finite element spaces, the semi-discrete versions of both the DG and central DG methods lead to a problem of the form $W_t=AW$, where $W$ is the coefficient vector in the expansion of the numerical solution with respect to the basis functions. The $L^2$ norm of the spatial operator is the same as the 2-norm of $A$, or, equivalently, the largest singular value of $A$.

In Fig. 1, we plot the upper bounds for ${\mathcal {L}_{dg,k}}$ scaled by $\frac{k^2}{h}$, with $k>0$. Cases I and II show the quadratic dependence of the DG operator bound on $k$, and Case III confirms the quadratic dependence. Asymptotically, the bound of DG operator in Case I is roughly five to six times as large as the one in Case III, while the bound in Case II is roughly twice as large as the actual value in Case III. Similarly, in Fig. 2, we plot the upper bounds for ${\mathcal {L}_{cdg,k}^{\infty }}$ scaled by $\frac{k}{h}$, with $k>0$. The theoretically predicted results in Cases I and II, which show the linear dependence of the central DG operator bound on the polynomial degree $k$, are also conformed algebraically in Case III. Asymptotically, the bound in Case I is nearly fifty times the one in Case III, while a much better bound is provided in Case II which is roughly two-and-a-half times the actual value in Case III.

Fig. 1

The upper bound of ${\Vert {\mathcal {L}_{dg,k}}\Vert }$, scaled by $\frac{k^2}{h}$, as a function of $k$ with $k>0$

Fig. 2

The upper bound of ${\Vert {\mathcal {L}_{cdg,k}^{\infty }}\Vert }$, scaled by $\frac{k}{h}$, as a function of $k$ with $k>0$

Finally, we want to compare the bounds of the DG and central DG operators. In Fig. 3, we plot the polynomial degree $k$ versus ${\Vert {\mathcal {L}_{dg,k}}\Vert }/{\Vert {\mathcal {L}_{cdg,k}^{\infty }}\Vert }$ using the bounds described in Cases I, II, and III. One can see that the comparison based on Case I depicts the DG bound as considerably smaller, with the quadratic growth in the DG bound exceeding the linear growth in the central DG bound only for $k\ge 15$. Cases II and III, on the other hand, provide a more reliable comparison, with the DG bound exceeding the central DG bound for all $k$. This comparison, combined with the time step conditions in Theorem 11, provides some indication about when central DG methods can allow larger time steps than DG methods.

Fig. 3

The ratio of the operator bounds ${\Vert {\mathcal {L}_{dg,k}}\Vert }/{\Vert {\mathcal {L}_{cdg,k}^{\infty }}\Vert }$ as a function of $k$

4.3 Time Step Conditions with Standard Runge–Kutta Time Discretizations

In practice, DG and central DG spatial discretizations are often combined with the standard Runge–Kutta time discretizations. These time discretizations may not always be locally stable. In this subsection, we want to investigate numerically the largest time steps allowed for these fully discrete schemes to complement our theoretical analysis for the time step restriction, which, as we recall, requires locally stable time discretizations.

More specifically, we consider the DG and central DG spatial discretizations with the polynomial degree $k$ combined with the $(k+1)$-stage, $(k+1)$th order Runge–Kutta time discretizations [4]. For the central DG method, we consider both $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$ and $\tau _{\mathrm {max}}=\infty$. These schemes are applied to the linear advection equation (1) with $a=1$ and $u_0(x)=\frac{1}{2}+\sin (2\pi x)$. Each scheme is implemented on uniform mesh with mesh size $h=\frac{1}{40}$, and we record the largest $\Delta t$, denoted as $\Delta t_{\max {}}$, for which the fully discrete schemes exhibit stability up to the final time $T=100$, namely, ${\left\| u_h(\cdot \,,T)\right\| }_{L^2([0,1])}\le {\left\| u_h(\cdot \,,0)\right\| }_{L^2([0,1])}$ in the case of DG methods, and ${\left\| u_h(\cdot \,,T)\right\| }^2_{L^2([0,1])}+{\left\| v_h(\cdot \,,T)\right\| }^2_{L^2([0,1])}\le {\left\| u_h(\cdot \,,0)\right\| }^2_{L^2([0,1])}+{\left\| v_h(\cdot \,,0)\right\| }^2_{L^2([0,1])}$ in central DG methods. The CFL number is defined as $\frac{\Delta t_{\max {}}}{h}$.

In Fig. 4, we plot the computed CFL number for each method. The results for the DG method, given by (a), agree well with the widely known formula for the CFL number [3], $c_1(k)=\frac{1}{2k+1}$, which is given by (d). The results for the central DG method, given by (b) for $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$ and (c) for $\tau _{\mathrm {max}}=\infty$, have less clear trends. To better understand the results, we further perform a least-squares data-fitting to fit the data set (b) with a function of the form $\frac{1}{\alpha k+\beta }$, finding $c_2(k)=\frac{1}{0.606k+3.511}$ represented by (e) when fitting the data with $k=1,\ldots ,16$, and $c_3(k)=\frac{1}{0.339k+6.070}$ represented by (f) when fitting the data with $k=9,\ldots ,16$. In Fig. 5, we show the ratio of the CFL numbers of the DG method in (a) and the central DG method in (b) with $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$, which confirms again that larger time steps are often allowed for central DG methods even when both the DG and central DG methods are combined with the same standard time discretizations which may not be locally stable.

Fig. 4

The computed CFL number as a function of $k$ for both the DG and central DG methods

Fig. 5

The ratio of the CFL numbers for the DG and central DG methods, as a function of $k$; $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$

4.4 The Parameter $\tau _{\mathrm {max}}$, and the Computational Efficiencies of the DG and Central DG Methods

In this subsection, we want to investigate the effect of the parameter $\tau _{\mathrm {max}}$ on the performance of the central DG methods. We also compare the computational efficiencies of the DG and central DG methods.

Recall that, in Sect. 3.3, we introduce $\tau _{\mathrm {max}}^*$ as the choice of $\tau _{\mathrm {max}}$ for which the two parts of the central DG operators (7) have the same operator bounds. On the other hand, as two extreme cases, when $\tau _{\mathrm {max}}$ approaches $0$, central DG methods become inconsistent to the governing equation; when $\tau _{\mathrm {max}}$ approaches $\infty$, we observe sub-optimal convergence order for the central DG methods with the odd polynomial degree $k$.

We again consider the linear advection equation (1) with $a=1$ and $u_0(x)=\frac{1}{2}+\sin (2\pi x)$. We implement central DG methods, up to time $T=1$, on a sequence of meshes with $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$, where $\lambda$ takes a wide range of values. The $L^2$ errors of numerical solutions are plotted as a function of $\lambda$ on each given mesh in Fig. 6 for $k=2$ and in Fig. 7 for $k=3$. The time discretizations are the third-order and fourth-order RK methods, respectively. One can see that, when $k=2$, the numerical errors are not very sensitive to the choice of $\tau _{\mathrm {max}}$, as long as $\tau _{\mathrm {max}}$ is not too small. When $k=3$, if $\tau _{\mathrm {max}}$ is too large, the errors increase. On each fixed mesh, $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$ almost provides the smallest error and therefore nearly the best result in terms of accuracy.

Fig. 6

$L^2$ error in the central DG method for $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$. Here, the polynomial degree $k=2$, and each curve corresponds to a different mesh size $h$

Fig. 7

$L^2$ error in the central DG method for $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$. Here, the polynomial degree $k=3$, and each curve corresponds to a different mesh size $h$

In Figs. 8 and 9, we further plot the $L^2$ errors versus RK CPU run time for $k=2$ and $k=3$, respectively. The time discretizations are again the third-order and fourth-order RK methods, respectively. For both, the code was implemented in Fortran 95 using double-precision arithmetic, compiled on gfortran, and tested on a computer running Ubuntu 13.04 on an Intel Xeon E5607 processor with a clock speed of 2.27 GHZ. Only one of the processor cores was used for the computation, so naturally the CPU times would be less for the parallel implementations to which both DG and central DG methods are amenable. Overall, central DG methods with $\tau _{\mathrm {max}}=\tau _{\mathrm {max}}^*$ perform very well in terms of accuracy and efficiency: when $\tau _{\mathrm {max}}$ is too small, the scheme becomes inconsistent and excessively expensive in terms of computational costs, and when $\tau _{\mathrm {max}}$ is too large, the scheme loses accuracy for odd $k$.

Fig. 8

$L^2$ error versus RK CPU run time with different choices of $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$ in the central DG method. Here, the polynomial degree $k=2$, and each curve corresponds to a different choice of $\lambda$

Fig. 9

$L^2$ error versus RK CPU run time with different choices of $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$ in the central DG method. Here, the polynomial degree $k=3$, and each curve corresponds to a different choice of $\lambda$

Finally we want to compare the computational efficiencies of the DG and central DG methods. In Fig. 10, we present the $L^2$ errors versus RK CPU run time of the methods to solve the same problem described above. Here, the DG and central DG spatial discretizations with the polynomial degree $k$ are combined with $(k+1)$th order RK methods, and each curve in Fig. 10 follows the lower right to the upper left with increasing $k$ from $k=1$ to $k=16$. We observe that the DG method provides the smaller errors compared with the central DG methods with the same $k$, yet the larger time steps of the central DG scheme provide lower computational costs than the DG method for comparable errors when $\tau _{\mathrm {max}}$ takes a relatively larger value. In particular, the central DG scheme outperforms the DG scheme for $k\ge 6$ when $\lambda =\infty$ and $k\ge 7$ when $\lambda =10$ and $\lambda =100$, where $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$. We want to point out that to implement the central DG method with $\lambda =\infty$, the terms containing $\tau _{\mathrm {max}}$ in the scheme are not included, and this will lower the computational cost. The reduction of the accuracy order of central DG methods with odd $k$ and larger $\tau _{\mathrm {max}}$ causes uneven performance. For the example reported here, $\lambda =10$ seems to provide a good balance of accuracy and computational cost.

Fig. 10

$L^2$ error versus RK CPU run time of the DG and central DG methods with $\tau _{\mathrm {max}}=\lambda \tau _{\mathrm {max}}^*$. Here, the polynomial degree $k=1,\ldots ,16$, and each curve follows the lower right to the upper left with increasing $k$

5 Extension

Our analysis of the operator bounds and stable time step conditions in Sect. 3 can be extended in a natural way to analyze DG and central DG discretizations of one-dimensional linear hyperbolic systems and multi-dimensional scalar and systems of hyperbolic equations. In the multi-dimensional cases, we can use discrete spaces with tensor structures, also called Q-type elements, on Cartesian meshes. When the meshes and finite element approximations are more general, however, inverse inequalities associated with these meshes and approximations would need to be established to parallel those in Sect. 3.1.

As illustration, we review and examine two DG methods for solving a one-dimensional wave equation, $w_{tt}=w_{xx}$, with initial conditions $w(x,0)=w_0(x)$ and $w_t(x,0)=w_1(x)$ and periodic boundary conditions on the domain $\Omega =[0,1]$. The numerical methods start with the first-order form of the problem,

$$\begin{aligned} u_t-v_x=0,\qquad v_t-u_x=0, \end{aligned}$$

(26)

by letting $u=w_t$ and $v=w_x$. Accordingly, the initial conditions become $u(x,0)=w_1(x)$ and $v(x,0)=w_0'(x)$, and the boundary conditions remain periodic. We apply the notation from Sect. 2 for the meshes and discrete spaces.

DG Method on One Mesh. Following the standard formulation of DG methods for hyperbolic systems, we approximate the solutions to (26) in the following way: look for $u_h(\cdot ,t), v_h(\cdot ,t)\in U_h^k$ such that, for any $\varphi , \psi \in U_h^k$ and all $j$,

$$\begin{aligned} \int \limits _{I_j}\partial _tu_h\varphi dx&= -\int \limits _{I_j}v_h\partial _x\varphi dx +\widehat{v}_{h\;j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- -\widehat{v}_{h\;j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+,\end{aligned}$$

(27a)

$$\begin{aligned} \int \limits _{I_j}\partial _tv_h\psi dx&= -\int \limits _{I_j}u_h\partial _x\psi dx +\widehat{u}_{h\;j+\frac{1}{2}}{\psi }_{j+\frac{1}{2}}^- -\widehat{u}_{h\;j-\frac{1}{2}}{\psi }_{j-\frac{1}{2}}^+, \end{aligned}$$

(27b)

where

$$\begin{aligned} {\widehat{v}}_h=\{{v_h}\}+\alpha [{v_h}]+\beta [u_h], \qquad \widehat{u}_h=\{{u_h}\}-\alpha [{u_h}]+\beta [v_h]. \end{aligned}$$

When $\alpha =\beta =0$, we have the central flux; when $\alpha =\pm \frac{1}{2}$, $\beta =0$, we have alternating fluxes. Also, when $\alpha =0$, $\beta =\frac{1}{2}$, we recover the upwind flux.

DG Method on Staggered Mesh. By approximating $u$ and $v$ with functions in $U_h^k$ and $V_h^k$, respectively, another scheme can be defined: look for $u_h(\cdot ,t)\in U_h^k$ and $v_h(\cdot ,t)\in V_h^k$ such that, for any $\varphi \in U_h^k$ and $\psi \in V_h^k$ and all $j$,

$$\begin{aligned} \int \limits _{I_j}\partial _tu_h\varphi dx&= -\int \limits _{I_j}v_h\partial _x\varphi dx +{v_h}_{j+\frac{1}{2}}{\varphi }_{j+\frac{1}{2}}^- -{v_h}_{j-\frac{1}{2}}{\varphi }_{j-\frac{1}{2}}^+,\end{aligned}$$

(28a)

$$\begin{aligned} \int \limits _{I_{j+\frac{1}{2}}}\partial _tv_h\psi dx&= -\int \limits _{I_{j+\frac{1}{2}}}u_h\partial _x\psi dx +{u_h}_{j+1}{\psi }_{j+1}^- -{u_h}_{j}{\psi }_{j}^+. \end{aligned}$$

(28b)

Since $u_h$ and $v_h$ are piecewise smooth with respect to different meshes, there is no need for numerical fluxes.

Following a similar analysis as that in Sect. 3.2, one can easily see that the bound of the operator in the first method of (27) depends quadratically on $k$, while the one in the second method of (28) depends linearly on $k$.

Appendices

Appendix 1

In this “Appendix”, we illustrate how to find $\tilde{C}_{1,k}$ for use in (10) as described in Sect. 4.1. More specifically, for any $k\ge 0$, we want to find $\tilde{C}_{1,k}$ such that

$$\begin{aligned} {\Vert p'\Vert }_{L^2([-1,1])}\le \tilde{C}_{1,k}k^2{\Vert p\Vert }_{L^2([-1,1])} \end{aligned}$$

for any $p\in P^k([-1,1])$. By inspection, we see that $\tilde{C}_{1,0}=0$, so we consider $k\ge 1$. We can represent any $p\in P^k([-1,1])$ uniquely as $p(x)=\sum _{j=0}^k\alpha _j\tilde{L}_j(x),$ where $\{\tilde{L}_j(x)\}_{j=0}^k$ are the Legendre polynomials normalized so that ${\Vert \tilde{L}_j\Vert }_{L^2([-1,1])}=1$. We let $\alpha =(\alpha _j)\in {\mathbb R}^{k+1}$ denote the coefficient vector, and we let $A_k=\left( a_{ij}\right) \in {\mathbb R}^{(k+1)\times (k+1)}$, where

$$\begin{aligned} a_{ij}=\int \limits _{-1}^1\frac{d^{}\tilde{L}_{i-1}}{dx^{}}\frac{d^{}\tilde{L}_{j-1}}{dx^{}}dx, \qquad i, j=1, \ldots , k+1. \end{aligned}$$

We note that $A_k$ is a symmetric positive semi-definite matrix, and, in addition, that

$$\begin{aligned} {\Vert p'\Vert }^2_{L^2([-1,1])}={\alpha }^T{A_k}{\alpha } , \qquad {\Vert p\Vert }^2_{L^2([-1,1])}={\alpha }^T{\alpha }. \end{aligned}$$

Accordingly, we see that

$$\begin{aligned} (\tilde{C}_{1,k}k^2)^2 =\max _{\begin{array}{c} p\in P^k([-1,1])\\ p\ne 0 \end{array}} \frac{{\Vert p'\Vert }^2_{L^2([-1,1])}}{{\Vert p\Vert }^2_{L^2([-1,1])}} =\max _{\begin{array}{c} \alpha \in {\mathbb R}^{k+1}\\ \alpha \ne 0 \end{array}} \frac{{\alpha }^T{A_k}{\alpha }}{{\alpha }^T{\alpha }} =\lambda _{\mathrm {max}}(A_k), \end{aligned}$$

where $\lambda _{\mathrm {max}}(A_k)\ge 0$ is the largest eigenvalue of $A_k$, so we have

$$\begin{aligned} \tilde{C}_{1,k}=\frac{\sqrt{\lambda _{\mathrm {max}}(A_k)}}{k^2}. \end{aligned}$$

The process of finding $\tilde{C}_{2,k}$, $\tilde{C}_{3,s,k}$, and $\tilde{C}_{4,s,k}$ for use in (11), (12), and (13), respectively, is similar.

Table 5 Values of $\Xi (k;\sigma )$, where $C_{3,s}$ and $C_{4,s}$ are replaced by $\tilde{C}_{3,s,k}$ and $\tilde{C}_{4,s,k}$, respectively, as described in Sect. 4.1 and “Appendix 1”

Appendix 2

To illustrate how the local mesh regularly will affect the estimate in (21) for the central DG spatial operator on general meshes, we consider a quasi-uniform mesh with

$$\begin{aligned} x_{j+\frac{1}{2}} = \left( (1+\sigma )j+\frac{1-(-1)^j}{2}(1-\sigma )\right) \frac{h}{2} \end{aligned}$$

for any $j$, and $\sigma \in (0,1]$. For such mesh, $\rho _{j+\frac{1}{2}}=\sigma$ for all $j$, and $\sigma =1$ corresponds to a uniform mesh. In Table 5, we report the value of

$$\begin{aligned} \Xi (k;\sigma ) :=\left( 2C_{3,\frac{1}{2}}+2C_{3,\star }\right) k+4C_{4,\frac{1}{2}}C_{4,\star }(k+1), \end{aligned}$$

(29)

for different $\sigma$ and $k$, where the constants $C_{3, s}$ and $C_{4,s}$ are replaced by $\tilde{C}_{3, s, k}$ and $\tilde{C}_{4, s, k}$ as described in Sect. 4.1 and “Appendix 1”. From the results, one can see that the value of $\Xi (k;\sigma )$ is not affected dramatically by the local mesh regularity.