A high-order relaxation method with projective integration for solving nonlinear systems of hyperbolic conservation laws

https://doi.org/10.1016/j.jcp.2017.03.027Get rights and content

Abstract

We present a general, high-order, fully explicit relaxation scheme which can be applied to any system of nonlinear hyperbolic conservation laws in multiple dimensions. The scheme consists of two steps. In a first (relaxation) step, the nonlinear hyperbolic conservation law is approximated by a kinetic equation with stiff BGK source term. Then, this kinetic equation is integrated in time using a projective integration method. After taking a few small (inner) steps with a simple, explicit method (such as direct forward Euler) to damp out the stiff components of the solution, the time derivative is estimated and used in an (outer) Runge–Kutta method of arbitrary order. We show that, with an appropriate choice of inner step size, the time step restriction on the outer time step is similar to the CFL condition for the hyperbolic conservation law. Moreover, the number of inner time steps is also independent of the stiffness of the BGK source term. We discuss stability and consistency, and illustrate with numerical results (linear advection, Burgers' equation and the shallow water and Euler equations) in one and two spatial dimensions.

Introduction

Hyperbolic conservation laws arise in numerous physical applications, such as fluid dynamics, plasma physics, traffic modeling and electromagnetism (see, for instance, [26], [37]). They express the conservation of physical quantities (such as mass, momentum, or energy) and may be supplemented with boundary conditions that control influx or outflux at the boundaries of the physical domain [26]. In this paper, we consider a system of hyperbolic conservation laws in multiple spatial dimensions:tu+xF(u)=0, or, equivalently,tu+d=1DxdFd(u)=0, in which x=(xd)d=1dRD represents the space variables (D being the number of spatial dimensions), u(x,t):=(um(x,t))m=1mRM denotes the conserved quantities, and F(u)RM×D corresponds to the flux functions.

Hyperbolic conservation laws are often solved using a finite volume method [26], [29], which is derived from the integral expression of the conservation law. To that end, in a scalar, one-dimensional setting and with a spatially uniform grid, the domain is divided in I cells Ci=[xi1/2,xi+1/2] with constant cell width Δx over which the cell average of the solution u(x,t) to the conservation lawtu+xF(u)=0, is approximated at time t=tn byUin1ΔxCiu(x,tn)dx. Note that boldface is removed whenever the quantities are scalar. A numerical scheme is then constructed by integrating the conservation law (3) in space over the cell Ci and in time from tn to tn+1 to obtainUin+1=UinΔtΔx(Fi+1/2nFi1/2n), in which Δt=tn+1tn and the numerical flux satisfiesFi±1/2n1Δttntn+1F(u(xi±1/2,t))dt. Clearly, equation (5) is conservative by construction. The numerical fluxes Fi±1/2n can be obtained by constructing an (approximate) Riemann solver, based on a (possibly high-order) reconstruction of the solution in each of the cells using interpolation over the neighboring cells [26], [32]. However, in the general nonlinear case, these spatial discretizations require the (possibly tedious) computation of the solutions of local Riemann problems.

Relaxation methods offer an interesting alternative in which the nonlinear hyperbolic conservation law is replaced by a linear transport equation with a stiff nonlinear (but local) source term, see, for instance, discrete kinetic schemes in [18], [19], [27] and, in particular, [1] which also contains a brief historical overview. In a relaxation method, the conservation law (1) is approximated by a problem of higher dimension containing a small relaxation parameter ε such that, when ε tends to zero, the original problem is recovered. In this paper, we will consider the relaxation problem to be a kinetic BGK equation. In a scalar one-dimensional setting, this equation describes the evolution of a distribution function fε(x,v,t) of particles at position x with velocity v at time t and takes the following form:tfε+vxfε=1ε(Mv(uε)fε). The left hand side of equation (7) describes the transport of particles, whereas the right hand side represents collisions between particles, which is modeled as a linear relaxation to the Maxwellian Mv(uε) with a relaxation time ε. The idea is that some of the difficulties associated with the original problem are avoided, while, for sufficiently small ε, the relaxation problem is a good approximation of the problem of interest. In particular, the advantage of the kinetic equation (7) over the conservation law (3) is the fact that the advection term in (7) is now linear, removing the difficulties associated with the high-order discretization of a nonlinear flux term. The disadvantage is the appearance of a stiff source term, which requires special care during time integration. The first methods, proposed in [1], [19] are based on splitting techniques. As a consequence, the order in time is restricted to 2 and can only be improved by nontrivial manipulations, see [9]. More recently, several asymptotic-preserving methods based on IMEX techniques (in the sense of Jin [17]) have been proposed. An appealing idea along this line of thought, based on IMEX Runge–Kutta methods, is presented in [5], [6] for general hyperbolic systems with relaxation. We refer to [10], [14] for specific methods for the Boltzmann equation in the hyperbolic and diffusive regimes with a computational cost that is independent of ε. We note that the principle of a kinetic relaxation scheme also bears resemblance to the method of transport [13], see also [38].

In this paper, we propose to use a projective integration method to solve the stiff relaxation systems with an arbitrary order of accuracy in time. We will show that the resulting scheme constitutes a flexible, robust and fully explicit alternative to splitting and IMEX methods, while avoiding the construction of complicated and problem-specific (approximate) Riemann solvers. Projective integration methods were proposed in [15] for stiff systems of ordinary differential equations and analyzed in [23] for kinetic equations with a diffusive scaling. An arbitrary order version, based on Runge–Kutta methods, has been proposed recently in [22], where it was also analyzed for kinetic equations with an advection–diffusion limit. Projective integration is particularly suited for stiff problems with a clear spectral gap. In such stiff problems, the fast modes, corresponding to the Jacobian eigenvalues with large negative real parts, decay quickly, whereas the slow modes correspond to eigenvalues of smaller magnitude and are the solution components of practical interest. Projective integration allows a stable yet explicit integration of such problems by first taking a few small (inner) steps with a simple, explicit method, until the transients corresponding to the fast modes have died out, and subsequently projecting (extrapolating) the solution forward in time over a large (outer) time step. Besides being robust and fully explicit, the resulting projective integration relaxation method is very appealing for nonlinear hyperbolic conservation laws because of its flexibility: once a solver is available, applying it to a different nonlinear hyperbolic conservation law merely amounts to changing the definition of the Maxwellian function Mv(u) in equation (7), leaving both the space and time discretizations untouched.

Projective integration fits within recent research efforts on numerical methods for multiscale simulation [11], [20], [21]. In this context, projective integration is a useful technique to effectively deal with problems in which there is a macroscopic (slow) dynamics whose mathematical formulation is not known and that can be captured “on-the-fly” by a short (appropriately initialized) microscopic simulation. Then, a few small steps of the full microscopic dynamics are combined with an extrapolation of the macroscopic, slow degrees of freedom only, and the resulting method is called coarse projective integration. Examples are, amongst others, bacterial chemotaxis [31], chemical reactions [30] and disease modeling [8]. For more examples, we refer to [21]. To conclude, we also mention alternative approaches to obtain a higher-order projective integration scheme which have been proposed in [24], [30]; see also [12], [34], [35] for related work.

The remainder of this paper is structured as follows. In section 2, we introduce the kinetic equations that form the basis of the relaxation method, and discuss their asymptotic equivalence with the original hyperbolic problem. In section 3, we describe the projective integration method that will be used to integrate these kinetic equations. We then analyze convergence of the resulting projective integration relaxation method for hyperbolic conservation laws in section 4, including the choice of appropriate method parameters. This analysis is based on the results in [22], for which we provide a number of alternative, simplified proofs that are specific for the relaxation systems of section 2. Section 5 reports the results of extensive numerical tests for a set of benchmark problems in both one and two space dimensions: linear advection, nonlinear conservation, the dam-break problem and Sod's shock test. We conclude in section 6 with a brief discussion and some ideas for future work.

Section snippets

Kinetic equation and hydrodynamic limit

To solve equation (1), we introduce, as in [1], the (hyperbolically scaled) kinetic equation:tfε+vxfε=1ε(Mv(uε)fε), or, equivalently,tfε+d=1Dvdxdfε=1ε(Mv(uε)fε), which models the evolution of a vector of particle distribution functions fε(x,v,t)=(fmε(x,v,t))m=1MRM with particle positions xRD and velocities vVRD. The right hand side of (9) contains the BGK relaxation operator [3] that describes linear relaxation of fε to a Maxwellian equilibrium Mv(uε)RM, in which the argument uε(x,t

Projective integration

In this section, we construct a fully explicit, asymptotic-preserving, arbitrary order time integration method for the stiff system (16). The asymptotic-preserving property [17] implies that, in the limit when ε tends to zero, an ε-independent time step constraint, of the form Δt=O(Δx), can be used, in agreement with the classical hyperbolic CFL constraint for the limiting equation (12). To achieve this, we will use a projective integration method [15], [23], which combines a few small time

Numerical properties

Now we are ready to use the projective integration method on the relaxation system (35). The parameters to determine are then the time scale separation parameter ε in the relaxation system (35), as well as the projective integration parameters: the inner time step δt, the outer time step Δt and the number of inner steps K. The projective integration parameters δt, K, and Δt can be determined by imposing that all the eigenvalues of the selected inner integrator scheme fall into the stability

Applications

In this section, we illustrate the relaxation method with projective integration on a number of example systems. We first examine the one-dimensional case. In section 5.1, we consider the linear advection equation, and demonstrate the spatial and temporal order of the methods. Subsequently, we investigate nonlinear conservation laws: Burgers' equation in section 5.2 and the Euler equations (Sod's shock test) in section 5.3. Afterwards, we consider linear advection, the dam-break problem and the

Conclusions

We presented a general, high-order, fully explicit, relaxation scheme for systems of nonlinear hyperbolic conservation laws in multiple dimensions, by approximating the nonlinear hyperbolic conservation law by a kinetic equation with BGK source term, which is, in turn, discretized and integrated using a projective integration method. After taking a few small (inner) steps with the direct forward Euler method, an estimate of the time derivative is used in an (outer) Runge–Kutta method of

References (38)

  • Sebastiano Boscarino et al.

    Implicit–explicit Runge–Kutta schemes for hyperbolic systems and kinetic equations in the diffusion limit

    SIAM J. Sci. Comput.

    (2013)
  • Sebastiano Boscarino et al.

    On a class of uniformly accurate IMEX Runge–Kutta schemes and applications to hyperbolic systems with relaxation

    SIAM J. Sci. Comput.

    (2009)
  • François Bouchut

    Construction of BGK models with a family of kinetic entropies for a given system of conservation laws

    J. Stat. Phys.

    (1999)
  • Jaime Cisternas et al.

    Equation-free modeling of evolving diseases: coarse-grained computations with individual-based models

    Proc. R. Soc. London A: Math. Phys. Eng. Sci.

    (2004)
  • Giacomo Dimarco et al.

    Asymptotic-preserving implicit–explicit Runge–Kutta methods for nonlinear kinetic equations

    SIAM J. Numer. Anal.

    (2013)
  • E. Weinan et al.

    The heterogeneous multiscale methods

    Commun. Math. Sci.

    (2003)
  • Kenneth Eriksson et al.

    Explicit time-stepping for stiff ODEs

    SIAM J. Sci. Comput.

    (2004)
  • Michael Fey et al.

    The Method of Transport for Nonlinear Systems of Hyperbolic Conservation Laws in Several Space Dimensions

    (1997)
  • C. William Gear et al.

    Projective methods for stiff differential equations: problems with gaps in their eigenvalue spectrum

    SIAM J. Sci. Comput.

    (2003)
  • Cited by (22)

    • Projective and telescopic projective integration for non-linear kinetic mixtures

      2022, Journal of Computational Physics
      Citation Excerpt :

      An arbitrary order version, based on Runge-Kutta methods, has been proposed recently in [39], where it was also analysed for kinetic equations in the advection-diffusion limit. In [40], the scheme was used to construct a explicit, flexible, arbitrary order method for general non-linear hyperbolic conservation laws, based on their relaxation to a kinetic equation. Alternative approaches to obtain higher-order PInt schemes have been proposed in [42,52].

    View all citing articles on Scopus
    View full text