A review of high order strong stability preserving two-derivative explicit, implicit, and IMEX methods

Sigal Gottlieb, Zachary J. Grant · 2024

Read A review of high order strong stability preserving two-derivative explicit, implicit, and IMEX methods by Sigal Gottlieb, Zachary J. Grant (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15142.txt.

Introduction

Gottlieb and Grant published in twenty twenty-four a review of high-order time-stepping methods that preserve stability. Such methods simulate wave-like equations where sharp features must not blow up. Strong stability preserving schemes keep key bounds from the spatial model intact. The review covers methods that use two derivatives at each step. It spans explicit, implicit, and mixed implicit-explicit variants. Conditions for stability differ with how the second derivative enters.

For implicit schemes, one special condition can give stability without step limits. That condition also powers mixed schemes whose step size ignores the stiff part. The authors present theory for mixed general linear methods too. They include new second and third order methods built on that theory. The review gathers a decade of progress in one place.

Catalog record

CREATORSigal Gottlieb, Zachary J. Grant
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15142

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A review of high order strong stability preserving two-derivative explicit, implicit, and IMEX methods Sigal Gottlieb, Zachary J. Grant Abstract High order strong stability preserving (SSP) time discretizations ensure the nonlinear non-inner-product strong stability properties of spatial discretizations suited for the stable simulation of hyperbolic PDEs. Over the past decade multiderivative time-stepping have been used for the time-evolution hyperbolic PDEs, so that the strong stability properties of these methods have become increasingly relevant. In this work we review sufficient conditions for a two-derivative multistage method to preserve the strong stability properties of spatial discretizations in a forward Euler and different conditions on the second derivative. In particular we present the SSP theory for explicit and implicit two-derivative Runge–Kutta schemes, and discuss a special condition on the second derivative under which these implicit methods may be unconditionally SSP. This condition is then used in the context of implicit-explicit (IMEX) multi-derivative Runge–Kutta schemes, where the time-step restriction is independent of the stiff term. Finally, we present the SSP theory for implicit-explicit (IMEX) multi-derivative general linear methods, and some novel second and third order methods where the time-step restriction is independent of the stiff term. 1 Overview Strong stability preserving Runge–Kutta methods were developed by Shu in [ 71 , 72 ] to preserve the nonlinear stability properties of forward Euler in any norm, semi-norm, or convex functional. This approach was further studied for Runge–Kutta, multistep, and general linear methods in [ 31 , 32 , 66 , 70 , 74 , 75 , 28 , 38 , 67 , 37 , 65 , 73 , 45 , 47 , 51 , 30 , 57 , 39 , 40 , 6 ] . The study of the SSP properties of different time-stepping methods has been aided by its connections to contractivity theory [ 24 , 26 , 35 , 36 , 27 , 47 , 45 ] . SSP methods have proven useful in the solution of hyperbolic PDEs using many different spatial approaches [ 14 , 62 , 8 , 22 , 11 , 15 , 42 , 8 , 19 , 2 , 4 , 9 , 78 , 23 , 49 , 3 , 82 , 60 , 77 , 12 , 80 , 81 ] . They have been widely used for many application areas [ 80 , 61 , 77 , 8 , 4 , 19 , 2 , 82 , 23 , 3 , 53 , 49 , 12 , 60 , 14 , 9 , 78 , 15 , 11 , 42 ] . More recently, two-derivative SSP methods have become a subject of increasing interest [ 56 , 13 , 33 , 55 , 20 , 29 , 64 , 63 ] . In this work we review two-step Runge–Kutta methods which preserve the properties of forward Euler and a selection of conditions on the second derivative. In Section 2 we review SSP theory for Runge–Kutta methods. In Section 3 we discuss the strong stability preservation theory for two derivative methods and propose three different conditions on the second derivative that each lead to SSP two-derivative Runge–Kutta methods, and present some optimal methods in each class. Finally, in Section 4 we discuss implicit-explicit (IMEX) Runge–Kutta methods with two derivatives treated implicitly, and in Section 5 we extend this approach to IMEX general linear methods. We note that while this paper is a review of the topic of SSP two derivative methods, the material in Section 5 and the related order conditions in Appendix C is new. 2 SSP methods In numerically solving the hyperbolic conservation law \displaystyle U_{t}+f(U)_{x}=0, (1) oscillations leading to instability may occur when the exact solution develops sharp gradients or discontinuities. High order spatial discretizations that can handle discontinuities while preserving nonlinear non-inner-product stability properties, such as total variation stability or positivity, are required for the stable simulation of such problems. After discretizing in space using such a specially designed scheme (e.g. DG, TVD, WENO), we obtain the semi-discretized equation \displaystyle u_{t}=F(u), (2) (where u is a vector of approximations to U ) that has the property that the numerical solution is strongly stable when coupled with forward Euler time stepping \displaystyle\|u^{n+1}\| \displaystyle= \displaystyle\|u^{n}+\Delta tF(u^{n})\|\leq\|u^{n}\|,\quad 0\leq\Delta t\leq\Delta t_{{FE}}, (3) where \|\cdot\| is some norm, semi-norm, or convex functional, depending on the design of the spatial discretization. In practice, Euler’s method is not a preferred method, as it is low order and has a linear stability region that excludes the imaginary axis. Instead, we desire a higher order method that preserves the strong stability property \|u^{n+1}\|\leq\|u^{n}\| under a (possibly modified) time-step restriction \Delta t\leq\mathcal{C}\Delta t_{{FE}} . If such a method exists for \mathcal{C}>0 , we call it a strong stability preserving (SSP) method, and we say that \mathcal{C} is the SSP coefficient of the method. The research in the field of SSP methods focuses on finding SSP methods of high order with largest possible \mathcal{C} . 2.1 Explicit SSP Runge–Kutta methods In this section we will show that if a higher order Runge–Kutta method can be written as convex combinations of forward Euler steps, then any convex functional property ( 3 ) satisfied by the forward Euler scheme u^{n+1}=u^{n}+\Delta tF(u^{n}) (4) will be preserved under a modified time-step restriction \Delta t\leq\mathcal{C}\Delta t_{{FE}} [ 71 , 72 ] . In this sense, the forward Euler method is the building block to constructing SSP Runge–Kutta methods. In fact, the forward Euler condition is a natural and important property of an operator F ; it has been noted [ 25 ] that it is equivalent to the circle condition which is central to the analysis of contractive functions F . The s -stage explicit Runge–Kutta method \displaystyle y^{(0)} \displaystyle= \displaystyle u^{n}, \displaystyle y^{(i)} \displaystyle= \displaystyle\sum_{j=0}^{i-1}\left(\alpha_{i,j}y^{(j)}+\Delta t\beta_{i,j}F(y^{(j)})\right),\;\;\;\;i=1,...,s (5) \displaystyle u^{n+1} \displaystyle= \displaystyle y^{(s)} can be rewritten as convex combination of forward Euler steps of the form ( 4 ) by factoring each stage \displaystyle y^{(i)} \displaystyle= \displaystyle\sum_{j=0}^{i-1}\alpha_{i,j}\left(y^{(j)}+\Delta t\frac{\beta_{i,j}}{\alpha_{i,j}}F(y^{(j)})\right). If all the coefficients \alpha_{i,j} and \beta_{i,j} are non-negative, and \alpha_{i,j} is zero only if its corresponding \beta_{i,j} is zero, then the consistency condition \sum_{j=0}^{i-1}\alpha_{i,j}=1 and the forward Euler condition ( 3 ) imply that each stage is bounded by \displaystyle\|y^{(i)}\| \displaystyle\leq \displaystyle\sum_{j=0}^{i-1}\alpha_{i,j}\,\left\|y^{(j)}+\Delta t\frac{\beta_{i,j}}{\alpha_{i,j}}F(y^{(j})\right\|\leq\|y^{(j)}\| for \frac{\beta_{i,j}}{\alpha_{i,j}}\Delta t\leq\Delta t_{{FE}} . Putting this together for the entire Runge–Kutta method ( 5 ), we see that \displaystyle\|u^{n+1}\|\leq\|u^{n}\|\;\;\;\;\;\;\;\mbox{for}\;\;\;\;\Delta t\leq\mathcal{C}\Delta t_{{FE}}\;\;\;\;\mbox{where}\;\;\;\;\mathcal{C}=\min_{i,j}\frac{\alpha_{i,j}}{\beta_{i,j}}. (6) (If any \beta is equal to zero, we consider that ratio to be infinite.) The resulting time-step restriction is a combination of two distinct factors: (1) the term \Delta t_{{FE}} that depends on the spatial discretization, and (2) the SSP coefficient \mathcal{C} that depends only on the time-discretization. As stated above, any method that admits such a decomposition with \mathcal{C}>0 is called a strong stability preserving (SSP) method. This convex combination decomposition was used in the development of second and third order explicit SSP Runge–Kutta methods [ 71 ] and later of fourth order SSP Runge–Kutta methods methods [ 74 , 45 ] . These methods not only guarantee the strong stability properties of any spatial discretization, given only the forward Euler condition, but also ensure that the intermediate stages in a Runge–Kutta method satisfy the strong stability property as well. The

Read the complete text