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

Authors: Christopher Bresten, Sigal Gottlieb, Zachary Grant, Daniel Higgs, David I. Ketcheson and Adrian Németh
Journal: Math. Comp. 86 (2017), 747-769
MSC (2010): Primary 65M20
DOI: https://doi.org/10.1090/mcom/3115
Published electronically: June 2, 2016
MathSciNet review: 3584547
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

[1] Peter Albrecht, The Runge-Kutta theory in a nutshell, SIAM J. Numer. Anal. 33 (1996), no. 5, 1712–1735. MR 1411846, https://doi.org/10.1137/S0036142994260872
[2] 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, https://doi.org/10.1016/S0021-9991(02)00032-3
[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
[4] 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, https://doi.org/10.1016/j.apnum.2006.09.008
[5] 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, https://doi.org/10.1137/090766206
[6] 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, https://doi.org/10.1006/jcph.2002.7166
[7] L. Feng, C. Shu, and M. Zhang, A hybrid cosmological hydrodynamic/-body code based on a weighted essentially nonoscillatory scheme, The Astrophysical Journal 612 (2004), 1-13.
[8] 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, https://doi.org/10.1137/S0036142902415584
[9] 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, https://doi.org/10.1090/S0025-5718-04-01664-3
[10] S. Gottlieb, D. Higgs, and D. I. Ketcheson, Strong stability preserving site,
http:www.sspsite.org/msrk.html.
[11] 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, https://doi.org/10.1007/s10915-008-9239-z
[12] 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
[13] 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, https://doi.org/10.1137/S003614450036757X
[14] 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
[15] Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193–223. MR 2069949, https://doi.org/10.1023/B:JOMP.0000030075.59237.61
[16] Inmaculada Higueras, Representations of Runge-Kutta methods and strong stability preserving methods, SIAM J. Numer. Anal. 43 (2005), no. 3, 924–948. MR 2177549, https://doi.org/10.1137/S0036142903427068
[17] Chengming Huang, Strong stability preserving hybrid methods, Appl. Numer. Math. 59 (2009), no. 5, 891–904. MR 2495128, https://doi.org/10.1016/j.apnum.2008.03.030
[18] 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, https://doi.org/10.1016/j.jcp.2004.11.008
[19] David I. Ketcheson, Computation of optimal monotonicity preserving general linear methods, Math. Comp. 78 (2009), no. 267, 1497–1513. MR 2501060, https://doi.org/10.1090/S0025-5718-09-02209-1
[20] 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, https://doi.org/10.1137/10080960X
[21] J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, https://doi.org/10.1007/BF01933264
[22] 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, https://doi.org/10.1016/j.jcp.2004.04.020
[23] H. W. J. Lenferink, Contractivity preserving explicit linear multistep methods, Numer. Math. 55 (1989), no. 2, 213–223. MR 987386, https://doi.org/10.1007/BF01406515
[24] 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, https://doi.org/10.1016/j.apnum.2010.11.013
[25] 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, https://doi.org/10.1007/s10915-011-9473-7
[26] 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.
[27] H. Nguyen-Thu, Strong-stability-preserving Hermite-Birkhoff time-discretization methods, Dissertation, University of Ottawa, Canada, (2012).
[28] Huong Nguyen-Thu, Truong Nguyen-Ba, and Rémi Vaillancourt, Strong-stability-preserving, Hermite-Birkhoff time-discretization based on 𝑘 step methods and 8-stage explicit Runge-Kutta methods of order 5 and 4, J. Comput. Appl. Math. 263 (2014), 45–58. MR 3162335, https://doi.org/10.1016/j.cam.2013.11.013
[29] 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, https://doi.org/10.1006/jcph.1999.6345
[30] 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, https://doi.org/10.1023/A:1015156832269
[31] Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, https://doi.org/10.1137/0909073
[32] 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, https://doi.org/10.1137/060661739
[33] M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), no. 3, 271–290. MR 723625, https://doi.org/10.1007/BF01389573
[34] M. Tanguay and T. Colonius, Progress in modeling and simulation of shock wave lithotripsy (SWL), in Fifth International Symposium on cavitation (CAV2003), 2003.