Conservative Multi-dimensional Semi-Lagrangian Finite Difference Scheme: Stability and Applications to the Kinetic and Fluid Simulations

Abstract

In this paper, we propose a mass conservative semi-Lagrangian finite difference scheme for multi-dimensional problems without dimensional splitting. The semi-Lagrangian scheme, based on tracing characteristics backward in time from grid points, does not necessarily conserve the total mass. To ensure mass conservation, we propose a conservative correction procedure based on a flux difference form. Such procedure guarantees local mass conservation, while introducing time step constraints for stability. We theoretically investigate such stability constraints from an ODE point of view by assuming exact evaluation of spatial differential operators and from the Fourier analysis for linear PDEs. The scheme is tested by classical two dimensional linear passive-transport problems, such as linear advection, rotation and swirling deformation. The scheme is applied to solve the nonlinear Vlasov–Poisson system and guiding center Vlasov model using high order tracing schemes. The effectiveness of the proposed conservative semi-Lagrangian scheme is demonstrated numerically by extensive numerical tests.

1 Introduction

Semi-Lagrangian (SL) schemes have been used extensively in many areas of science and engineering, including weather forecasting [11, 14, 26], kinetic simulations [8, 12] and fluid simulations [16, 29], interface tracing [7, 27], etc. The schemes are designed to combine the advantages of Eulerian and Lagrangian approaches. In particular, the schemes are built upon a fixed computational mesh. Similar to the Eulerian approach, high spatial resolution can be realized by using high order interpolation/reconstruction procedures or by using piecewise polynomial solution spaces. On the other hand, in each time step evolution, the scheme is designed by propagating information along characteristics, relieving the CFL condition. Typically, the numerical time step size allowed for an SL scheme is larger than that of an Eulerian approach, leading to gain in computational efficiency.

Among high order SL schemes, depending on solution spaces, different classes of methods can be designed. For example, a finite difference scheme evolves point-wise values and realizes high spatial resolution by high order interpolation procedures [17, 29], a finite volume scheme considers integrated cell-averages with high order reconstruction procedures [6, 14], while a finite element method has piecewise continuous or discontinuous polynomial functions as its solution space [11, 15, 16, 20, 21]. Each class of the above mentioned SL methods has its own advantages. For example, the finite element method is more flexible with the geometry and handling boundary conditions, while the finite difference and finite volume schemes could perform better in resolving solution structures with sharp gradients, e.g. by using a weighted essentially non-oscillatory (WENO) procedure. To compare finite difference and finite volume schemes, finite volume scheme is often considered more physically relevant and the local mass conservation can be built up in a natural way; while the finite difference scheme is more computationally efficient for high-dimensional problems, if one considers schemes of third order or higher.

In this paper, we consider SL finite difference schemes with local mass conservation property. In fact, many existing SL finite difference schemes are built based on tracing characteristics backward in time together with a high order interpolation procedure [3]. Typically such schemes do not have local mass conservation property, which is fine for certain applications. However, for applications in weather forecasting or in kinetic simulations, ignoring local mass conservation could lead to significant loss of total mass, especially when the solution with sharp gradients becomes under-resolved by the computational mesh [13].

There have been many attempts to preserve the mass conservation of an SL finite difference scheme with large time stepping sizes, e.g. [17, 19]. However, they are mostly designed for 1D problems by taking advantage of some special features in a 1D setting. Their generalization to high dimensional problems often relies on dimensional splitting which is subject to splitting errors. In this paper, we propose and investigate a truly multi-dimensional approach without dimensional splitting errors. To build an SL finite difference scheme with local mass conservation, one essential framework that we propose to work with is the flux-difference form. However, by working with the flux difference form, one often may observe time step constraint for numerical stability. Note that unlike the Eulerian approach, such time step constraint does not come from the CFL condition (i.e. numerical domain of dependence should include the physical domain of dependence), but from numerical stability one employed for temporal integration. As far as we are aware of, there is little work in quantifying the stability constraint and in optimizing the numerical strategies balancing stability, accuracy and computational efficiency. This paper aims to fill such gap, by understanding such time step constraints. In particular, we investigate the stability of time integration schemes based on a linear stability analysis around the imaginary axis in the complex plane, assuming the spatial differentiation is exact. We optimize quadrature rules for time integration by maximizing the stability interval along the imaginary axis. We further employ Fourier analysis to study the numerical stability of a fully-discretized scheme. The schemes are applied to 2D passive-transport problems, as well as to nonlinear Vlasov–Poisson (VP), guiding center Vlasov model and incompressible Euler system in vorticity stream function formulation, by using high order characteristics tracing schemes proposed in [18, 28]. Finally, we would like to mention a few of our previous work related to stability of SL finite difference schemes in a flux-difference form. In [19], a special treatment is introduced to relieve the time step constraint for 1D passive transport problems. However, such treatment is not possible for general high dimensional problems. In [5], the time step constraint is studied by Fourier analysis for an SL finite difference scheme coupled with integral deferred correction framework.

The paper is organized as follows. The SL finite difference scheme in flux-difference form is described in Sect. 2. The stability of time integration with quadrature rule is investigated in Sect. 3, assuming exact evaluation of spatial differentiation operators. We also optimize temporal integration rules. In Sect. 4, we study the numerical stability of a fully discretized scheme by Fourier analysis. In Sect. 5, numerical tests are performed for 2D linear passive-transport problems. In Sect. 6, we apply the scheme to the nonlinear VP system, the guiding center Vlasov equation and incompressible Euler system.

2 A Mass Conservative SL Finite Difference Scheme

In this section, we describe an SL finite difference scheme based on a flux-difference form to locally preserve mass. The scheme starts from a standard non-conservative procedure with backward characteristics tracing and high order spatial interpolation. Then a conservative correction is performed by a flux-difference formulation. We describe the scheme in a 1D linear setting, noting that its extension to nonlinear and high dimensional problems is straightforward, as long as characteristics can be properly traced backward in time, e.g. see our numerical examples in Sect. 5.

We consider a 1D linear advection equation,

$$\begin{aligned} \frac{\partial f}{\partial t} + \frac{\partial f}{\partial x} = 0, \quad f(x,0) = f^0(x), \quad x\in [-\pi , \pi ]. \end{aligned}$$

(2.1)

For simplicity, we assume a periodic boundary condition. We assume a uniform discretization in space with $x_j = j\Delta x$, $j=1,\ldots ,n_x$ and let $f^n_j$ be an approximation of the solution at time $t^n$ and position $x_j$. We describe below the conservative SL procedure to update $\{f^{n+1}_j\}_{j=1}^{n_x}$ from $\{f^n_j\}_{j=1}^{n_x}$.

In an Eulerian finite difference method, typically one would firstly approximate the spatial derivative by a flux difference form to ensure mass conservation, then the system of ODEs will be evolved in time by a high order numerical integrator such as the Runge-Kutta (RK) method via the method of lines. In the SL setting, however, we propose to perform the time integration based on quadrature rules first,

$$\begin{aligned} f^{n+1}_j = f^n_j - \frac{\partial }{\partial x}\left( \int _{t^n}^{t^{n+1}} f(x, t)dt\right) |_{x=x_j} \approx f^n_j - \frac{\partial }{\partial x} ({\mathcal {F}}(x))|_{x_j}, \end{aligned}$$

(2.2)

where we let

$$\begin{aligned} {\mathcal {F}}(x) \doteq \sum _{\ell =1}^{s} f(x, t^n+c_\ell \Delta t) b_\ell \Delta t \end{aligned}$$

(2.3)

as a quadrature approximation of $\int _{t^n}^{t^{n+1}} f(x, t)dt$. Here $(c_\ell ,b_\ell )$, $\ell = 1,\ldots ,s$ are the nodes and weights of an accurate quadrature formula and $f(x_j, t^n+c_\ell \Delta t)$, $\ell =1,\ldots ,s$ (we call it stage values) can be approximated via a non-conservative SL scheme via backward characteristics tracing and high order spatial interpolation. For the linear equation (2.2), $f(x_j, t^n+c_\ell \Delta t)$ can be traced back along characteristics to $t^n$ at $f(x_j-c_\ell \Delta t, t^n)$, whose value can be obtained via interpolation from neighboring grid point values $\{f^n_j\}_{j=1}^{n_x}$, see our description for different interpolation procedures in Sect. 4. Then a conservative scheme, based on a flux-difference form, can be proposed in the spirit of the work by Shu and Osher [24]. In particular, the scheme can be formulated as

$$\begin{aligned} f^{n+1}_j = f^n_j - \frac{1}{\Delta x} \left( \hat{F}_{j+\frac{1}{2}} - \hat{F}_{j-\frac{1}{2}}\right) , \end{aligned}$$

(2.4)

where $\hat{F}_{j+\frac{1}{2}}$ comes from WENO reconstruction of fluxes from $\{{\mathcal {F}}_j\}_{j=1}^{n_x}$ with ${\mathcal {F}}_j \doteq {\mathcal {F}}(x_j)$. We refer to [23] for the basic principle and detailed procedures of WENO reconstruction. Also, Sect. 4 provides detailed discussions on different reconstruction procedures. It can be shown that the mass conservation is locally preserved due to the flux difference form (2.4).

Such conservative correction procedure can be directly generalized to problems with non-constant velocity fields in a multi-dimensional setting without any difficulty, e.g. rotation and swirling deformation. In addition to the procedures described above, a high order ODE integrator such as a RK method can be employed to locate the foot of a characteristic accurately. For example, we consider a 2D problem with a prescribed velocity field a(x, y, t) and b(x, y, t)

$$\begin{aligned} f_t + \left( a(x, y, t) f\right) _x + \left( b(x, y, t) f\right) _y = 0. \end{aligned}$$

Let the set of grid points

$$\begin{aligned} x_1< \cdots< x_i< \cdots< x_{n_x}, \quad y_1< \cdots< y_j< \cdots < y_{n_y} \end{aligned}$$

(2.5)

be a uniform discretization of a 2D rectangular domain with $x_i = i \Delta x$ and $y_j = j \Delta y$. The foot of characteristic emanating from a 2D grid point, say $(x_i, y_j)$ at $t^{\ell }\doteq t^n+c_\ell \Delta t$ can be located by solving the following final-value problem accurately with a high order RK method,

$$\begin{aligned} \frac{dx}{dt} = a(x, y, t), \quad \frac{dy}{dt} = b(x, y, t), \quad x(t^\ell ) = x_i, \quad y(t^\ell ) = y_j. \end{aligned}$$

(2.6)

Once the foot of characteristic located, say at $(x^\star _i, y^\star _j)$, then $f(x_i, y_j, t^{\ell })$ can be evaluated by approximating $f(x^\star _i, y^\star _j, t^n)$ via a high order 2D interpolation procedure [23]. A 2D conservative scheme based on a flux-difference form can be formulated as

$$\begin{aligned} f^{n+1}_{ij} = f^n_{ij} - \frac{1}{\Delta x} \left( \hat{F}_{i+\frac{1}{2}, j} - \hat{F}_{i-\frac{1}{2}, j}\right) - \frac{1}{\Delta y} \left( \hat{G}_{i, j+\frac{1}{2}} - \hat{G}_{i, j-\frac{1}{2}}\right) , \end{aligned}$$

(2.7)

where $\hat{F}_{i\pm \frac{1}{2}, j}$ comes from WENO reconstruction of fluxes from $\{{\mathcal {F}}_{ij}\}_{i=1}^{n_x}$ for all j with

$$\begin{aligned} {\mathcal {F}}_{ij} \doteq {\mathcal {F}}(x_i, y_j) \approx \Delta t \sum _{\ell =1}^{s} f(x_i, y_j, t^n+c_\ell \Delta t) b_\ell . \end{aligned}$$

The procedure for WENO reconstruction is the same as the 1D case for all j and we again refer to the review paper [23]. Similarly, $\hat{G}_{i, j\pm \frac{1}{2}}$ comes from WENO reconstruction of fluxes from $\{{\mathcal {F}}_{ij}\}_{j=1}^{n_y}$ for all i.

To generalize the conservative SL scheme to nonlinear systems, a problem-dependent high order characteristics tracing procedure needs to be designed for solving the final-value problem in the form of Eq. (2.6), but with the velocity field depending on the unknown function f. In many cases, a high order RK method could not be directly applied. In [18], a high order multi-dimensional characteristics tracing scheme for the VP system is proposed, and in [28], it has been generalized for the guiding center Vlasov system and the incompressible Euler system in the vorticity-stream function formulation. Both can be applied in the above proposed conservative SL framework.

We close this section by making the following remark to motivate our discussions in the following two sections. There are two issues in the scheme formulation that contribute to the stability property of the above proposed SL scheme. One is the discretization by the quadrature rule (2.3). This part of stability is viewed as an ODE stability (assuming exact evaluation of spatial operators) and is investigated carefully in Sect. 3. The other issue concerns the spatial discretization, and can be explained by observing the following situation: if one changes the time stepping size slightly (could be arbitrary small), the root of characteristics $x_j-c_\ell \Delta t$ could come from a different grid cell, leading to a different interpolation stencil in the implementation. This aspect is investigated in Sect. 4.

3 Temporal Discretization and Stability

3.1 Linear stability functions and stability regions

We first investigate the linear stability of quadrature rules for temporal discretization (2.3) in an ODE setting, by assuming an exact evaluation of spatial derivative in Eq. (2.2). In particular, we look for the evolution of a Fourier mode, identified by a Fourier variable $\xi \in [-\pi , \pi ]$, assuming exact evaluation of spatial interpolation and reconstruction procedure mentioned above. Such a discrete Fourier mode at time $t^n = n \Delta t$, will be denoted by,

$$\begin{aligned} f_\xi ^n(x) = (Q(\xi ))^n e^{{\mathbf {i}} x \xi /\Delta x}, \quad {\mathbf {i}} = \sqrt{-1}, \end{aligned}$$

(3.1)

where $Q(\xi )$ is the amplification factor associated with $\xi$. After plugging such ansatz into the expression for the flux, Eq. (2.3), and taking into account Eq. (3.1), we have:

$$\begin{aligned} {\mathcal {F}}(x) = \sum _{\ell =1}^s b_\ell f^n(x-c_\ell \Delta t)\,\Delta t = Q^n(\xi )\sum _{\ell =1}^s b_\ell \exp \left[ {\mathbf {i}}\xi \left( x-c_\ell \Delta t\right) /\Delta x\right] \, \Delta t \end{aligned}$$

Using such expression in Eq. (2.2) gives:

$$\begin{aligned} f_j^{n+1} = f^n_j - Q^n(\xi )\exp ({\mathbf {i}}\xi x/\Delta x) \frac{\Delta t}{\Delta x}{\mathbf {i}}\xi \sum _{\ell =1}^s b_\ell \exp (-{\mathbf {i}}\xi c_\ell \Delta t/\Delta x) \end{aligned}$$

from which we deduce

$$\begin{aligned} Q(\xi ) = 1- {\mathbf {i}} \xi a \sum _{\ell =1}^s b_\ell \exp ({-{\mathbf {i}}c_\ell \xi a}), \end{aligned}$$

(3.2)

where $a = \Delta t/\Delta x$ denotes the Courant number. The scheme is stable if

$$\begin{aligned} |Q(\xi )|\le 1, \quad \forall \xi \in [-\pi , \pi ]. \end{aligned}$$

Such stability property is closely related to the linear stability of the quadrature rule, which can be studied by the stability region for a scalar linear ODE.

3.2 Relation with A-Stability

Let us recall the definition of A-stability. Consider the scalar ODE

$$\begin{aligned} w'(t) = \lambda w(t), \qquad w(0) = 1 \end{aligned}$$

(3.3)

and $\lambda \in \mathbb {C}$. The solution after one time step is given by

$$\begin{aligned} w(\Delta t) = e^{\lambda \Delta t} = e^z, \end{aligned}$$

where we set $z\equiv \lambda \Delta t$. Such solution is stable if and only if $\mathfrak {R}(z)\le 0$, i.e. if and only if $\mathfrak {R}(\lambda ) \le 0$. Consider now the following identity

$$\begin{aligned} e^z = 1 + z \int _0^1 e^{\alpha z}\,d\alpha . \end{aligned}$$

(3.4)

This is really an identity, because $\int _0^1 e^{\alpha z} \, d\alpha = (e^z-1)/z =: \varphi (z)$. Now let us approximate the integral appearing in Eq. (3.4) by a quadrature formula, whose nodes and weights are, respectively, $c_\ell$ and $b_\ell$, $\ell = 1, \ldots , s$. Then one obtains the following approximation of the exact solution of Eq. (3.3) after one time step:

$$\begin{aligned} R(z) = 1 + z \sum _{\ell = 1}^s b_\ell e^{c_\ell z}. \end{aligned}$$

(3.5)

It is clear that in general it is not true that $|R(z)|\le 1$ if $\mathfrak {R}(z)\le 0$. Neglecting all other approximations, the core reason of the instability of the SL conservative method relies on the lack of unconditional stability in the approximation of $e^z$ by R(z) for z purely imaginary. This relation can be immediately applied to the study of the stability of the SL conservative scheme, since comparing Eq. (3.2) with Eq. (3.5), one has

$$\begin{aligned} Q(\xi ) = R(-i\xi a). \end{aligned}$$

Because $\xi \in [-\pi ,\pi ]$, the stability problem can be stated as follows: look for the largest interval $I^*\equiv [-y^*,y^*]$ of the imaginary axis such that $|R(iy)| \le 1$, $\forall y\in I^*$. Then the maximum CFL number for the SL scheme that guarantees stability will be

$$\begin{aligned} a^* = y^*/\pi \end{aligned}$$

(3.6)

Below, we report the stability regions for the following commonly used quadrature rules in the left panel of Fig. 1.

• 1. midpoint: $q_1 = 1/2$, $w_1=1$.

• 2. trapezoidal: $q_1 = 0, q_2 = 1$, $w_1 = w_2 = 1/2$.

• 3. Simpson: $q_1=0, q_2=1/2, q_3=1$, $w_1 = w_3=1/6, w_2=2/3$.

• 4. two-point Gauss–Legendre formulas (GL2): $q_1=\frac{1}{2}-\frac{1}{2\sqrt{3}}, q_2=\frac{1}{2} +\frac{1}{2\sqrt{3}}$, $w_1=w_2=1/2$.

As it is apparent from the plot, midpoint and Simpson’s rule do not include a portion of the imaginary axis, while the trapezoidal rule and the two-point Gauss–Legendre rule do. The boundary of the stability region of the trapezoidal rule intersects the imaginary axis at $\pi$, and therefore the maximum CFL number that guarantees linear stability for the conservative scheme is $\pi /\pi = 1$. The two point Gauss–Legendre quadrature formula provides a wider stability interval, since in this case $y^*\approx 5.43$, giving a maximum CFL number of approximately $5.43/\pi =1.72$. Higher order Gauss–Legendre quadrature formulas, hereafter denoted by GLs, where s indicates the number of nodes, may provide wider stability interval, as is illustrated in the right panel of Fig. 1. To better appreciate the stability region, we plot in Fig. 2$|R({\mathbf {i}}y)|^2-1$ as a function of y. GL4 is observed to have better stability property, as $|R({\mathbf {i}}y)|^2-1 \le 0$ for an interval with boundary $y^*\approx 6.2765$ leading to a maximum CFL number of approximately $6.2765/\pi =1.99$. Gauss–Legendre rule formulas with odd number of points, such as GL3 and GL5, are unstable near the origin, see the right panel of Fig. 1 as well as Fig. 2.

Fig. 1

Stability region for midpoint, trapezoidal, Simpson’s and two-point Gauss–Legendre rules (left) and GLs with $s=2, 3, 4, 5$ (right)

Fig. 2

$R({\mathbf {i}}y)^2-1$ versus y for GL3, GL4, GL5 formulas. GL3 and GL5 is observed to be unstable

3.3 Maximize the Stability Interval on Imaginary Axis

In order to analyze the stability of quadrature formulas, let us consider the expression $R({\mathbf {i}}y)$ from Eq. (3.5), and write it in the form

$$\begin{aligned} R({\mathbf {i}}y) = 1+{\mathbf {i}}y(C_s(y) + i S_s(y)) = 1-yS_s(y) + {\mathbf {i}}y C_s(y) \end{aligned}$$

(3.7)

where

$$\begin{aligned} C_s(y)\equiv \sum _{\ell =1}^sb_\ell \cos (c_\ell y), \quad S_s(y)\equiv \sum _{\ell =1}^sb_\ell \sin (c_\ell y). \end{aligned}$$

(3.8)

The stability condition therefore becomes

$$\begin{aligned} |R({\mathbf {i}}y)|^2 = 1-2yS_s(y) + y^2 \left( C_s^2(y)+S_s^2(y) \right) \le 1. \end{aligned}$$

Such condition can be written in the form

$$\begin{aligned} y F_s(y) \ge 0, \end{aligned}$$

(3.9)

where

$$\begin{aligned} F_s(y)\equiv S_s(y) - \frac{1}{2}y\left( C_s^2(y)+S_s^2(y)\right) . \end{aligned}$$

(3.10)

The problem of finding quadrature formulas with the widest stability region can be stated as: determine the coefficients ${\mathbf {b}}=(b_1, \ldots , b_s)$ and ${\mathbf {c}}=(c_1, \ldots , c_s)$ so that the interval in which (3.9) is satisfied is the widest.

Rather than directly solving this optimization problem, we consider a particular case of quadrature formulas, i.e. those for which the nodes are symmetrically located with respect to point 1 / 2 in the interval [0, 1]. The choice is motivated by the observation that several quadrature formulas have a symmetric distribution of nodes and weights around the center of the integration interval. Furthermore, such an assumption greatly simplifies the derivation and analysis of the methods. Among such formulas we restrict to the case in which s even, as the schemes are observed to be unstable for odd s, see Fig. 2.

Let us denote by $\tilde{c}_\ell = 1-2 c_\ell , \ell = 1, \ldots , s$. Then $c_\ell = (1-\tilde{c}_\ell )/2$. Since the nodes are symmetric and the quadrature formula is interpolatory, we have

$$\begin{aligned} \tilde{c}_\ell = -\tilde{c}_{s-\ell +1}, \quad b_\ell = b_{s-\ell +1}. \end{aligned}$$

(3.11)

The absolute stability function $R({\mathbf {i}}y)$ can then be written, after simple manipulations, as

$$\begin{aligned} R({\mathbf {i}}y) = 1-2y \sin (y/2) \tilde{C}_s(y) + 2 {\mathbf {i}}y \cos (y/2)\tilde{C}_s(y), \end{aligned}$$

where

$$\begin{aligned} \tilde{C}_s(y)\equiv \sum _{\ell =1}^{s/2}b_\ell \cos (\tilde{c}_\ell y/2), \end{aligned}$$

leading to

$$\begin{aligned} |R({\mathbf {i}}y)|^2 = 1-4y \sin (y/2)\tilde{C}_s(y) + 4 y^2 \tilde{C}_s^2(y). \end{aligned}$$

(3.12)

The function $F_s(y)$ can then be written, after simple manipulations

$$\begin{aligned} F_s(y) = 2 \tilde{C}_s(y) \left( \sin (y/2) - y \tilde{C}_s(y)\right) . \end{aligned}$$

(3.13)

Then the stability condition (3.9) becomes

$$\begin{aligned} \tilde{C}_s(y) \left( \sin (y/2) - y \tilde{C}_s(y)\right) \ge 0. \end{aligned}$$

Because function $F_s$ contains the product of two factors, the condition to ensure that the function does not change sign at roots is that the two factors vanish simultaneously at simple roots, therefore $\tilde{C}_s(y)$ has to vanish also at the same points $y_k > 0$ at which $\sin (y/2) - y \tilde{C}_s(y)=0$. There is no need to impose that $\tilde{C}_s$ vanishes at the origin, since, because of symmetry, $yF_s(y)$ does not change sign at the origin.

In order to determine the coefficients that define the quadrature formula for maximizing the stability interval on imaginary axis, we proceed as follows. Because of the symmetry constraints (3.11), we have to find s coefficients, i.e. $b_1,\ldots ,b_{s/2}$ and $\tilde{c}_1,\ldots ,\tilde{c}_{s/2}$ by imposing a total of s conditions. Such conditions will be a balance between accuracy and stability. If we want that the quadrature formulas have degree of precision $s-1$, i.e. if we want that they are exact for polynomials of degree less or equal to $s-1$, we have to impose

$$\begin{aligned} \frac{1}{2} \int _{-1}^1 \zeta ^{2k} \, d\zeta = \sum _{\ell =1}^sb_\ell (\tilde{c}_\ell )^{2k}, \quad k=0,\ldots ,s/2-1. \end{aligned}$$

(3.14)

We only impose the condition for even polynomials, since for odd polynomials the conditions are automatically satisfied because of the symmetry. The condition that $\tilde{C}_s(y)$ vanishes when $\sin (y/2)-y\tilde{C}_s(y)$ vanishes becomes

$$\begin{aligned} \tilde{C}_s(2\pi k) = 0, \quad k=1,\ldots ,s/2. \end{aligned}$$

(3.15)

For $k=0$ the stability condition (3.15) is marginally satisfied since $\tilde{C}_s(0) = \sum _{\ell =1}^{s/2}b_\ell = 1/2$. Eqs. (3.14) and (3.15) constitute a nonlinear set of equations for the s coefficients $b_1,\ldots ,b_{s/2}$ and $\tilde{c}_1,\ldots ,\tilde{c}_{s/2}$. Because the equations are nonlinear, we have to resort to Newton’s method for their solution. In practice, for large values of s, it is hard to find an initial guess which lies in the convergence basin of Newton’s method. We had to resort to a relaxed version of Newton’s method, coupled with continuation techniques, in order to solve the system.

We numerically compute nodes and weights for $s=2, 4, 6, 8, 10, 12$ and check a posteriori whether the stability condition is actually satisfied. The following phenomena are observed:

• $s=2$: the quadrature nodes and weights are consistent with those of the two-point Gauss–Legendre formula.

• $s = 4, 8, 12$: In Fig. 3 we plot the functions $|R_s({\mathbf {i}}y)|^2-1$ (left panel) and the corresponding stability regions in the complex plane (right panel) for $s = 4, 8, 12$. A wide interval with stability on the imaginary axis is shown. We report the coefficients in Table 1. Only s / 2 coefficients are reported, since the other satisfy the symmetry relation (3.11). We also report the maximum CFL number $a^* =y^*/\pi$ [see Eq. (3.6)].

• $s=6$ and $s=10$: In Fig. 4, we plot the functions $|R_s({\mathbf {i}}y)|^2-1$ for $s = 6$ and $s = 10$. It is observed that $|R_s({\mathbf {i}}y)|^2\ge 1$ for any interval containing the origin, i.e. these two quadrature formulas are not stable.

Fig. 3

Left: plot of $|R({\mathbf {i}}y)|^2$ for the symmetric quadrature formulas with $s = 4, 8, 12$. Right: plot of stability regions for the corresponding quadrature formulas. These formulas show a wide stability interval on the imaginary axis, thus allowing, in principle, large CFL numbers

Fig. 4

Plot of $|R({\mathbf {i}}y)|^2-1$ for the symmetric quadrature formulas with $s = 6, 10$. Such formulas are not stable because the stability region do not contain a portion of the imaginary axis

Table 1 Weights and nodes of accurate and stable quadrature formulas

The stability regions for the quadrature formulas obtained for $s=4,8,12$ reported in Table 1 are computed under the assumption that one considers the exact space dependence of the Fourier mode, so that the only error is in time integration. In reality there are several other causes of errors, that may affect the stability region of the quadrature. In the next section, we take spatial discretization into account and quantify the corresponding stability interval.

4 Spatial Discretization

There are two spatial discretization processes in the scheme. One is the interpolation in approximating $f(x_j, t^n+c_\ell \Delta t) = f(x_j-c_\ell \Delta t, t^n)$ from neighboring grid point values $\{f^n_j\}_{j=1}^{n_x}$. The other is the reconstruction in obtaining numerical fluxes $\hat{F}_{j+\frac{1}{2}}$ in (2.4) from $\{{\mathcal {F}}_j\}_{j=1}^{n_x}$. In this paper, we consider the following two classes of spatial discretizations.

• Odd order approximations. For the linear equation (2.1), we use a right-biased stencil to approximate $f(x_j-c_\ell \Delta t, t^n)$ and use a left-biased stencil for reconstructing the flux $\hat{F}_{j+\frac{1}{2}}$. For example, for a first order scheme with $\Delta t/\Delta x<1$, $f(x_j-c_\ell \Delta t, t^n)$ is approximated from the interpolation stencil $\{f_j\}$ and the numerical flux $\hat{F}_{j+\frac{1}{2}}$ is approximated from the reconstruction stencil $\{{\mathcal {F}}_j\}$. With such stencil arrangement, the SL scheme is reduced to a first order upwind scheme when $\Delta t/\Delta x<1$,

  $$\begin{aligned} f^{n+1}_j = f^n_j - \Delta t/\Delta x (f^n_j - f^n_{j-1}). \end{aligned}$$

  Third, fifth, seventh and ninth order schemes can be constructed by including one, two, three, four more points symmetrically from left and from right, respectively, in the interpolation and reconstruction stencils. We list them as follows.

  $$\begin{aligned} \begin{array}{lll} &{}\text{ Third } \text{ order }: &{} \{f_{j-1}, f_j, f_{j+1}\}, \quad \{{\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}\}.\\ &{}\text{ Fifth } \text{ order }: &{} \{f_{j-2}, f_{j-1}, f_j, f_{j+1}, f_{j+2}\}, \quad \{{\mathcal {F}}_{j-2}, {\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}\}.\\ &{}\text{ Seventh } \text{ order }: &{} \{f_{j-3}, f_{j-2}, f_{j-1}, f_j, f_{j+1}, f_{j+2}, f_{j+3}\}, \\ &{} &{} \{{\mathcal {F}}_{j-3}, {\mathcal {F}}_{j-2}, {\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}, {\mathcal {F}}_{j+3}\}.\\ &{}\text{ Ninth } \text{ order }: &{} \{f_{j-4}, f_{j-3}, f_{j-2}, f_{j-1}, f_j, f_{j+1}, f_{j+2}, f_{j+3}, f_{j+4}\}, \\ &{} &{} \{{\mathcal {F}}_{j-4}, {\mathcal {F}}_{j-3}, {\mathcal {F}}_{j-2}, {\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}, {\mathcal {F}}_{j+3}, {\mathcal {F}}_{j+4}\}. \end{array} \end{aligned}$$

• Even order approximations. For the linear equation (2.1), we use symmetric stencils to approximate $f(x_j-c_\ell \Delta t, t^n)$ by interpolation and to approximate $\hat{F}_{j+\frac{1}{2}}$ by reconstruction. For example, for a second order scheme with $\Delta t/\Delta x<1$, $f(x_j-c_\ell \Delta t, t^n)$ is approximated from the interpolation stencil $\{f_{j-1}, f_j\}$ and the numerical flux $\hat{F}_{j+\frac{1}{2}}$ is approximated from the reconstruction stencil $\{{\mathcal {F}}_j, {\mathcal {F}}_{j+1}\}$. Fourth, sixth and eighth order schemes can be constructed by including one, two, three more points symmetrically from left and from right, respectively, in the interpolation and reconstruction stencils. We list them as follows.

  $$\begin{aligned} \begin{array}{lll} &{}\text{ Fourth } \text{ order }: &{} \{f_{j-2}, f_{j-1}, f_j, f_{j+1}\}, \quad \{{\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}\}.\\ &{}\text{ Sixth } \text{ order }: &{} \{f_{j-3}, f_{j-2}, f_{j-1}, f_j, f_{j+1}, f_{j+2}\}, \\ &{} &{} \{{\mathcal {F}}_{j-2}, {\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}, {\mathcal {F}}_{j+3}\}.\\ &{}\text{ Eighth } \text{ order }: &{} \{f_{j-4}, f_{j-3}, f_{j-2}, f_{j-1}, f_j, f_{j+1}, f_{j+2}, f_{j+3}\}, \\ &{} &{} \{{\mathcal {F}}_{j-3}, {\mathcal {F}}_{j-2}, {\mathcal {F}}_{j-1}, {\mathcal {F}}_j, {\mathcal {F}}_{j+1}, {\mathcal {F}}_{j+2}, {\mathcal {F}}_{j+3}, {\mathcal {F}}_{j+4}\}. \end{array} \end{aligned}$$

Remark 4.1

We follow the same principle in the interpolation and reconstruction procedures in more general settings, for example the situation when the time stepping size is greater than the CFL restriction, i.e $\Delta t/\Delta x \ge 1$ for Eq. (2.1). For example, if $\Delta t/\Delta x$ is between 1 and 2 then all the stencils for the computation of $f(x_j-\Delta t)$ are shifted to the left by one, and so on. For general high dimensional problems, e.g. the Vlasov equation, similar procedures can be applied in a truly multi-dimensional fashion.

To access the stability property of the conservative method, we perform Fourier analysis via the linear equation (2.1) with $x\in [0, 2\pi ]$ and periodic boundary condition. In particular, we make the ansatz $f^n_j = \hat{f}^n e^{{\mathbf {i}} j \xi }$ with ${\mathbf {i}} = \sqrt{-1}$ and $\xi \in [0, 2\pi ]$. Plugging the ansatz into the SL conservative scheme as described in Sect. 2, but with both linear interpolation and linear reconstruction (i.e. the WENO coefficients are frozen to constant values that guarantee maximum accuracy), we obtain $\hat{f}^{n+1}(\xi ) = Q_{\lambda }(\xi ) \hat{f}^n (\xi )$ with $Q_{\lambda }(\xi )$ being the amplification factor for the Fourier mode associated with $\xi$ and $\lambda = \frac{\Delta t}{\Delta x}$. To ensure linear stability, it is sufficient to have

$$\begin{aligned} |Q_\lambda (\xi )|\le 1, \quad \forall \xi \in [0, 2\pi ], \quad \forall \lambda \in [0, \lambda ^\star ], \quad \hbox { for some}\ \lambda ^\star . \end{aligned}$$

(4.1)

We seek for $\lambda ^\star$ by numerically checking the inequality (4.1) for 100 discretized grid points on $\xi \in [0, 2\pi ]$, and by gradually increasing $\lambda$ with a step size of 0.01 starting from $\lambda =0$. Taking the machine precision into account in our implementation, we check the inequality $|Q_\lambda (\xi )|\le 1 + 10^{-11}$ instead. We tabulate such $\lambda ^\star$ in Table 2 for different quadrature formulas as discussed in Sect. 3 and with different choices of spatial interpolation and reconstruction stencils with odd and even order respectively. One can observe that the second order trapezoidal rule and the fourth order GL2 perform much better than the mid-point rule in terms of stability, especially for high order spatial approximations. The time stepping sizes allowed for stability of fully discretized schemes with $s=4, 8, 12$ are observed to be much less than the one provided by ODE stability analysis in the previous section. The reason for this behavior is not clear, and a deeper analysis is needed to study the stability of fully discrete schemes, on order to obtain more effective quadrature formulas. Such analysis is however beyond the scope of the present paper and will be subjetc of future investigation.

In the following, we take the linear advection equation $u_t + u_x = 0$ with a smooth initial function $\sin (2\pi x)$ on the domain [0, 1], to test the CFL bounds in Table 2. Here for better illustration, only linear interpolation and linear reconstruction are used (i.e. the WENO weights are frozen to obtain maximum order of accuracy). We consider schemes of coupling GL2 for temporal integration with third or fourth order spatial approximations. Errors and orders of convergence at a final integration time $T=100.1$ for the 3rd order and $T=1001.1$ for the 4th order are recorded in Table 3. Clear third order and fourth order spatial accuracies are observed at the corresponding upper bounds for CFL (1.22 for 3rd order and 1.84 for 4th order as in Table 2.) The code will blow up with the CFL increased by 0.01 at the corresponding time, which confirms the validity of the CFL bounds in the table. We have similar observations for schemes of higher order, but omitting them to save space. Although even order schemes comparatively have larger CFL bounds than odd order ones, for solutions with discontinuities, we can observe that odd order schemes with upwind mechanism can resolve the discontinuities better, see Fig. 5 for the numerical solutions of our schemes with linear weights for advecting a step function. Due to the above considerations, we will only consider the scheme with 5th order spatial approximation and GL2 for temporal integration in the following numerical sections. We would mention that the numerical oscillations for discontinuous solutions due to a linear scheme can be well controlled by only using WENO in the reconstruction step, not in the interpolation, see Fig. 5 for 5th order linear interpolation with 5th order WENO reconstruction, and also the tests in the numerical section.

Table 2 Upper bounds of CFL for FD SL scheme with odd and even order interpolation and reconstruction

Table 3 Accuracy test of the linear advection equation $u_t + u_x = 0$ with the initial function $\sin (2\pi x)$ for the 3rd order scheme with $\mathrm {CFL}=1.22$ at $T=100.1$ and 4th order with $\mathrm {CFL}=1.84$ at $T=1001.1$

Fig. 5

Numerical solution for the linear advection equation $u_t + u_x = 0$ with an initial step function at $T=100.1$. Left: 3rd order with $\mathrm {CFL}=1.22$ and 5th order with $\mathrm {CFL}=1.19$; Right: 4th order and 6th order with $\mathrm {CFL}=1.84$. $N=800$. Here “weno5” means 5th order linear interpolation with 5th order WENO reconstruction, while others all using linear interpolation with linear reconstruction in corresponding orders

5 Numerical Tests on 2D Linear Passive-Transport Problems

In this section, the conservative truly multi-dimensional SL scheme will be tested for passive transport equations, such as linear advection, rotation and swirling deformation. Since the velocity of the field is given a priori, characteristics can be traced by a high order RK ODE integrator.

In this and next sections, we use 5th order spatial approximations with linear interpolation and WENO reconstruction for evaluating flux functions in (2.4). We use GL2 for temporal integration, while characteristics are traced back in time by RK to locate feet of characteristics. For a general two dimensional problem $u_t+f(u)_x + g(u)_y = 0$, the time step is taken as

$$\begin{aligned} \Delta t = {\mathrm{CFL}}/(a/\Delta x+b/\Delta y), \end{aligned}$$

where $a=\max |f'(u)|$ and $b=\max |g'(u)|$. From Table 2, the maximum CFL number allowed by stability is 1.22 for a 3rd order spatial discretization and 1.19 for the 5th order. In the following, we take ${\mathrm{CFL}}=1.15$ without specification.

Example 5.1

We first test our problem for the linear equation $u_t+u_x+u_y=0$ with initial condition $u(x,y,0)=\sin (x)\sin (y)$. The exact solution is $u(x,y,t)=\sin (x-t)\sin (y-t)$. For this example, the roots of characteristics are located exactly. Tables 4 and 5 present spatial and temporal orders of convergence of the proposed scheme. Both 5th order spatial accuracy and 4th order temporal accuracy from GL2 can be observed.

Table 4 Errors and orders for the linear equation in space

Table 5 Errors and orders for the linear equation in time

Example 5.2

Now we consider two problems defined on the domain $[-\pi ,\pi ]^2$. One is the rigid body rotating problem

$$\begin{aligned} u_t - y u_x + x u_y =0, \end{aligned}$$

the other is the swirling deformation flow problem

$$\begin{aligned} u_t - \left( \cos ^2\left( \frac{x}{2}\right) \sin (y)g(t)u\right) _x + \left( \sin (x)\cos ^2\left( \frac{y}{2}\right) g(t)u\right) _y = 0, \end{aligned}$$

with $g(t)=\cos (\pi t/T)\pi$. Both have the initial condition, which includes a slotted disk, a cone as well as a smooth hump, see Figs. 6 (top left) and 7 (top left). To trace characteristics backward in time in the SL framework, we use a fourth order Runge-Kutta method in solving final value problems.

For the rigid body rotating problem, its period is $2\pi$. In left panels of Fig. 6, we have shown the results at a half period and one period. As we can see, the shape of the bodies are well preserved. For the swirling deformation flow problem, after a half period the bodies are deformed; and they regain its initial shape after one period, see left panels in Fig. 7. On right panels, 1D cuts of numerical solutions are shown, benchmarked with the exact reference solutions.

Fig. 6

Rigid body rotating problem. Mesh size: $128\times 128$. Left: from top to bottom, time at $T=0, \pi , 2\pi$ respectively. Right: from top to bottom, cuts at $T=2\pi$ along $x=0$, $y=\pi /4$ and $y=-5\pi /8$

Fig. 7

Swirling deformation flow problem. Mesh size: $128\times 128$. Left: from top to bottom, time at $T=0, 0.75, 1.5$ respectively. Right: from top to bottom, cuts at $T=1.5$ along $x=0, y=\pi /4$ and $y=-5\pi /8$

6 Numerical Tests of Nonlinear Systems

In this section, we test the conservative SL scheme, which is denoted as “Cons-SL”, on the nonlinear VP system, the guiding center Vlasov system and the incompressible Euler system in vorticity-stream function formulation. Despite different application backgrounds, the latter two systems have indeed almost the same mathematical formulation, only with different signs in the Poisson’s equation.

We will compare our conservative scheme to the nonconservative one [17], which is denoted as “NonCons-SL”. For the nonconservative scheme “NonCons-SL”, we take 6th order spatial reconstruction, which is 5th order accurate in space globally, and $\mathrm{CFL}=1.15$ the same as the conservative scheme.

6.1 Vlasov–Poisson System

Arising from collisionless plasma applications, the rescaled VP system [4, 8, 25] writes

$$\begin{aligned} \frac{\partial f}{\partial t} + \mathbf{v} \cdot \nabla _\mathbf{x} f + {\mathbf {E}}(\mathbf{x},t) \cdot \nabla _\mathbf{v} f = 0, \end{aligned}$$

(6.1)

where

$$\begin{aligned} {\mathbf {E}}({\mathbf {x}},t)=-\nabla _\mathbf{x}\phi ({\mathbf {x}},t).\quad -\Delta _\mathbf{x}\phi ({\mathbf {x}},t)=\rho ({\mathbf {x}},t)-1. \end{aligned}$$

(6.2)

The system describes the temporal evolution of the particle distribution function in six dimensional phase space. $f( \mathbf{x},\mathbf{v},t)$ is the probability distribution function which describes the phase space density of charged particles with velocity $\mathbf {v}$ at position $\mathbf {x}$ at time t, $\mathbf {E}$ is the electric field, and $\phi$ is the self-consistent electrostatic potential. The probability distribution function couples to the long range fields via the charge density, $\rho (t,\mathbf{x}) = \int _{\mathbb {R}^{d_v}} f(\mathbf{x},\mathbf{v},t)d\mathbf{v}$, where $d_v$ is the dimension in the velocity field, and we take the limit of uniformly distributed infinitely massive ions in the background, whose charge density is assumed to be 1 (with mines sign) appearing in the Poisson equation (6.2). In this paper, we consider the VP system with 1-D in $\mathbf{x}$ and 1-D in $\mathbf{v}$ and simply denote as (x, v) the coordinates in the phase space. Periodic boundary condition is imposed in the x-direction, while zero boundary condition is imposed in v-direction. The equations for tracking characteristics are

$$\begin{aligned} \frac{dx}{dt} = v, \quad \frac{dv}{dt} = E, \end{aligned}$$

(6.3)

where the electric field E is now a scalar function and nonlinearly depends on f via the Poisson system (6.2). To locate the foot of characteristics accurately, we apply the high order procedure proposed in [18].

Next we recall several norms in the VP system below, which should remain constant in time [10].

• 1. Mass:

  $$\begin{aligned} \text {Mass}=\int _v\int _xf(x,v,t)dxdv. \end{aligned}$$

• 2. $L^p$ norm $1\le p<\infty$:

  $$\begin{aligned} \Vert f\Vert _p=\left( \int _v\int _x|f(x,v,t)|^pdxdv\right) ^\frac{1}{p}. \end{aligned}$$

  (6.4)

• 3. Energy:

  $$\begin{aligned} \text {Energy}=\frac{1}{2}\int _v\int _xf(x,v,t)v^2dxdv + \int _xE^2(x,t)dx, \end{aligned}$$

  (6.5)

  where E(x, t) is the electric field.

• 4. Entropy:

  $$\begin{aligned} \text {Entropy}=\int _v\int _xf(x,v,t)\log (f(x,v,t))dxdv. \end{aligned}$$

  (6.6)

Tracking relative deviations of these quantities numerically will be a good measure of the quality of numerical schemes. The relative deviation is defined to be the deviation away from the corresponding initial value divided by the magnitude of the initial value. We also check the mass conservation over time $\int _v\int _x f(x,v,t)dxdv$, which is the same as the $L^1$ norm if f is positive. However, since our scheme is not positivity preserving, the time evolution of the mass could be different from that of the $L^1$ norm due to the negative values appearing in numerical solutions.

In our numerical tests, we let the time step size

$$\begin{aligned} \Delta t = {\mathrm{CFL}}\, \min (\Delta x/v_{max}, \Delta v/\max (E)), \end{aligned}$$

where CFL is specified as 1.15, and let $v_{max} = 2\pi$ to minimize the error from truncating the domain in v-direction. The spatial domain will be [0, L], where $L=\frac{2\pi }{k}$ with k being the wave number appeared in the initial condition specified in the examples. In all examples, we compare performance of conservative and non-conservative schemes, using the same set of computational mesh, by comparing the evolution of relative deviations of norms mentioned above.

Example 6.1

(Weak Landau damping) For the VP system, we first consider the weak Landau damping with the initial condition:

$$\begin{aligned} f(t=0,x,v)=\frac{1}{\sqrt{2\pi }}\left( 1+\alpha \cos (k x)\right) \exp \left( -\frac{v^2}{2}\right) , \end{aligned}$$

(6.7)

where $\alpha =0.01$ and $k=0.5$. The length of the domain in the x-direction is $L=\frac{2\pi }{k}=4\pi$.

We take mesh size $128\times 128$. In Fig. 8 (top left), we plot the time evolution of the electric field E in $L^2$ norm and $L^\infty$ norm. The results are comparable to those in [17]. The relative derivation of mass, the discrete $L^1$ norm and $L^2$ norm, kinetic energy and entropy are plotted in Fig. 9, and are compared to the results from the nonconservative scheme [17]. The mass and $L^1$ norm will be the same when the distribution function f(t, x, v) is alway positive, otherwise they are different. We can observe that the conservative scheme “Cons-SL” preserves the mass exactly and also the $L^1$ norm, which is much better than the nonconservative scheme “NonCons-SL”. For the $L^2$ norm, energy and entropy, “Cons-SL” also preserves them better than “NonCons-SL”.

Fig. 8

Time evolution of the electric field in $L^2$ norm and $L^\infty$ norm. Mesh: $128 \times 128$. Top left: weak Landau damping; top right: strong Landau damping; bottom left: two stream instability; bottom right: symmetric two stream instability

Fig. 9

Preservation of conserved quantities for weak Landau damping. Mesh: $128\times 128$

Example 6.2

(Strong Landau damping) The initial condition of strong Landau damping is (6.7), with $\alpha =0.5$ and $k=0.5$. Similarly we take mesh $128\times 128$ and in Fig. 8 (top right), we plot the time evolution of the electric field in $L^2$ norm and $L^\infty$ norm for “Cons-SL”. In Fig. 10, we compare the relative derivation of mass, the discrete $L^1$ norm and $L^2$ norm, kinetic energy and entropy of “Cons-SL” and “NonCons-SL” schemes. Except entropy, “Cons-SL” preserves those quantities better than “NonCons-SL”.

We also use this example to show the spatial and temporal accuracies of the conservative scheme proposed in this paper. In Tables 6 and 7, we can observe 5th order spatial accuracy and almost 4th order temporal accuracy respectively. Here the errors are computed by comparing to a reference solution on the mesh size $256\times 256$ with ${\mathrm{CFL}}=0.01$. In order to measure the temporal accuracy, 9th order linear interpolation and 9th order linear reconstructions are used. As we can see that the temporal accuracy is almost one order higher than expected, that is we use a third order scheme in tracking characteristics proposed in [18] and observe higher than third order convergence in the table. Such phenomenon does not appear in the nonconservative case [18], which might be due to some special cancellation in the flux difference form.

Fig. 10

Preservation of conserved quantities for strong Landau damping. Mesh: $128\times 128$

Example 6.3

(Two stream instability) Now we consider the two stream instability problem, with an unstable initial distribution function given by:

$$\begin{aligned} f(t=0,x,v)= & {} \frac{2}{7\sqrt{2\pi }}(1+5v^2)(1+\alpha ((\cos (2kx)+\cos (3kx))/1.2\nonumber \\&+\cos (kx))\exp \left( -\frac{v^2}{2}\right) \end{aligned}$$

(6.8)

where $\alpha =0.01$ and $k=0.5$. We show the time evolution of electric field in $L^2$ norm and $L^\infty$ norm in Fig. 8 (bottom left) with a mesh of $128\times 128$. We plot the numerical solution at $T=53$ in Fig. 12 (left) with a mesh of $256\times 256$. The results are comparable to those in [17]. The relative derivation of mass, the discrete $L^1$ norm and $L^2$ norm, kinetic energy and entropy, as compared to the nonconservative scheme, are shown in Fig. 11. “Cons-SL” preserves those quantities better than “NonCons-SL”. Better performances in preserving norms are observed for “Cons-SL”.

Table 6 Errors and orders for strong Landau damping in Example 6.2

Table 7 Errors and orders for strong Landau damping in Example 6.2

Fig. 11

Preservation of conserved quantities for two stream instability with the initial data (6.8). Mesh: $128\times 128$

Example 6.4

(Symmetric two stream instability) We consider the symmetric two stream instability with the initial condition:

$$\begin{aligned} f(t=0,x,v)=\frac{1}{2v_{th}\sqrt{2\pi }}\left[ \exp \left( -\frac{(v-u)^2}{2v_{th}^2}\right) +\exp \left( -\frac{(v+u)^2}{2v_{th}^2}\right) \right] (1+\alpha \cos (kx)) \end{aligned}$$

(6.9)

with $\alpha =0.05$, $u=0.99$, $v_{th}=0.3$, $k=\frac{2}{13}$ and $L=13\pi$. The time evolution of the electric field in $L^2$ norm and $L^\infty$ norm are shown in Fig. 8 (bottom right). We plot the numerical solution with mesh size $256\times 256$ at $T=70$ in Fig. 12 (right). These results are similar to those in [17]. The relative derivation of mass, the discrete $L^1$ norm and $L^2$ norm, kinetic energy and entropy, comparing ‘Cons-SL” and “NonCons-SL”, are reported in Fig. 13. As observed in previous examples, “Cons-SL” preserves these quantities better than “NonCons-SL”.

Fig. 12

Left: two stream instability at $T=53$, mesh: $256\times 256$. Right: symmetric two stream instability at $T=70$, mesh: $256 \times 256$

Fig. 13

Preservation of conserved quantities for symmetric two stream instability. Mesh: $128\times 128$

6.2 The Guiding Center Vlasov Model

The guiding center model is an approximation of the 2D Vlasov model [9, 30] under a strong constant external magnetic field, which can be written as

$$\begin{aligned} \frac{\partial \rho }{\partial t} + E_2 \frac{\partial \rho }{\partial x} - E_1 \frac{\partial \rho }{\partial y} =0, \end{aligned}$$

(6.10)

or equivalently in a conservative form as

$$\begin{aligned} \frac{\partial }{\partial t} \rho + \frac{\partial }{\partial x} (\rho E_2)+ \frac{\partial }{\partial y}(-\rho E_1) =0, \end{aligned}$$

(6.11)

where $\mathbf{E} = (E_1, E_2) = -\nabla \Phi$ with $\Phi$ determined from the Poisson’s equation

$$\begin{aligned} \bigtriangleup \Phi = -\rho . \end{aligned}$$

It is well-known that the mass, energy and entropy are preserved over time in the PDE level.

• 1. Mass:

  $$\begin{aligned} \text {Mass}=\int _y\int _x \rho (x, y, t)dxdy. \end{aligned}$$

  (6.12)

• 2. Energy:

  $$\begin{aligned} \Vert \mathbf{E}\Vert _2^2=\int _y\int _x \Vert \mathbf{E}\Vert ^2dxdy. \end{aligned}$$

  (6.13)

• 3. Entropy:

  $$\begin{aligned} \Vert \rho \Vert _2^2=\int _y\int _x |\rho (x, y, t)|^2 dxdy. \end{aligned}$$

  (6.14)

Tracking relative deviations of these quantities numerically will be a good measure of the quality of numerical schemes. In a SL framework, we adopt a third order high order characteristic tracing scheme as proposed in our recent work [28]. For this problem, the time step size is taken as

$$\begin{aligned} \Delta t = {\mathrm{CFL}}\, \min (\Delta x/\max (E_2), \Delta y/\max (E_1)), \end{aligned}$$

with CFL specified as 1.15.

Example 6.5

(Kelvin–Helmholtz instability problem) This example is the 2-D guiding center model problem with the initial condition

$$\begin{aligned} \rho _0(x,y)=\sin (y)+0.015\cos (kx) \end{aligned}$$

(6.15)

and periodic boundary conditions on the domain $[0,4\pi ]\times [0,2\pi ]$. We let $k=0.5$, which creates a Kelvin–Helmholtz instability [22].

For this example, we take mesh size $256\times 256$ and show the surface of the solution at $T=20$ and 40 in Fig. 14; the solution profiles are comparable to those previously presented in other papers [9, 28]. Then we take mesh size $128\times 128$ and show the relative derivation of mass, energy $\Vert \mathbf{E}\Vert _2^2$ and entropy $\Vert \rho \Vert _2^2$ in Fig. 15. We compare them to the nonconservative scheme [28] with 6th order space reconstruction and $\mathrm{CFL}=1.15$. For this example, “Cons-SL” has exact mass conservation, while “NonCons-SL” does not. For the energy and entropy, “NonCons-SL” seems to perform a little better.

Fig. 14

Kelvin–Helmholtz instability problem. Mesh: $256\times 256$. $T=20$ (left), $T=40$ (right)

Fig. 15

Preservation of conserved quantities for Kelvin–Helmholtz instability problem. Mesh: $128\times 128$

6.3 Incompressible Euler Equation

The incompressible Euler equations in the vorticity-stream function formulation in two space dimensions reads

$$\begin{aligned} \omega _{t}+\nabla \cdot ({\mathbf {u}}\,\omega )=0, \quad \Delta \psi =\omega , \quad {\mathbf {u}}=\left( -\frac{\partial \psi }{\partial y},\frac{\partial \psi }{\partial x}\right) , \end{aligned}$$

(6.16)

where $\mathbf{u}=(u_1, u_2)$ is the velocity vector, $\omega = \frac{\partial u_2}{\partial x}-\frac{\partial u_1}{\partial y}$ is the vorticity and $\psi$ is a stream function. The form is almost equivalent as the guiding center Vlasov model, up to a sign difference for the field equation [28]. The conservation of mass, energy and entropy shown in Eqs. (6.12)–(6.14) is the same as the guiding center model. We use the third order characteristics tracing scheme, similar to that in the guiding center model, as presented in our previous work [28]. Similar to the guiding center problem, the time step size is taken as

$$\begin{aligned} \Delta t = {\mathrm{CFL}}\, \min (\Delta x/\max (u_1), \Delta y/\max (u_2)), \end{aligned}$$

with CFL to be 1.15.

Example 6.6

We first consider the incompressible Euler system on the domain $[0, 2\pi ]\times [0,2\pi ]$ with an initial condition $\omega _0(x,y)=-2\sin (x)\sin (y)$. The exact solution will stay stationary with $\omega (x,y,t)=-2\sin (x)\sin (y)$. Similarly as in Tables 6 and 7, the 5th order spatial accuracy and 4th order temporal accuracy are clearly observed in Tables 8 and 9 respectively. Here in Table 9, in order to measure the temporal convergence, we use a 9th order linear interpolation and 9th order linear reconstruction in space to minimize errors from spatial approximations.

Table 8 Errors and orders for the incompressible Euler equation in Example 6.6

Table 9 Errors and orders for the incompressible Euler equation in Example 6.6

Fig. 16

Vortex patch problem. Mesh: $256\times 256$. $T=5$ (left) and $T=10$ (right)

Fig. 17

Preservation of conserved quantities for the incompressible flow system. Mesh: $128\times 128$. Left: vortex patch; right: shear flow

Fig. 18

Shear flow problem. Mesh: $256\times 256$. $T=6$ (left) and $T=8$ (right)

Example 6.7

(The vortex patch problem) In this example, we consider the incompressible Euler equations with the initial condition given by

$$\begin{aligned} \omega _0(x,y)= {\left\{ \begin{array}{ll} \displaystyle -1, \qquad &{} \frac{\pi }{2} \le x \le \frac{3\pi }{2}, \frac{\pi }{4}\le y \le \frac{3\pi }{4}; \\ \displaystyle 1, \qquad &{} \frac{\pi }{2} \le x \le \frac{3\pi }{2}, \frac{5\pi }{4} \le y \le \frac{7\pi }{4}; \\ \displaystyle 0, \qquad &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

(6.17)

We show the surface of $\omega$ at $T=5$ and 10 in Fig. 16. The mesh size is $256 \times 256$. The results are similar to those in [19]. Then we take mesh size $128\times 128$ and show the relative derivation of mass, energy $\Vert \mathbf{E}\Vert _2^2$ and entropy $\Vert \rho \Vert ^2_2$ in Fig. 15 (left). We compare them to the nonconservative scheme [28] with 6th space reconstruction and $CFL=1.15$. “Cons-SL” has exact mass conservation, while “NonCons-SL” does not. For the energy and entropy, “Cons-SL” performs better than “NonCons-SL”.

Example 6.8

(Shear flow problem) This example is the same as above but with following initial conditions (Fig. 17)

$$\begin{aligned} \omega _0(x,y)= {\left\{ \begin{array}{ll} \displaystyle \delta \cos (x)-\frac{1}{\rho }\mathrm{sech}^2((y-\pi /2)/\rho )^2, \qquad &{}y\le \pi ; \\ \displaystyle \delta \cos (x)+\frac{1}{\rho }\mathrm{sech}^2((3\pi /2-y)/\rho )^2,\qquad &{} y>\pi . \end{array}\right. } \end{aligned}$$

(6.18)

where $\delta =0.05$ and $\rho =\frac{\pi }{15}$. We show the surface of $\omega$ at $T=6$ and 8 in Fig. 18. The mesh size is $256\times 256$. The results are also similar to those in [19], which can also show our multi-dimensional non-splitting conservative scheme can perform well. Then we take mesh size $128\times 128$ and show the relative deviation of mass, energy $\Vert \mathbf{E}\Vert _2^2$ and entropy $\Vert \rho \Vert _2^2$ in Fig. 15 (right). We compare them to the nonconservative scheme. Similar to the vortex patch problem, “Cons-SL” has exact mass conservation, while “NonCons-SL” does not. For the energy and entropy conservation, “Cons-SL” performs better than “NonCons-SL”.

7 Conclusion

In this paper, we propose a mass conservative semi-Lagrangian finite difference WENO scheme based on a flux difference formulation. We investigate its numerical stability from the linear ODE and PDE point of view via Fourier analysis. The upper bound of time step constraints have been found in the linear setting and have been numerically verified. These upper bounds are only slightly greater than those from the Eulerian approach, unfortunately. The schemes are applied to passive transport problems as well as nonlinear Vlasov systems and the incompressible Euler system to showcase its effectiveness. The properties of the schemes are verified numerically. In several circumstances the conservative scheme provides more accurate solutions than the corresponding non conservative counterpart with the same discretization parameters. The development of conservative, large time step, multi-dimensional semi-Lagrangian scheme is currently under investigation. If one is interested in using semi-Lagrangian schemes with mass conservation, and with stability for large CFL numbers, the discontinuous Galerkin method would be a good framework to use [1, 2].