4
$\begingroup$

Time-explicit high order finite element/DG methods for the advection equation tend to have a timestep restriction which looks like $$dt < C h/p^2$$ where $h$ is mesh spacing and $p$ is polynomial degree. I'm having trouble finding a similar order-dependent restriction for high order finite difference stencils. Is there one known, or does it depend more on the specific stencil used instead of the order of the stencil?

Edit: Given Kirill's answer, I'll look instead for the growth of $\rho(A)$ as a proxy for the CFL constant (for example, DG gives $\rho(A) < Ch/p^2$). Is it known how $\rho(A)$ for FD discretizations depends on stencil order or type?

$\endgroup$
5
$\begingroup$

I'm going to guess that there isn't one. In the usual method of lines for $u_t +au_x=0$, you end up with a system of ODEs of the form $$ u_t = Au. $$

So the restriction on the time step comes from (1) requiring that eigenvalues of $A$ lie in the domain of stability of whatever time-stepping method you use (e.g., if $A$ is skew-symmetric, with imaginary eigenvalues, then forward Euler is always unstable), and (2) from minimizing error (if both space and time discretizations are second-order, then $\delta t=\delta x$).

So based on this reasoning, I'd say no, because there is too much freedom in how you can pick the r.h.s. matrix and the time-stepping method, and the result has less to do specifically with the order of the method, and more to do with other properties, mainly $A$'s spectrum. Of course this doesn't quite rule out such a formula, but my understanding is that the stability analysis has to be done case-by-case.

$\endgroup$
  • $\begingroup$ Thanks @Kirill. A related question then: I'm interested in the growth of $\rho(A)$ as a proxy for the CFL constant (for example DG gives a bound $\rho(A) \leq O(h/p^2)$). Is it known how $\rho(A)$ for FD discretizations depends on stencil order or stencil type? $\endgroup$ – Jesse Chan Aug 11 '15 at 19:03
  • $\begingroup$ @JesseChan Sorry, can't tell you anything useful off the top of my head. But: the thing that governs stability is $\|e^{A\delta t}\|$, which isn't quite the same as $\rho(A)$ when $A$ is not a normal matrix. Maybe the literature on matrix pseudospectra would be relevant here. $\endgroup$ – Kirill Aug 11 '15 at 19:27
  • 2
    $\begingroup$ @JesseChan E.g., Pseudospectra of Linear Operators by Trefethen. $\endgroup$ – Kirill Aug 11 '15 at 19:31
1
$\begingroup$

At least in one dimensional case for linear advection I have not experienced for finite difference methods the CFL restriction depending on the precision order as you write. Conditionally stable explicit in time well designed numerical schemes have typically the restriction $dt \le C h$, I have such experience (and proofs) with 2nd and 3rd order accurate schemes, the stencil being at most 5 nodes, i. e. from i-2 to i+2.

Opposite to DG methods where degrees of freedom for higher methods are localized at the same geometric location (element), the standard finite difference methods are increasing also the geometric stencil when increasing the precision order.

Standard text books on finite difference (or related finite volume) methods relate the CFL condition to a "domain of influence" that depends on the equation you solve. Maybe some "geometric" clustering of degrees of freedom in DG method introduce the unfavourable influence of CFL condition on the order of method, but my subjective opinion would not expect it with finite difference methods.

Addendum

I was asked for references, here is one:

Principles of Computational Fluid Dynamics - Pieter Wesseling, 2001, see Theorem 9.3.3 on so called kappa class of schemes for 1D advection equation $u_t + v u_x=0$ with constant speed $v$. Several 2nd order schemes belong to this class and one 3rd order accurate (QUICKEST), the stability is reached for Courant number $dt v/h$ less or equal 1. It is so called von Neumann stability (Fourier series analysis).

I do not work with higher order methods than 3, but I know from papers and conferences that e.g. so called ADER schemes (M. Dumbser use it also for DG) can produce arbitrary order of accuracy and I do not know about any bad behaviour of schemes with respect to the CFL condition, but I might be wrong.

$\endgroup$
  • $\begingroup$ Thanks Peter - would you mind linking me to any of those proofs? It it known how $C$ depends on stencil order (or width)? I think polynomial bases in general tend to introduce issues with CFL, as high order polynomials can vary rapidly at domain boundaries (there is a discussion in @Kirill's link on Pseudospectra, as well as in Markov inequalities for polynomial derivatives) $\endgroup$ – Jesse Chan Aug 13 '15 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.