Low-storage implicit/explicit Runge–Kutta schemes for the simulation of stiff high-dimensional ODE systems

Abstract

Implicit/explicit (IMEX) Runge–Kutta (RK) schemes are effective for time-marching ODE systems with both stiff and nonstiff terms on the RHS; such schemes implement an (often A-stable or better) implicit RK scheme for the stiff part of the ODE, which is often linear, and, simultaneously, a (more convenient) explicit RK scheme for the nonstiff part of the ODE, which is often nonlinear. Low-storage RK schemes are especially effective for time-marching high-dimensional ODE discretizations of PDE systems on modern (cache-based) computational hardware, in which memory management is often the most significant computational bottleneck. In this paper, we develop and characterize eight new low-storage implicit/explicit RK schemes which have higher accuracy and better stability properties than the only low-storage implicit/explicit RK scheme available previously, the venerable second-order Crank–Nicolson/Runge–Kutta–Wray (CN/RKW3) algorithm that has dominated the DNS/LES literature for the last 25 years, while requiring similar storage (two, three, or four registers of length N) and comparable floating-point operations per timestep.

Introduction

Although a wide variety of methods have been used for spatial discretization and subgrid-scale modeling in the Direct Numerical Simulation (DNS) and Large Eddy Simulation (LES) of turbulent flows, time marching schemes for such systems have relied, in most cases, on an implicit scheme for the advancement of the stiff terms and an explicit scheme for the advancement of the nonstiff terms. Among these so-called IMEX schemes, an approach that gained favor due to [11] and [12] coupled the (implicit, second-order) Crank–Nicolson (CN) scheme for the stiff terms with the (explicit) second-order Adams–Bashforth (AB2) scheme for the nonstiff terms. This approach was refined in [13], which used the (implicit) CN scheme for the stiff terms, at each RK substep, together with the (explicit) third-order low-storage Runge–Kutta–Wray (RKW3) scheme [22] for the nonstiff terms. This venerable IMEX algorithm, dubbed CN/RKW3, still enjoys extensive use today, and is particularly appealing, as only two registers are required for advancing the ODE in time, though if three registers are used, the number of flops required by the algorithm may be significantly reduced. In high-dimensional discretizations of 3D PDE systems on modern computational hardware, the reduced memory footprint of this time marching algorithm, in its two-register or three-register form, can significantly reduce the execution time of a simulation. However, the CN/RKW3 scheme has the considerable disadvantage of being only second-order accurate, and its implicit part is only A-stable. In recent years, there have been relatively few attempts to refine the CN/RKW3 time-marching scheme for turbulence simulations, perhaps due to a mistaken notion that modifying it to achieve higher order might result in either increased storage requirements, significantly more computation per timestep, or the loss of A stability of the implicit part. It turns out that this is untrue; in fact, there is much to be gained by revising this algorithm.

When using an IMEX scheme, such as those described above, to march the incompressible Navier–Stokes equation, one natural choice is to treat the (linear) diffusion terms as the “stiff terms” and the (nonlinear) convective terms as the “nonstiff terms”. Note that a better choice for discretizations with significant grid clustering implemented in one or more spatial directions, as usually present when simulating wall-bounded turbulent flows, is to treat the diffusion and linearized convection terms with derivatives in the direction of most significant grid clustering (e.g., in the direction normal to the nearest wall) as the “stiff” terms, and the remaining terms as the “nonstiff” terms, as suggested by [1]. Note further that so-called fractional step methods are often combined with such IMEX schemes in order to enforce the incompressibility constraint (see, e.g., [13]). The present paper focuses exclusively on the IMEXRK part of such time-advancement algorithms; various creative choices for which terms to take implicitly at different points in the physical domain of interest, and various methods for implementing fractional step techniques for enforcing exactly the divergence-free constraint, may subsequently be addressed in an identical manner as discussed in [1] and [13], and elsewhere in the literature.

Over the last 30 years, there has been significant development of (full-storage) IMEXRK algorithms. A comprehensive review of this literature is given in [9], and a brief summary of this subject is given in Section 1.1 below, including the general structure of full-storage IMEXRK schemes, their general implementation, conditions on their parameters for second-, third-, and fourth-order accuracy, and characterizations of their stability.

Further, in the years since the development of RKW3 in [22], there has been significant development of alternative low-storage explicit RK schemes; a comprehensive review of this literature is given in [10], and a brief summary of this subject is given in Section 1.2 below, including the extension to implicit RK schemes, the introduction of a general 2-register IMEXRK form, efficient 3-register and 2-register implementations of this form, as well as the introduction of a general 3-register IMEXRK form, and efficient 4-register and 3-register implementations of this form.

We then develop eight new low-storage IMEXRK schemes well suited for turbulent flow simulations, and other computational grand challenge applications, using two, three, or four registers of length N (the dimension of the ODE under consideration). With an eye on the computational cost of their implementation, we focus on schemes with the smallest number of stages possible for a given order, stability, and storage requirement. A comprehensive summary of the schemes developed in this paper is given in Table 1. In short:

• Section 2 presents two second-order, 2-register IMEXRK schemes:

  • the classic 3-stage, A-stable, CN/RKW3 scheme, and

  • a new, $(2,3)$-stage [that is, a scheme with 2 implicit stages and 3 explicit stages], L-stable, strong-stability-preserving scheme, dubbed IMEXRKCB2.

• Section 3 presents five new third-order, 2-register IMEXRK schemes:

  • a $(2,3)$-stage, strongly A-stable scheme, dubbed IMEXRKCB3a,

  • a $(3,4)$-stage, strongly A-stable scheme with ESDIRK implicit part, dubbed IMEXRKCB3b, and

  • three $(3,4)$-stage, L-stable schemes:

    • one with coefficients selected to maximize stability of the ERK part on the negative real axis while being strong stability preserving, dubbed IMEXRKCB3c,

    • one with coefficients selected to be strong stability preserving for the maximum possible timestep, dubbed IMEXRKCB3d, and

    • one with coefficients selected to maximize accuracy of the ERK part, dubbed IMEXRKCB3e.

• Section 4 presents a new third-order, 3-register, 4-stage, L-stable, stage-order-2 scheme dubbed IMEXRKCB3f.

• Section 5 presents a new fourth-order, 3-register, 6-stage, L-stable, stage-order-2 scheme dubbed IMEXRKCB4.

In Section 6, we provide an analysis of the well-known order reduction phenomenon arising during the integration of very stiff ODEs using these IMEXRK schemes. Finally, Section 7 considers the application of all of these low-storage IMEXRK schemes, and some of their full-storage IMEXRK competitors, to a representative test problem in order to compare their computational efficiency.

A comprehensive review of (full-storage) IMEXRK schemes is given by Kennedy, Carpenter, and Lewis [9]. In short, IMEXRK schemes incorporate a coordinated pair of Diagonally Implicit Runge–Kutta (DIRK, with lower-triangular A) and Explicit Runge–Kutta (ERK, with strictly lower-triangular A) schemes, with parameters as summarized in the standard Butcher tableaux

for the time advancement of an ODE of the form

$$\frac{d\mathbf{x}(t)}{dt}=\mathbf{f}(\mathbf{x},t)+\mathbf{g}(\mathbf{x},t),$$

where $\mathbf{f}(\mathbf{x},t)$ represents the stiff part of the RHS [advanced with the DIRK method at left in (1)], and $\mathbf{g}(\mathbf{x},t)$ represents the nonstiff part of the RHS [simultaneously advanced with the ERK method at right in (1)].

If the stiff part of the ODE is linear [that is, if $\mathbf{f}(\mathbf{x},t)=A\mathbf{x}$] then, denoting the efficient solution of $A\mathbf{x}=\mathbf{b}$ as $A^{-1}\mathbf{b}$, a full-storage implementation of the IMEXRK scheme in (1) to advance from $\mathbf{x}={\mathbf{x}}_n$ to $\mathbf{x}={\mathbf{x}}_{n+1}$ proceeds as follows

$$\mathtt{for}k=1:s$$

$$\mathtt{if}k==1,\mathbf{y}=\mathbf{x},\mathtt{else},\mathbf{y}=\mathbf{x}+\sum _{i=1}^{k-1}{a}_{k,i}^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{f}}_i+\sum _{j=1}^{k-1}{a}_{k,j}^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{g}}_j,\mathtt{end}$$

$${\mathbf{f}}_k=A{(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}\mathbf{y}[\text{equivalently},{\mathbf{f}}_k={(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}A\mathbf{y}]$$

$${\mathbf{g}}_k=\mathbf{g}(\mathbf{y}+a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{f}}_k,t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)$$

$$\mathtt{end}$$

$$\mathbf{x}\leftarrow \mathbf{x}+\sum _{i=1}^s{b}_i^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{f}}_i+\sum _{j=1}^s{b}_j^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{g}}_j$$

$$\hat{\mathbf{x}}\leftarrow \hat{\mathbf{x}}+\sum _{i=1}^s{\hat{b}}_i^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{f}}_i+\sum _{j=1}^s{\hat{b}}_j^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{g}}_j$$

Line (3c) above is simply ${\mathbf{f}}_k=\mathbf{f}(\mathbf{z},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)$, where z is the solution of $\mathbf{e}(\mathbf{z})=\mathbf{z}-\mathbf{y}-a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{f}(\mathbf{z},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)=0$ [that is, where $\mathbf{z}=\mathbf{y}+a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{f}(\mathbf{z},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)$], in the special case that $\mathbf{f}(\mathbf{x},t)=A\mathbf{x}$. More generally, if the stiff part $\mathbf{f}(\mathbf{x},t)$ is nonlinear, then line (3c) is replaced by a Newton–Raphson iteration (see [16]) to find the z such that $\mathbf{e}(\mathbf{z})=0$:

$$\begin{array}{cc}\text{Initialize}:\hfill & {\mathbf{z}}_0=\mathbf{y}+a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{f}(\mathbf{y},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)\hfill \\ \text{Iterate}:\hfill & (I-a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t{\frac{\partial \mathbf{f}(\mathbf{x},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)}{\partial \mathbf{x}}|}_{\mathbf{x}={\mathbf{z}}_m})({\mathbf{z}}_{m+1}-{\mathbf{z}}_m)=-{\mathbf{z}}_m+\mathbf{y}+a_{kk}^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{f}({\mathbf{z}}_m,t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)\hfill \\ \text{Upon exit}:\hfill & {\mathbf{f}}_k=\mathbf{f}({\mathbf{z}}_{\text{converged}},t_n+c_k^{\mathrm{IM}}\mathrm{\Delta }t)\hfill \end{array}\}$$

The Jacobian used in this iteration may be computed analytically or approximated numerically. The low-storage IMEXRK algorithms developed in this work may be applied in the linear or nonlinear setting, mutatis mutandis; Sections 1.2.1 General three-register implementation of [2R] IMEXRK schemes, 1.2.2 General two-register implementation of [2R] IMEXRK schemes, 1.2.3 General four-register implementation of [3R] IMEXRK schemes, 1.2.4 General three-register implementation of [3R] IMEXRK schemes provide low-storage pseudocode implementations in the case in which the stiff part of the ODE is linear.

Finally, note that the ${\hat{b}}_i^{\mathrm{IM}}$ and ${\hat{b}}_i^{\mathrm{EX}}$ coefficients in the Butcher tableaux, if provided, are used to form a so-called embedded scheme to advance the solution at each timestep with an order of accuracy reduced by one with respect to the main scheme. Using this embedded scheme, one may estimate the error of the simulation at each timestep, and adjust the stepsize at the next iteration accordingly.

As is well known (see, e.g., [3]), for the DIRK and ERK components in (1), when used in isolation, to be first-order accurate, it is required that

$${\tau }_1^{\mathrm{IM}(1)}=\sum _i{b}_i^{\mathrm{IM}}-1=0{\tau }_1^{\mathrm{EX}(1)}=\sum _i{b}_i^{\mathrm{EX}}-1=0,$$

for these schemes, when used in isolation, to be second-order accurate, it is additionally required that

$${\tau }_1^{\mathrm{IM}(2)}=\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}-1/2=0{\tau }_1^{\mathrm{EX}(2)}=\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}-1/2=0,$$

for these schemes, when used in isolation, to be third-order accurate, it is additionally required that

$${\tau }_1^{\mathrm{IM}(3)}=(1/2)\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}-1/6=0{\tau }_1^{\mathrm{EX}(3)}=(1/2)\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}-1/6=0$$

$${\tau }_2^{\mathrm{IM}(3)}=\sum _{i,j}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{IM}}-1/6=0{\tau }_2^{\mathrm{EX}(3)}=\sum _{i,j}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{EX}}-1/6=0,$$

and for these schemes, when used in isolation, to be fourth-order accurate, it is additionally required that

$${\tau }_1^{\mathrm{IM}(4)}=(1/6)\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}-1/24=0{\tau }_1^{\mathrm{EX}(4)}=(1/6)\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}-1/24=0$$

$${\tau }_2^{\mathrm{IM}(4)}=(1/3)\sum _{i,j}{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{IM}}-1/24=0{\tau }_2^{\mathrm{EX}(4)}=(1/3)\sum _{i,j}{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{EX}}-1/24=0$$

$${\tau }_3^{\mathrm{IM}(4)}=(1/2)\sum _{i,j}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{IM}}{c}_j^{\mathrm{IM}}-1/24=0{\tau }_3^{\mathrm{EX}(4)}=(1/2)\sum _{i,j}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{EX}}{c}_j^{\mathrm{EX}}-1/24=0$$

$${\tau }_4^{\mathrm{IM}(4)}=\sum _{i,j,k}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{IM}}{a}_{jk}^{\mathrm{IM}}{c}_k^{\mathrm{IM}}-1/24=0{\tau }_4^{\mathrm{EX}(4)}=\sum _{i,j,k}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{EX}}{a}_{jk}^{\mathrm{EX}}{c}_k^{\mathrm{EX}}-1/24=0.$$

Recall that, in the scalar case, the exact solution of $x^{\prime }=f(x)+g(x)$ has the following terms:

$$x_{n+1}=x_n+\mathrm{\Delta }t{x}_n^{\prime }+{(\mathrm{\Delta }t)}^2{x}_n^{″}/2!+{(\mathrm{\Delta }t)}^3{x}_n^{‴}/3!+O\left({(\mathrm{\Delta }t)}^4\right)=x_n+\mathrm{\Delta }t{\{f+g\}}_{(x_n,t_n)}+\frac{{(\mathrm{\Delta }t)}^2}{2!}{\{f^{\prime }f+f^{\prime }g+g^{\prime }f+g^{\prime }g\}}_{(x_n,t_n)}+\frac{{(\mathrm{\Delta }t)}^3}{3!}{\{f^{″}ff+2f^{″}fg+f^{″}gg+g^{″}ff+2g^{″}fg+g^{″}gg+f^{\prime }{f}^{\prime }f+f^{\prime }{g}^{\prime }f+g^{\prime }{f}^{\prime }f+g^{\prime }{g}^{\prime }f+f^{\prime }{f}^{\prime }g+f^{\prime }{g}^{\prime }g+g^{\prime }{f}^{\prime }g+g^{\prime }{g}^{\prime }g\}}_{(x_n,t_n)}+O\left({(\mathrm{\Delta }t)}^4\right);$$

note in particular that there are 2 terms at second order and 10 terms at third order that involve both f and g. For the DIRK and ERK components in (1), when used together in an IMEX fashion, to be second-order accurate, it is thus additionally required that

$${\tau }_1^{\mathrm{IMEX}(2)}=\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{EX}}-1/2=0{\tau }_2^{\mathrm{IM}\mathrm{EX}(2)}=\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{IM}}-1/2=0,$$

for these schemes, when used together in an IMEX fashion, to be third-order accurate, it is additionally required that

$${\tau }_1^{\mathrm{IMEX}(3)}=(1/2)\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{EX}}{c}_i^{\mathrm{EX}}-1/6=0{\tau }_2^{\mathrm{IMEX}(3)}=(1/2)\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}-1/6=0$$

$${\tau }_3^{\mathrm{IMEX}(3)}=(1/2)\sum _i{b}_i^{\mathrm{IM}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{EX}}-1/6=0{\tau }_4^{\mathrm{IMEX}(3)}=(1/2)\sum _i{b}_i^{\mathrm{EX}}{c}_i^{\mathrm{IM}}{c}_i^{\mathrm{EX}}-1/6=0$$

$${\tau }_5^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{EX}}-1/6=0{\tau }_6^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{IM}}-1/6=0$$

$${\tau }_7^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{IM}}-1/6=0{\tau }_8^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{EX}}-1/6=0$$

$${\tau }_9^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{IM}}{a}_{ij}^{\mathrm{EX}}{c}_j^{\mathrm{IM}}-1/6=0{\tau }_{10}^{\mathrm{IMEX}(3)}=\sum _{i,j}{b}_i^{\mathrm{EX}}{a}_{ij}^{\mathrm{IM}}{c}_j^{\mathrm{EX}}-1/6=0,$$

and for these schemes, when used together in an IMEX fashion, to be fourth-order accurate, 44 additional constraints are required (see [9]), which for brevity aren't listed here.

The stability of an RK scheme may be characterized by considering the model problem $dx/dt=\lambda x$ and defining $z=\lambda \mathrm{\Delta }t$, $\sigma (z)=x_{n+1}/x_n$, and $\sigma (\infty )\triangleq {\lim }_{|z|\to \infty }\sigma (z)$. The stability function of an RK scheme with Butcher tableau parameters A and b is then given by $\sigma (z)=1+z{\mathbf{b}}^T{(I-zA)}^{-1}\mathbf{1}$, where 1 denotes a vector of ones; the RK scheme is said to be stable for any z such that $|\sigma (z)|\le 1$. Further, considering its application to stiff systems, an RK scheme is said to be

• A-stable if $|\sigma (z)|\le 1$ over the entire LHP of z,

• strongly A-stable if it is A-stable and $|\sigma (\infty )|<1$, and

• L-stable if it is A-stable and $\sigma (\infty )=0$.

The stability of an IMEXRK scheme is a bit more difficult to characterize. Of course, one may start by characterizing the stability of the implicit and explicit parts considered in isolation. To evaluate the stability of the implicit and explicit components of an IMEX scheme working together, we consider the model problem $dx/dt={\lambda }_{f}x+{\lambda }_{g}x$, where the first term on the RHS is handled implicitly, and the second term on the RHS is handled explicitly. Defining $z^{\mathrm{IM}}={\lambda }_f\mathrm{\Delta }t$, $z^{\mathrm{EX}}={\lambda }_g\mathrm{\Delta }t$, and $\sigma (z^{\mathrm{IM}};z^{\mathrm{EX}})=x_{n+1}/x_n$, we may write (see [9])

$$\sigma (z^{\mathrm{IM}};z^{\mathrm{EX}})=\frac{\text{det}[I-z^{\mathrm{IM}}{A}^{\mathrm{IM}}-z^{\mathrm{EX}}{A}^{\mathrm{EX}}+z^{\mathrm{IM}}\mathbf{1}{({\mathbf{b}}^{\mathrm{IM}})}^T+z^{\mathrm{EX}}\mathbf{1}{({\mathbf{b}}^{\mathrm{EX}})}^T]}{\text{det}[I-z^{\mathrm{IM}}{A}^{\mathrm{IM}}]}.$$

We may then characterize the stability of the implicit and explicit parts of an IMEXRK scheme working in concert, when the implicit part of the problem is stiff, by looking at $\sigma (z^{\mathrm{IM}};z^{\mathrm{EX}})$ as $z^{\mathrm{IM}}\to \infty$ for finite $z^{\mathrm{EX}}$.

Consider the 1D hyperbolic PDE

$$\partial u/\partial t=-\partial f(u)/\partial x;$$

denoting by $u_i(t)$ the discretization of $u(x,t)$ on N spatial grid points $x_i$, and by $\mathbf{u}(t)$ a vector containing all of the $u_i(t)$, we write the spatial discretization of this PDE as the ODE

$$d\mathbf{u}/dt=L(\mathbf{u}).$$

If a TVD spatial discretization is used, such as a Godunov or MUSCL scheme with an appropriate flux limiter incorporated (see [14]), then applying a simple Explicit Euler time discretization to (7),

$${\mathbf{u}}^{n+1}={\mathbf{u}}^n+\mathrm{\Delta }tL\left({\mathbf{u}}^n\right),$$

under the appropriate CFL condition on the timestep, $\mathrm{\Delta }t\le \mathrm{\Delta }{t}_{\mathit{CFL}}$, results in a simulation exhibiting a total variation of the discrete solution which does not increase in time, that is,

$$\mathit{TV}\left({\mathbf{u}}^{n+1}\right)\le \mathit{TV}\left({\mathbf{u}}^n\right),\text{where}\mathit{TV}\left({\mathbf{u}}^n\right)=\sum _j|u_{j+1}^n-u_j^n|.$$

Strong-stability preserving (SSP) explicit time-discretization methods (see [17] and [18]) are simply higher-order time discretization methods that conserve this total variation diminishing property with a modified CFL condition on the timestep, $\mathrm{\Delta }t\le c\mathrm{\Delta }{t}_{\mathit{CFL}}$.

In [18] (see also [6]), a condition for an explicit Runge–Kutta scheme to be SSP has been developed. This condition states that if an s-stage explicit Runge–Kutta scheme is written in incremental form, that is,

$${\mathbf{u}}^{(0)}={\mathbf{u}}^n$$

$${\mathbf{u}}^{(i)}=\sum _{j=0}^{i-1}({\alpha }_{ij}{\mathbf{u}}^{(j)}+\mathrm{\Delta }t{\beta }_{ij}\mathbf{L}\left({\mathbf{u}}^{(j)}\right))\text{for}i=1,\dots ,s$$

$${\mathbf{u}}^{n+1}={\mathbf{u}}^{(s)},$$

where all of the ${\alpha }_{ij}\ge 0$, and if the forward Euler method applied to the ODE (7) arising from a TVD spatial discretization of the hyperbolic PDE (6) is strongly stable under the appropriate CFL restriction, then such an explicit Runge–Kutta method is SSP provided that all of the ${\beta }_{ij}\ge 0$ and that the following CFL restriction is fulfilled:

$$\mathrm{\Delta }t\le c\mathrm{\Delta }{t}_{\mathit{CFL}},c=\underset{i,j}{\min }\frac{{\alpha }_{ij}}{{\beta }_{ij}}.$$

In case an explicit scheme is coupled with an implicit scheme, as in an IMEXRK formulation, then, provided the implicit scheme used to integrate the stiff part of the ODE is L-stable, in the stiff limit the time integration scheme becomes the explicit Runge–Kutta scheme, and the order of accuracy of the limiting scheme is greater than or equal to the order of accuracy of the IMEXRK scheme itself. Hence, as stated in [15], if the explicit part of the IMEXRK scheme is SSP, then the IMEXRK scheme will also be SSP in the stiff limit.

In [15], three full-storage second-order and two full-storage third-order IMEXRK schemes are presented which are SSP in the stiff limit; no other IMEXRK schemes with this SSP property were found in our review of the IMEXRK literature. The present paper derives three new IMEXRK schemes which are SSP in the stiff limit (one which is second-order and two which are third-order); unlike the schemes in [15], the IMEXRK schemes derived here are of the low-storage variety.

The existing literature on low-storage RK schemes to date appears to focus exclusively on explicit schemes. Note that a cavalier implementation of a full-storage ERK scheme [see the explicit part of (3a), (3b), (3c), (3d), (3e), (3f), (3g)] requires storage of the state vector [x], the intermediate vector [y], and s values of the RHS vectors [${\mathbf{g}}_k$]; that is, $s+2$ vectors of length N, where $\mathbf{x}={\mathbf{x}}_{N\times 1}$. We now summarize the two main classes of low-storage ERK schemes,¹ a comprehensive review of which is given in Kennedy, Carpenter, and Lewis [10].

The two-register Williamson class of ERK schemes [20], denoted “$[2N]$” schemes, may be written to advance from $\mathbf{x}={\mathbf{x}}_n$ to $\mathbf{x}={\mathbf{x}}_{n+1}$ as

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathrm{\Delta }\mathbf{x}\leftarrow \mathrm{\Delta }t\mathbf{g}(\mathbf{x},t_n+c_k\mathrm{\Delta }t),\mathtt{else}\hfill \\ \mathrm{\Delta }\mathbf{x}\leftarrow {\alpha }_k\mathrm{\Delta }\mathbf{x}+\mathrm{\Delta }t\mathbf{g}(\mathbf{x},t_n+c_k\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+{\beta }_k\mathrm{\Delta }\mathbf{x}\hfill \\ \mathtt{end}\hfill \end{array}$$

If handled with care, such schemes can often be implemented efficiently in two registers of length N, x and $\mathrm{\Delta }\mathbf{x}$.

The two-register van der Houwen class of schemes [19], denoted “[2R]” schemes, restrict the parameters $a_{ij}$ below the first subdiagonal in the Butcher tableau of the ERK scheme to be equal to the parameters $b_j$ of the corresponding column, and may thus be written to advance from $\mathbf{x}={\mathbf{x}}_n$ to $\mathbf{x}={\mathbf{x}}_{n+1}$ as

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},\mathtt{else}\hfill \\ \mathbf{y}\leftarrow \mathbf{x}+(a_{k,k-1}-b_{k-1})\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_k\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \end{array}$$

Such schemes can often be implemented efficiently in two registers of length N (namely, x and y). If implemented with three registers, however, the function $\mathbf{g}(\mathbf{y},t_n+c_k\mathrm{\Delta }t)$ can be computed just once per timestep (instead of twice). RKW3 [22] is a commonly-used example of a two-register, three-stage, third-order van der Houwen ERK scheme, with a Butcher tableau of

In the three-register van der Houwen class of schemes, denoted “[3R]” schemes, only the parameters $a_{ij}$ below the second subdiagonal of the Butcher tableau of the ERK scheme must equal the parameters $b_j$ of the corresponding column. An effective implementation of such [3R] schemes that uses only three registers of length N (namely, x, y and z) is given by

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},\mathbf{z}\leftarrow \mathbf{x},\mathtt{else},\hfill \\ \mathbf{z}\leftarrow \mathbf{y}+a_{k,k-1}\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}\mathrm{\Delta }t)\hfill \\ \mathtt{if}k<s,\mathbf{y}\leftarrow \mathbf{x}+(a_{k+1,k-1}-b_{k-1})\mathbf{g}(\mathbf{y},t_n+c_{k-1}\mathrm{\Delta }t),\mathtt{end}\hfill \\ \mathtt{end}\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_k\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \end{array}$$

Again, if implemented with four registers, the function $\mathbf{g}(\mathbf{y},t_n+c_k\mathrm{\Delta }t)$ can be computed just once per timestep (instead of thrice). In the present work, we extend the two- and three-register van der Houwen classes of ERK schemes to the DIRK case, which can be accomplished with precisely the same restrictions on the (lower triangular) DIRK Butcher tableau as in the (strictly lower triangular) ERK case, as specified above. Further, we will develop coordinated pairs of such [2R] and [3R] DIRK and ERK schemes in the IMEX setting described in Section 1.1. In particular, we will develop a [2R] second-order IMEX scheme, [2R] and [3R] third-order IMEX schemes, and a [3R] fourth-order IMEX scheme.

As shown in Section 1.1, six constraints on the parameters of the IMEX Butcher tableaux (1) must be satisfied for second-order accuracy, fourteen additional constraints must be satisfied for third-order accuracy, and fifty-two additional constraints must be satisfied for fourth-order accuracy. Before proceeding, we thus introduce some significant simplifying assumptions. Following [15] and [9] and the CN/RKW3 scheme of [13], we synchronize the stages of DIRK and ERK components by imposing $c_i^{\mathrm{IM}}=c_i^{\mathrm{EX}}=c_i$ for $i=1,\dots ,s$. We also coordinate the constituent DIRK and ERK components such that $b_i^{\mathrm{IM}}=b_i^{\mathrm{EX}}=b_i$ for $i=1,\dots ,s$, as also done in [15] and [9], but which is not satisfied by CN/RKW3. Finally, for each stage, a stage-order of one is also imposed such that

$$\sum _{j=1}^i{a}_{ij}^{\mathrm{IM}}=\sum _{j=1}^{i-1}{a}_{ij}^{\mathrm{EX}}=c_i\text{for}i=1,\dots ,s;$$

it follows that $c_1=a_{11}^{\mathrm{IM}}=a_{11}^{\mathrm{EX}}=0$. As a result of these assumptions, the number of constraints on the IMEX parameters [see (4a), (4b), (4c), (4d), (4e), (4f), (4g), (4h), (4i), (4j), (4k), (4l), (4m), (4n)] for second-order accuracy is reduced to just two, the number of constraints for third-order accuracy is reduced to five, and the number of constraints for fourth-order accuracy is reduced to fourteen.

For several of the IMEXRK schemes developed in this paper, a lower-order embedded scheme is also developed, relaxing the ${\hat{b}}_i^{\mathrm{IM}}={\hat{b}}_i^{\mathrm{EX}}$ restriction to provide increased freedom during the design phase. As a general guideline, none of the leading-order truncation terms of an embedded scheme should vanish, so that each of these terms will contribute to the error estimate (subject to this restriction, the remaining free parameters of the embedded scheme are then optimized to maximize the magnitude of the leading-order truncation terms). Unfortunately, this is not always achievable; as a result, not all of the schemes developed in this paper are listed with embedded schemes. For all of the embedded schemes we do report, the DIRK part of the embedded scheme is at least A-stable, which is a property of the embedded scheme recommended by [8]; note, however, that the embedded scheme is not used for time marching, it is only used to adjust the timestep.

The IMEX Butcher tableaux in (1) for coordinated pairs of [2R] DIRK and ERK schemes are thus simplified to

and the IMEX Butcher tableaux for coordinated pairs of [3R] DIRK and ERK schemes are simplified to

Note also that, as the DIRK component, the IMEXRK form considered above has an explicit first stage, its stability function (5) may be written

$$\sigma (z^{\mathrm{IM}};z^{\mathrm{EX}})=\frac{1+{\sum }_{i=1}^s{p}_i(z^{\mathrm{EX}}){[z^{\mathrm{IM}}]}^i}{1+{\sum }_{i=1}^{s-1}{q}_i{[z^{\mathrm{IM}}]}^i}\text{where}{p}_i\left(z^{\mathrm{EX}}\right)=\sum _{j=0}^{s-i}{\hat{p}}_{ij}{\left[z^{\mathrm{EX}}\right]}^j.$$

Note that, if the stiff part of the ODE is linear [that is, if $\mathbf{f}(\mathbf{x},t)=A\mathbf{x}$] then, denoting the efficient solution of $A\mathbf{x}=\mathbf{b}$ as $A^{-1}\mathbf{b}$, a straightforward implementation of the low-storage IMEXRK scheme in (16) that uses three registers² of length N to advance from $\mathbf{x}={\mathbf{x}}_n$ to $\mathbf{x}={\mathbf{x}}_{n+1}$ proceeds as follows:

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},\mathtt{else}\hfill \\ \mathbf{y}\leftarrow \mathbf{x}+(a_{k,k-1}^{\mathrm{IM}}-b_{k-1}^{\mathrm{IM}})\mathrm{\Delta }t\mathbf{z}+(a_{k,k-1}^{\mathrm{EX}}-b_{k-1}^{\mathrm{EX}})\mathrm{\Delta }t\mathbf{y}\hfill \\ \mathtt{end}\hfill \\ \mathbf{z}={(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}A\mathbf{y}\hfill \\ \mathbf{y}\leftarrow \mathbf{g}(\mathbf{y}+a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{z},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{z}+b_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{y}\hfill \\ \hat{\mathbf{x}}\leftarrow \hat{\mathbf{x}}+{\hat{b}}_k^{\mathrm{IM}}\mathrm{\Delta }t\mathbf{z}+{\hat{b}}_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{y}\hfill \\ \mathtt{end}\hfill \end{array}$$

where z and y store the implicit and explicit parts of the RHS at each stage, x is used to advance the solution of the main scheme,³ and $\hat{\mathbf{x}}$ stores the solution of the embedded scheme if adaptive time stepping is implemented. Note that one linear solve of the form ${(I-cA)}^{-1}\mathbf{b}$, one matrix/vector product $A\mathbf{y}$, and one nonlinear function evaluation $\mathbf{g}(\mathbf{y},t)$ are computed per stage, in addition to various level-1 BLAS (basic linear algebra subroutine) operations. As discussed in Section 1.1, implementation in the case of a nonlinear stiff part is a straightforward extension.

By applying the matrix inversion lemma ${(\hat{A}+\hat{B}\hat{C}\hat{D})}^{-1}={\hat{A}}^{-1}-{\hat{A}}^{-1}\hat{B}{({\hat{C}}^{-1}+\hat{D}{\hat{A}}^{-1}\hat{B})}^{-1}\hat{D}{\hat{A}}^{-1}$ with $\hat{A}=\hat{C}=I$, $\hat{D}=A$, and $B=-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }t$, the algorithm laid out in Section 1.2.1 may be rewritten in a form that only requires two registers² of length N:

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},\mathtt{else}\hfill \\ \mathbf{y}\leftarrow \mathbf{x}+(a_{k,k-1}^{\mathrm{IM}}-b_{k-1}^{\mathrm{IM}})\mathrm{\Delta }tA\mathbf{y}+(a_{k,k-1}^{\mathrm{EX}}-b_{k-1}^{\mathrm{EX}})\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \\ \mathbf{y}\leftarrow {(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}\mathbf{y}\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{y}+b_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \hat{\mathbf{x}}\leftarrow \hat{\mathbf{x}}+{\hat{b}}_k^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{y}+{\hat{b}}_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \end{array}$$

In this case, one linear solve of the form ${(I-cA)}^{-1}\mathbf{b}$ and two operations of the form⁴ $\mathbf{x}+cA\mathbf{y}+d\mathbf{g}(\mathbf{y},t)$ are computed per stage, in addition to various level-1 BLAS operations. However, the storage requirement is reduced from three registers of length N to only two, which is quite significant. In many cases, some of the coefficients in the above algorithm turn out to be zero, so the increased computational cost associated with the extra nonlinear function evaluations and matrix/vector products in this implementation is not as bad as one might initially anticipate, as quantified in Section 7.

For the development of the stage-order-two schemes IMEXRKCB3f and IMEXRKCB4 in Section 4 and Section 5, the [3R] IMEXRK structure (17) will be used to provide increased freedom during the design phase. Such schemes admit the following four-register implementation:

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},{\mathbf{z}}^{\mathrm{IM}}=\mathbf{x},{\mathbf{z}}^{\mathrm{EX}}\leftarrow \mathbf{x},\mathtt{else}\hfill \\ {\mathbf{z}}^{\mathrm{EX}}\leftarrow \mathbf{y}+a_{k,k-1}^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{EX}}\hfill \\ \mathtt{if}k<s,\mathbf{y}\leftarrow \mathbf{x}+(a_{k+1,k-1}^{\mathrm{IM}}-b_{k-1}^{\mathrm{IM}})\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{IM}}+(a_{k+1,k-1}^{\mathrm{EX}}-b_{k-1}^{\mathrm{EX}})({\mathbf{z}}^{\mathrm{EX}}-\mathbf{y})/a_{k,k-1}^{\mathrm{EX}},\mathtt{end}\hfill \\ {\mathbf{z}}^{\mathrm{EX}}\leftarrow {\mathbf{z}}^{\mathrm{EX}}+a_{k,k-1}^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{IM}}\hfill \\ \mathtt{end}\hfill \\ {\mathbf{z}}^{\mathrm{IM}}={(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}A{\mathbf{z}}^{\mathrm{EX}}\hfill \\ {\mathbf{z}}^{\mathrm{EX}}\leftarrow \mathbf{g}({\mathbf{z}}^{\mathrm{EX}}+a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{IM}},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{IM}}+b_k^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{EX}}\hfill \\ \hat{\mathbf{x}}\leftarrow \hat{\mathbf{x}}+{\hat{b}}_k^{\mathrm{IM}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{IM}}+{\hat{b}}_k^{\mathrm{EX}}\mathrm{\Delta }t{\mathbf{z}}^{\mathrm{EX}}\hfill \\ \mathtt{end}\hfill \end{array}$$

where ${\mathbf{z}}^{\mathrm{IM}}$ and ${\mathbf{z}}^{\mathrm{EX}}$ store the implicit and explicit parts of the RHS at each stage, y is a temporary variable which contributes to advance the solution to the next stage, x is used to advance the solution of the main scheme, and $\hat{\mathbf{x}}$ stores the solution of the embedded scheme if adaptive timestepping is used. As in the three-register implementation of the [2R] scheme, only one linear solve of the form ${(I-cA)}^{-1}\mathbf{b}$, one matrix/vector product, and one nonlinear function evaluation are computed per stage.

Leveraging matrix inversion lemma as done in Section 1.2.2, we obtain a general three-register implementation of any [3R] IMEXRK scheme:

$$\begin{array}{c}\mathtt{for}k=1:s\hfill \\ \mathtt{if}k==1,\mathbf{y}\leftarrow \mathbf{x},\mathbf{z}\leftarrow \mathbf{x},\mathtt{else}\hfill \\ \mathtt{if}k<s\hfill \\ \mathbf{z}\leftarrow \mathbf{y}+a_{k,k-1}^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{z}\hfill \\ \mathbf{y}\leftarrow A^{-1}(\mathbf{z}-\mathbf{y})/\left(a_{k,k-1}^{\mathrm{IM}}\mathrm{\Delta }t\right)\hfill \\ \mathbf{z}\leftarrow \mathbf{z}+a_{k,k-1}^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathbf{y}\leftarrow \mathbf{x}+(a_{k+1,k-1}^{\mathrm{IM}}-b_{k-1}^{\mathrm{IM}})\mathrm{\Delta }tA\mathbf{y}+(a_{k+1,k-1}^{\mathrm{EX}}-b_{k-1}^{\mathrm{EX}})\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathtt{else}\hfill \\ \mathbf{z}\leftarrow \mathbf{y}+a_{k,k-1}^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{z}+a_{k,k-1}^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{y},t_n+c_{k-1}^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \\ \mathtt{end}\hfill \\ \mathbf{z}\leftarrow {(I-a_{k,k}^{\mathrm{IM}}\mathrm{\Delta }tA)}^{-1}\mathbf{z}\hfill \\ \mathbf{x}\leftarrow \mathbf{x}+b_k^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{z}+b_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{z},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \hat{\mathbf{x}}\leftarrow \hat{\mathbf{x}}+{\hat{b}}_k^{\mathrm{IM}}\mathrm{\Delta }tA\mathbf{z}+{\hat{b}}_k^{\mathrm{EX}}\mathrm{\Delta }t\mathbf{g}(\mathbf{z},t_n+c_k^{\mathrm{EX}}\mathrm{\Delta }t)\hfill \\ \mathtt{end}\hfill \end{array}$$

Note that this algorithm requires the invertibility of the matrix A, a condition that is often true when A arises from the discretization of a PDE. In this case, two linear systems, three matrix/vector products, and three nonlinear function evaluations must be performed per stage (except for the last stage), plus an additional matrix/vector product and one nonlinear function evaluation if the embedded scheme is used for adaptive timestepping.

Finally, note that a (hardware-dependent) trade-off between flops and storage must ultimately be conducted to select between the two-register and three-register implementation of any [2R] scheme, or between the three-register and four-register implementation of any [3R] scheme.