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.

References

Peter Albrecht, The Runge-Kutta theory in a nutshell, SIAM J. Numer. Anal. 33 (1996), no. 5, 1712–1735. MR 1411846, DOI https://doi.org/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 https://doi.org/10.1016/S0021-9991%2802%2900032-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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

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 https://doi.org/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

Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193–223. MR 2069949, DOI https://doi.org/10.1023/B%3AJOMP.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 https://doi.org/10.1137/S0036142903427068

Chengming Huang, Strong stability preserving hybrid methods, Appl. Numer. Math. 59 (2009), no. 5, 891–904. MR 2495128, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1137/10080960X

J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1023/A%3A1015156832269

Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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.