Abstract
High order strong stability preserving (SSP) time discretizations are advantageous for use with spatial discretizations with nonlinear stability properties for the solution of hyperbolic PDEs. The search for high order strong stability time-stepping methods with large allowable strong stability time-step has been an active area of research over the last two decades. Recently, multiderivative time-stepping methods have been implemented with hyperbolic PDEs. In this work we describe sufficient conditions for a two-derivative multistage method to be SSP, and find some optimal SSP multistage two-derivative methods. While explicit SSP Runge–Kutta methods exist only up to fourth order, we show that this order barrier is broken for explicit multi-stage two-derivative methods by designing a three stage fifth order SSP method. These methods are tested on simple scalar PDEs to verify the order of convergence, and demonstrate the need for the SSP condition and the sharpness of the SSP time-step in many cases.
Similar content being viewed by others
References
Balsara, D.S., Shu, C.-W.: Monotonicity preserving weighted essentially non-oscillatory schemes with increasingly high order of accuracy. J. Comput. Phys. 160, 405–452 (2000)
Bresten, C., Gottlieb, S., Grant, Z., Higgs, D., Ketcheson, D.I., Németh, A.: Strong stability preserving multistep Runge–Kutta methods. Accept. Publ. Math. Comput
Chan, R.P.K., Tsai, A.Y.J.: On explicit two-derivative Runge–Kutta methods. Numer. Algorithms 53, 171–194 (2010)
Ferracina, L., Spijker, M.N.: Stepsize restrictions for the total-variation-diminishing property in general Runge–Kutta methods. SIAM J. Numer. Anal. 42, 1073–1093 (2004)
Ferracina, L., Spijker, M.N.: An extension and analysis of the Shu–Osher representation of Runge–Kutta methods. Math. Comput. 249, 201–219 (2005)
Gekeler, E., Widmann, R.: On the order conditions of Runge–Kutta methods with higher derivatives. Numer. Math. 50, 183–203 (1986)
Gottlieb, S., Ketcheson, D.I., Shu, C.-W.: Strong Stability Preserving Runge–Kutta and Multistep Time Discretizations. World Scientific Press, Singapore (2011)
Grant, Z.J.: Explicit SSP multistage two-derivative SSP optimization code. https://github.com/SSPmethods/SSPMultiStageTwoDerivativeMethods (2015)
Harten, A., Engquist, B., Osher, S., Chakravarthy, S.R.: Uniformly high-order accurate essentially nonoscillatory schemes. III. J. Comput. Phys. 71, 231–303 (1987)
Hesthaven, J., Gottlieb, S., Gottlieb, D.: Spectral Methods for Time Dependent Problems. Cambridge University Press, Cambridge Monographs of Applied and Computational Mathematics, Cambridge (2007)
Higueras, I.: On strong stability preserving time discretization methods. J. Sci. Comput. 21, 193–223 (2004)
Higueras, I.: Representations of Runge–Kutta methods and strong stability preserving methods. SIAM J. Numer. Anal. 43, 924–948 (2005)
Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202–228 (1996)
Kastlunger, K., Wanner, G.: On Turan type implicit Runge–Kutta methods. Comput. (Arch. Elektron. Rechnen) 9, 317–325 (1972). doi:10.1007/BF02241605
Kastlunger, K.H., Wanner, G.: Runge Kutta processes with multiple nodes. Comput. (Arch. Elektron. Rechnen) 9, 9–24 (1972)
Ketcheson, D.I.: Highly efficient strong stability preserving Runge–Kutta methods with low-storage implementations. SIAM J. Sci. Comput. 30, 2113–2136 (2008)
Ketcheson, D.I., Gottlieb, S., Macdonald, C.B.: Strong stability preserving two-step Runge-Kutta methods. SIAM J. Numer. Anal. 49, 2618–2639 (2012)
Ketcheson, D.I., Macdonald, C.B., Gottlieb, S.: Optimal implicit strong stability preserving Runge–Kutta methods. Appl. Numer. Math. 52, 373 (2009)
Ketcheson, D.I., Parsani, M., Ahmadia, A.J.: Rk-opt: software for the design of Runge–Kutta methods, version 0.2. https://github.com/ketch/RK-opt
Kraaijevanger, J.F.B.M.: Contractivity of Runge–Kutta methods. BIT 31, 482–528 (1991)
Lax, P., Wendroff, B.: Systems of conservation laws. Commun. Pure Appl. Math. 13, 217–237 (1960)
Mitsui, T.: Runge–Kutta type integration formulas including the evaluation of the second derivative. i. Publ. Res. Inst. Math. Sci. 18, 325–364 (1982)
Nguyen-Ba, T., Nguyen-Thu, H., Giordano, T., Vaillancourt, R.: One-step strong-stability-preserving Hermite–Birkhoff–Taylor methods. Sci. J. Riga Tech. Univ. 45, 95–104 (2010)
Obreschkoff, N.: Neue Quadraturformeln. Abh. Preuss. Akad. Wiss. Math. Nat. Kl. 4 (1940)
Ono, H., Yoshida, T.: Two-stage explicit Runge–Kutta type methods using derivatives. Jpn. J. Ind. Appl. Math. 21, 361–374 (2004)
Qiu, J., Dumbser, M., Shu, C.-W.: The discontinuous Galerkin method with Lax–Wendroff type time discretizations. Comput. Methods Appl. Mech. Eng. 194, 4528–4543 (2005)
Qiu, J., Shu, C.-W.: Finite difference WENO schemes with Lax–Wendroff-type time discretizations. SIAM J. Sci. Comput. 24, 2185–2198 (2003)
Ruuth, S.J., Spiteri, R.J.: Two barriers on strong-stability-preserving time discretization methods. J. Sci. Comput. 17, 211–220 (2002)
Seal, D.C., Guclu, Y., Christlieb, A.J.: High-order multiderivative time integrators for hyperbolic conservation laws. J. Sci. Comput. 60, 101–140 (2014)
Shintani, H.: On one-step methods utilizing the second derivative. Hiroshima Math. J. 1, 349–372 (1971)
Shintani, H.: On explicit one-step methods utilizing the second derivative. Hiroshima Math. J. 2, 353–368 (1972)
Shu, C.-W.: Total-variation diminishing time discretizations. SIAM J. Sci. Stat. Comp. 9, 1073–1084 (1988)
Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)
Spiteri, R.J., Ruuth, S.J.: A new class of optimal high-order strong-stability-preserving time discretization methods. SIAM J. Numer. Anal. 40, 469–491 (2002)
Stancu, D.D., Stroud, A.H.: Quadrature formulas with simple Gaussian nodes and multiple fixed nodes. Math. Comp. 17, 384–394 (1963)
Toro, E., Titarev, V.: Solution of the generalized Riemann problem for advection-reaction equations. Eng. Sci. Proc. R. Soc. Lond. A Math. Phys. 458, 271–281 (2002)
Tsai, A.Y.J., Chan, R.P.K., Wang, S.: Two-derivative Runge–Kutta methods for PDEs using a novel discretization approach. Numer. Algorithms 65, 687–703 (2014)
Turán, P.: On the theory of the mechanical quadrature. Acta Sci. Math. Szeged 12, 30–37 (1950)
Acknowledgments
This work was supported by: AFOSR Grants FA9550-12-1-0224, FA9550-12-1-0343, FA9550-12-1-0455, FA9550-15-1-0282, and FA9550-15-1-0235; NSF Grant DMS-1418804; New Mexico Consortium Grant NMC0155-01; and NASA Grant NMX15AP39G.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: Coefficients of Three Stage Fourth Order Methods
-
1.
For \(K=\frac{1}{2}\) we obtain an SSP coefficient \(\mathcal{{C}}=r =1.1464\). The Butcher array coefficients are given by
$$\begin{aligned} A= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 \quad &{} \quad 0\\ 0.436148675945340 &{} \quad 0 &{} \quad 0 \\ 0.546571371212865 &{} \quad 0.156647174804152 &{} \quad 0 \end{array} \right] , \; \; \; \; b = \left[ \begin{array}{l} 0.528992280543542 \\ 0.105732787708912 \\ 0.365274931747546 \end{array} \right] \\ \hat{A}= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 &{} \quad 0 \\ 0.095112833764436 &{} \quad 0 &{} \quad 0 \\ 0.071032477596813 &{} \quad 0.107904226252921 &{} \quad 0 \end{array} \right] , \; \; \; \; \hat{b} = \left[ \begin{array}{lll} 0.074866026156687 \\ 0.073410341982927 \\ 0.048740310097159 \end{array} \right] . \end{aligned}$$The Shu–Osher arrays are \(R \mathbf{e}= (1,0,0,0)^T\),
$$\begin{aligned} P= & {} \left[ \begin{array}{l l l l} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.5000&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.253176729307242 &{} \quad 0.179580018745470 &{} \quad 0&{} \quad 0\\ 0.181986129712082 &{} \quad 0.000000001889650 &{} \quad 0.418750476492704 &{} \quad 0 \\ \end{array} \right] \\ Q= & {} \left[ \begin{array}{l l l l} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.5&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0 &{} \quad 0.567243251947287 &{} \quad 0 &{} \quad 0\\ 0.140002406985210 &{} \quad 0.003037359947341&{} \quad 0.256223624973014 &{} \quad 0\ \end{array} \right] \end{aligned}$$ -
2.
For \(K=\sqrt{\frac{1}{2}}\) we obtain an SSP coefficient \(\mathcal{{C}}= r= 1.3927\) Butcher formulation
$$\begin{aligned} A= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 &{} \quad 0\\ 0.443752012194422 &{} \quad 0 &{} \quad 0 \\ 0.543193299768317 &{} \quad 0.149202742858795 &{} \quad 0 \end{array} \right] , \; \; \; \; b = \left[ \begin{array}{l} 0.515040964378407 \\ 0.178821699719783 \\ 0.306137335901811 \end{array} \right] \\ \hat{A}= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 &{} \quad 0\\ 0.098457924163299 &{} \quad 0 &{} \quad 0 \\ 0.062758211639901 &{} \quad 0.110738910914425 &{} \quad 0 \end{array} \right] , \; \; \; \; \hat{b} = \left[ \begin{array}{l} 0.072864982225864 \\ 0.073840478463180 \\ 0.061973770357455 \end{array} \right] . \end{aligned}$$The Shu–Osher arrays are \(R \mathbf{e}= (1,0,0,0)^T\),
$$\begin{aligned} P= & {} \left[ \begin{array}{l l l l} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.618033988749895&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.362588515112176 &{} \quad 0.207801573327953 &{} \quad 0&{} \quad 0\\ 0.144580879241747&{} \quad 0.110491604448675 &{} \quad 0.426371652664792 &{} \quad 0\\ \end{array} \right] \\ Q= & {} \left[ \begin{array}{l l l l} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.381966011250105&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0 &{} \quad 0.429609911559871 &{} \quad 0 &{} \quad 0\\ 0.078129569197367 &{} \quad 0&{} \quad 0.240426294447419 &{} \quad 0\ \end{array} \right] . \end{aligned}$$ -
3.
For \(K=1\) we obtain an SSP coefficient \(\mathcal{{C}}=r =1.6185\). The Butcher array coefficients are given by
$$\begin{aligned} A= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 &{} \quad 0 \\ 0.452297224196082 &{} \quad 0 &{} \quad 0 \\ 0.528050722182308&{} \quad 0.159236998008155 &{} \quad 0 \end{array} \right] , \; \; \; \; b = \left[ \begin{array}{l} 0.502519798444212\\ 0.210741084344740 \\ 0.286739117211047 \end{array} \right] \\ \hat{A}= & {} \left[ \begin{array}{lll} 0 &{} \quad 0 &{} \quad 0 \\ 0.102286389507741 &{} \quad 0 &{} \quad 0 \\ 0.055482128781494 &{} \quad 0.108677624192402 &{} \quad 0 \end{array} \right] , \; \; \; \; \hat{b} = \left[ \begin{array}{lll} 0.071256397204544 \\ 0.069475972085130 \\ 0.066877749079721 \end{array} \right] . \end{aligned}$$The Shu–Osher arrays are \(R \mathbf{e}= (1,0,0,0)^T\),
$$\begin{aligned} P= & {} \left[ \begin{array}{llll} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.732050807568877 &{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.457580533944888 &{} \quad 0.257727809835459 &{} \quad 0&{} \quad 0\\ 0.137886171629970 &{} \quad 0.176326540063367 &{} \quad 0.464092174540814 &{} \quad 0\\ \end{array} \right] , \\ Q= & {} \left[ \begin{array}{l l l l} 0&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0.267949192431123 &{} \quad 0&{} \quad 0&{} \quad 0 \\ 0 &{}\quad 0.284691656219654 &{} \quad 0 &{} \quad 0\\ 0.046502314960818 &{} \quad 0&{} \quad 0.175192798805030 &{} \quad 0\ \end{array} \right] . \end{aligned}$$
Appendix 2: Two Stage Third Order Method
This code gives the SSP coefficient and the Butcher and Shu Osher arrays for the optimal explicit SSP two stage third order method given the value K.
Appendix 3: Three Stage Fifth Order Method
This code gives the SSP coefficient and the Butcher and Shu Osher arrays for the optimal explicit SSP three stage fifth order method given the value K.
Rights and permissions
About this article
Cite this article
Christlieb, A.J., Gottlieb, S., Grant, Z. et al. Explicit Strong Stability Preserving Multistage Two-Derivative Time-Stepping Schemes. J Sci Comput 68, 914–942 (2016). https://doi.org/10.1007/s10915-016-0164-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-016-0164-2