CFL condition in Discontinuous Galerkin schemes

Question

I have implemented an ADER-Discontinuous Galerkin scheme for the resolution of linear systems of conservation laws of the type of $\partial_t U + A \partial_x U + B \partial_y U=0 $ and observed that the CFL condition is very restrictive. In the bibliography, an upper bound for the time step $\Delta t \leq \frac{h}{d(2N+1)\lambda_{max}}$ can be found, where $h$ is the cell size, $d$ is the number of dimensions and $N$ is the max degree of the polynomials.

Is there any way to circumvent this issue? I had been working with WENO-ADER Finite volume schemes and the CFL restrictions were much more relaxed. For instance, for a 5-th order scheme, a CFL lower than 0.04 must be imposed when using DG while CFL=0.4 can still be used in a WENO-ADER FV scheme.

Why using DG schemes rather than ADER-FV, for instance, in computational aeroacustics (linearized Euler equations) or similar applications (gas dynamics, shallow water, magnetohydrodynamics)? Is the overall computational cost of the scheme similar than that of the ADER-FV, in spite of the much lower time step?

Thoughts and suggestions for this are welcome.

Answer 1

The restrictive CFL of DG schemes typically comes from the combination of high order accuracy and a compact stencil (see this reference for example). The CFL depends on bounding the variational form in terms of the $L^2$ norm of the solution, which depends on derivative and traces of polynomials. Bounds for each of these quantities (using Bernstein or Markov brothers inequalities and discrete trace inequalities) give constants which depend inversely on $h$ and quadratically on the order $N$, resulting in an overall CFL of $O(h/N^2)$.

FYI - I've seen the CFL you mention referenced before, but I can't recall where it's proven. I'd like to know how they avoid quadratic dependence on $N$ in their bound.

Finite difference and WENO schemes (as well as B-spline based finite element methods on periodic meshes) have looser CFL conditions because the constants in the analogous bounds grow more slowly in $N$. This is in turn because the stencil size tends to increases with order $N$, which reduces some of these issues.

DG methods are more expensive, but they can deal easily with unstructured meshes and can be implemented efficiently. There are high order versions of WENO (or similar reconstructions) for unstructured grids, though these can introduce additional mathematical or implementational complications.

Answer 2

I would like to provide some references for the CFL bounds discussed in this post.

My starting point are lecture notes [1] by Olindo Zanotti which mention on page 23 (for 1D) both the quadratic \begin{equation} \Delta \overset{!}{\leq} \frac{h}{(N+1)^2} \tag{1} \label{1} \end{equation} as well as the linear bound $$ \Delta t \leq \frac{h}{(2N+1) \vert \lambda_\text{max} \vert }. \tag{2} \label{2} $$

As resources for bound \ref{1}, there are [2] and [3] given.
For bound \ref{2}, the author refers to [4], where it might also be useful to take a look at the related paper [5].

---

[1]: Olindo Zanotti. Laboratory of Applied Mathematics, University of Trento, Italy,. ADER Discontinuous Galerkin schemes. Lecture Notes for the course at the Institute for Theoretical Physics, 3-5 of May 2016, Frankfurt, Germany.
http://www.olindozanotti.net/wp-content/uploads/2015/03/DG-Frankfurt.pdf

[2]: Gottlieb and E. Tadmor. The CFL condition for spectral approximations to hyperbolic initial-boundary value problems. Mathematics of Computation, 56:565–588, April 1991
https://www.ams.org/journals/mcom/1991-56-194/S0025-5718-1991-1066833-9/

[3]: Radice and L. Rezzolla. Discontinuous Galerkin methods for general-relativistic hydrodynamics: Formu- lation and application to spherically symmetric spacetimes. Phys. Rev. D, 84(2):024010, July 2011
https://journals.aps.org/prd/abstract/10.1103/PhysRevD.84.024010

[4]: Krivodonova and R.Qin. An analysis of the spectrum of the discontinuous galerkin method. Applied Numerical Mathematics, 64:1–18, 2013
https://www.sciencedirect.com/science/article/abs/pii/S0168927412001742

[5] Krivodonova, Lilia and Qin, Ruibin. An analysis of the spectrum of the discontinuous Galerkin method II: Nonuniform grids. Applied Numerical Mathematics 71, pp.41-62, 2013, Elsevier.
https://www.sciencedirect.com/science/article/abs/pii/S0168927413000639