10

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.

Adr
  • 173
  • 8

2 Answers2

8

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.

Jesse Chan
  • 3,132
  • 1
  • 13
  • 17
  • 1
    Thank you very much for your detailed answer Jesse, it has provided me a broader view on this issue.

    In my numerical trials with the DG-ADER, I have noticed that when using structured quadrilateral meshes (with arbitrary quadrilateral shape, for instance squares, trapezoids or parallelograms...), the numerical solution is non-oscillatory and convergent to the exact solution, however, when moving to unstructured meshes, oscillations appear, even for quasi structured meshes, created by randomly displacing the nodes of an structured mesh a small distance. Is this an expected behavior?

     – Adr Jan 26 '17 at 20:12
  • 1
    @Adrian -- It's quite common for oscillations to appear once you move away from uniform meshes. Once you use general meshes, it is also not at all clear any more what exactly you mean by the mesh size $h$. It could be the cell diameter, the length of the shortest edge, the square root of the area (in 2d), or any other way of defining a "mesh size". – Wolfgang Bangerth Jan 26 '17 at 21:04
  • Thank you for the clarifications Wolfgang. So far, I was setting $h$ as the length of the shortest edge. But anyway, even reducing the CFL number one order of magnitude or more from the prescribed CFL, given by the formula, it is still oscillatory. – Adr Jan 26 '17 at 22:02
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

Dan Doe
  • 1,083
  • 5
  • 22