This looked true to me, I worked through the algebra for 1D and confirmed it. But no one seems to mention it, so maybe I'm missing something...

I'm using Bridson's SIGGRAPH 2007 course notes. [5MB pdf], p. 21 (page 33 in the pdf).

Semi-Lagrangian: back-trapolate the velocity field, to find the "particle" that would end up here ($x_i$), then linearly interpolate to get the value of that particle (pressure or whatever), which will become the value here ($q_i$).

Here, I assume velocity $u>0$ (to the right) and $\Delta t u < \Delta x$ (so the particle's previous position $x_P$ lies within the interval $[x_{i-1},x_i]$).

back-trapolate: $$x_P = x_i - \Delta t u_i$$

interpolate: $$\alpha = \frac{x_P - x_{i-1}}{\Delta x}$$

$$q_i^{t+1} = (1-\alpha)q_{i-1} + (\alpha)q_i$$

Upwind Euler Choose forward or backward Euler, depending on the direction information is coming from, i.e. "upwind". This is stable, with my velocity restriction.

Reusing the above velocity restriction (to the right; moves less than a cell-width in a timestep).

$$q_i^{t+1} = q_i - \frac{\Delta t u_i(q_i - q_{i-1})}{\Delta x}$$

This is identical to the semi-Lagrangian above. (I won't go through all the algebra here, but I began by expanding the semi-Lagrangian into one line and used $x_i - x_{i-1} = \Delta x$).

They're also identical for $u<0$, just using the cell to the right i.e. $x_i$ and $x_{i+1}$ instead of $x_{i-1}$ and $x_i$.

Semi-Lagrangian advection enables jumping multiple cells (which I exclude with my velocity restriction), the only difference seems to be handling the velocity direction by determining which cell interval the particle lies in.

What am I missing? Perhaps higher-order "semi-Lagrangian" schemes don't correspond to upwind schemes so neatly?

Or maybe, jumping multiple cells is very useful sometimes? (In my case, I need the velocity restriction anyway).

I prefer upwind Euler, because it's simpler to calculate, less complex and easier to understand. But I've got into trouble before by "improving" schemes: my confidence exceeded my competence. So I'm checking this time.

  • 1
    $\begingroup$ I think there are major differences in 2d/3d. SL methods will involve corner cells also if the characteristic goes that way. Standard schemes use 1d stencils and corner cells are not involved. Of course there are special multi-d schemes which make use of corners also. $\endgroup$ – cfdlab Aug 1 '19 at 14:19
  • 1
    $\begingroup$ Semi-Lagrangian advection is popular especially in Computer Graphics, as it is unconditionally stable, even with a CFL larger than 1. My impression is that a CFL larger than 1 is quite common in CG. $\endgroup$ – dweber Aug 1 '19 at 17:28

Your Answer

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

Browse other questions tagged or ask your own question.