Explicit strong stability preserving multistep Runge–Kutta methods

Bresten, Christopher; Gottlieb, Sigal; Grant, Zachary; Higgs, Daniel; Ketcheson, David; Németh, Adrian

doi:10.1090/mcom/3115

Explicit strong stability preserving multistep Runge–Kutta methods
HTML articles powered by AMS MathViewer

by Christopher Bresten, Sigal Gottlieb, Zachary Grant, Daniel Higgs, David I. Ketcheson and Adrian Németh;

Math. Comp. 86 (2017), 747-769

DOI: https://doi.org/10.1090/mcom/3115

Published electronically: June 2, 2016

PDF | Request permission

Abstract:

High-order spatial discretizations of hyperbolic PDEs are often designed to have strong stability properties, such as monotonicity. We study explicit multistep Runge–Kutta strong stability preserving (SSP) time integration methods for use with such discretizations. We prove an upper bound on the SSP coefficient of explicit multistep Runge–Kutta methods of order two and above. Numerical optimization is used to find optimized explicit methods of up to five steps, eight stages, and tenth order. These methods are tested on the linear advection and nonlinear Buckley-Leverett equations, and the results for the observed total variation diminishing and/or positivity preserving time-step are presented.

References

Peter Albrecht, The Runge-Kutta theory in a nutshell, SIAM J. Numer. Anal. 33 (1996), no. 5, 1712–1735. MR 1411846, DOI 10.1137/S0036142994260872
José A. Carrillo, Irene M. Gamba, Armando Majorana, and Chi-Wang Shu, A WENO-solver for the transients of Boltzmann-Poisson system for semiconductor devices: performance and comparisons with Monte Carlo methods, J. Comput. Phys. 184 (2003), no. 2, 498–525. MR 1959405, DOI 10.1016/S0021-9991(02)00032-3
Li-Tien Cheng, Hailiang Liu, and Stanley Osher, Computational high-frequency wave propagation using the level set method, with applications to the semi-classical limit of Schrödinger equations, Commun. Math. Sci. 1 (2003), no. 3, 593–621. MR 2069945
Vani Cheruvu, Ramachandran D. Nair, and Henry M. Tufo, A spectral finite volume transport scheme on the cubed-sphere, Appl. Numer. Math. 57 (2007), no. 9, 1021–1032. MR 2335233, DOI 10.1016/j.apnum.2006.09.008
Emil M. Constantinescu and Adrian Sandu, Optimal explicit strong-stability-preserving general linear methods, SIAM J. Sci. Comput. 32 (2010), no. 5, 3130–3150. MR 2729454, DOI 10.1137/090766206
Douglas Enright, Ronald Fedkiw, Joel Ferziger, and Ian Mitchell, A hybrid particle level set method for improved interface capturing, J. Comput. Phys. 183 (2002), no. 1, 83–116. MR 1944529, DOI 10.1006/jcph.2002.7166
L. Feng, C. Shu, and M. Zhang, A hybrid cosmological hydrodynamic/$N$-body code based on a weighted essentially nonoscillatory scheme, The Astrophysical Journal 612 (2004), 1–13.
L. Ferracina and M. N. Spijker, Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods, SIAM J. Numer. Anal. 42 (2004), no. 3, 1073–1093. MR 2113676, DOI 10.1137/S0036142902415584
L. Ferracina and M. N. Spijker, An extension and analysis of the Shu-Osher representation of Runge-Kutta methods, Math. Comp. 74 (2005), no. 249, 201–219. MR 2085408, DOI 10.1090/S0025-5718-04-01664-3
S. Gottlieb, D. Higgs, and D. I. Ketcheson, Strong stability preserving site, http:www.sspsite.org/msrk.html.
Sigal Gottlieb, David I. Ketcheson, and Chi-Wang Shu, High order strong stability preserving time discretizations, J. Sci. Comput. 38 (2009), no. 3, 251–289. MR 2475652, DOI 10.1007/s10915-008-9239-z
Sigal Gottlieb, David Ketcheson, and Chi-Wang Shu, Strong stability preserving Runge-Kutta and multistep time discretizations, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2011. MR 2789749, DOI 10.1142/7498
Sigal Gottlieb, Chi-Wang Shu, and Eitan Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Rev. 43 (2001), no. 1, 89–112. MR 1854647, DOI 10.1137/S003614450036757X
Jan S. Hesthaven, Sigal Gottlieb, and David Gottlieb, Spectral methods for time-dependent problems, Cambridge Monographs on Applied and Computational Mathematics, vol. 21, Cambridge University Press, Cambridge, 2007. MR 2333926, DOI 10.1017/CBO9780511618352
Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193–223. MR 2069949, DOI 10.1023/B:JOMP.0000030075.59237.61
Inmaculada Higueras, Representations of Runge-Kutta methods and strong stability preserving methods, SIAM J. Numer. Anal. 43 (2005), no. 3, 924–948. MR 2177549, DOI 10.1137/S0036142903427068
Chengming Huang, Strong stability preserving hybrid methods, Appl. Numer. Math. 59 (2009), no. 5, 891–904. MR 2495128, DOI 10.1016/j.apnum.2008.03.030
Shi Jin, Hailiang Liu, Stanley Osher, and Yen-Hsi Richard Tsai, Computing multivalued physical observables for the semiclassical limit of the Schrödinger equation, J. Comput. Phys. 205 (2005), no. 1, 222–241. MR 2132308, DOI 10.1016/j.jcp.2004.11.008
David I. Ketcheson, Computation of optimal monotonicity preserving general linear methods, Math. Comp. 78 (2009), no. 267, 1497–1513. MR 2501060, DOI 10.1090/S0025-5718-09-02209-1
David I. Ketcheson, Sigal Gottlieb, and Colin B. Macdonald, Strong stability preserving two-step Runge-Kutta methods, SIAM J. Numer. Anal. 49 (2011), no. 6, 2618–2639. MR 2873250, DOI 10.1137/10080960X
J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, DOI 10.1007/BF01933264
Simon Labrunie, José A. Carrillo, and Pierre Bertrand, Numerical study on hydrodynamic and quasi-neutral approximations for collisionless two-species plasmas, J. Comput. Phys. 200 (2004), no. 1, 267–298. MR 2086195, DOI 10.1016/j.jcp.2004.04.020
H. W. J. Lenferink, Contractivity preserving explicit linear multistep methods, Numer. Math. 55 (1989), no. 2, 213–223. MR 987386, DOI 10.1007/BF01406515
Truong Nguyen-Ba, Huong Nguyen-Thu, Thierry Giordano, and Rémi Vaillancourt, Strong-stability-preserving 3-stage Hermite-Birkhoff time-discretization methods, Appl. Numer. Math. 61 (2011), no. 4, 487–500. MR 2754573, DOI 10.1016/j.apnum.2010.11.013
Truong Nguyen-Ba, Huong Nguyen-Thu, Thierry Giordano, and Rémi Vaillancourt, Strong-stability-preserving 7-stage Hermite-Birkhoff time-discretization methods, J. Sci. Comput. 50 (2012), no. 1, 63–90. MR 2886319, DOI 10.1007/s10915-011-9473-7
T. Nguyen-Ba, H. Nguyen-Thu, and R. Vaillancourt, Strong-stability-preserving, k-step, 5- to 10-stage, Hermite-Birkhoff time-discretizations of order 12, American J. Computational Mathematics 1 (2011), 72–82.
H. Nguyen-Thu, Strong-stability-preserving Hermite-Birkhoff time-discretization methods, Dissertation, University of Ottawa, Canada, (2012).
Huong Nguyen-Thu, Truong Nguyen-Ba, and Rémi Vaillancourt, Strong-stability-preserving, Hermite-Birkhoff time-discretization based on $k$ step methods and 8-stage explicit Runge-Kutta methods of order 5 and 4, J. Comput. Appl. Math. 263 (2014), 45–58. MR 3162335, DOI 10.1016/j.cam.2013.11.013
Danping Peng, Barry Merriman, Stanley Osher, Hongkai Zhao, and Myungjoo Kang, A PDE-based fast local level set method, J. Comput. Phys. 155 (1999), no. 2, 410–438. MR 1723321, DOI 10.1006/jcph.1999.6345
Steven J. Ruuth and Raymond J. Spiteri, Two barriers on strong-stability-preserving time discretization methods, Proceedings of the Fifth International Conference on Spectral and High Order Methods (ICOSAHOM-01) (Uppsala), 2002, pp. 211–220. MR 1910562, DOI 10.1023/A:1015156832269
Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, DOI 10.1137/0909073
M. N. Spijker, Stepsize conditions for general monotonicity in numerical initial value problems, SIAM J. Numer. Anal. 45 (2007), no. 3, 1226–1245. MR 2318810, DOI 10.1137/060661739
M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), no. 3, 271–290. MR 723625, DOI 10.1007/BF01389573
M. Tanguay and T. Colonius, Progress in modeling and simulation of shock wave lithotripsy (SWL), in Fifth International Symposium on cavitation (CAV2003), 2003.