Abstract
Diagonally split Runge–Kutta (DSRK) time discretization methods are a class of implicit time-stepping schemes which offer both high-order convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of Runge–Kutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) time-stepping community which is generally concerned with computing oscillation-free numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second- and third-order unconditionally contractive DSRK methods do preserve the strong stability property for all time step-sizes, they suffer from order reduction at large step-sizes. Indeed, for time-steps larger than those typically chosen for explicit methods, these DSRK methods behave like first-order implicit methods. This is unfortunate, because it is precisely to allow a large time-step that we choose to use implicit methods. These results suggest that unconditionally contractive DSRK methods are limited in usefulness as they are unable to compete with either the first-order backward Euler method for large step-sizes or with Crank–Nicolson or high-order explicit SSP Runge–Kutta methods for smaller step-sizes.
We also present stage order conditions for DSRK methods and show that the observed order reduction is associated with the necessarily low stage order of the unconditionally contractive DSRK methods.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bellen, A., Torelli, L.: Unconditional contractivity in the maximum norm of diagonally split Runge–Kutta methods. SIAM J. Numer. Anal. 34(2), 528–543 (1997)
Bellen, A., Jackiewicz, Z., Zennaro, M.: Contractivity of waveform relaxation Runge–Kutta iterations and related limit methods for dissipative systems in the maximum norm. SIAM J. Numer. Anal. 31(2), 499–523 (1994)
Black, F., Scholes, M.: The pricing of options and corporate liabilities. J. Polit. Econ. 81(3), 637–654 (1973)
Butcher, J.C.: General linear methods. Acta Numer. 15, 157–256 (2006)
Coleman, T.: Option pricing: the hazards of computing delta and gamma. Website, http://www.fenews.com/fen49/where_num_matters/numerics.htm (2006)
Ferracina, L., Spijker, M.N.: Stepsize restrictions for the total-variation-diminishing property in general Runge–Kutta methods. SIAM J. Numer. Anal. 42(3), 1073–1093 (2004) (electronic)
Ferracina, L., Spijker, M.N.: An extension and analysis of the Shu–Osher representation of Runge–Kutta methods. Math. Comput. 74(249), 201–219 (2005) (electronic)
Ferracina, L., Spijker, M.N.: Strong stability of singly-diagonally-implicit Runge–Kutta methods. Appl. Numer. Math. (2007). doi: 10.1016/j.apnum.2007.10.004
Forsyth, P.A.: An introduction to computational finance without agonizing pain. Available on author’s website, http://www.cs.uwaterloo.ca/~paforsyt/agon.pdf, February 2005
Giles, M.B., Carter, R.: Convergence analysis of Crank–Nicolson and Rannacher time-marching. J. Comput. Financ. 9(4), 89–112 (2006)
Gottlieb, S.: On high order strong stability preserving Runge–Kutta and multi step time discretizations. J. Sci. Comput. 25(1-2), 105–128 (2005)
Gottlieb, S., Shu, C.-W.: Total variation diminishing Runge–Kutta schemes. Math. Comput. 67(221), 73–85 (1998)
Gottlieb, S., Shu, C.-W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43(1), 89–112 (2001) (electronic)
Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Springer Series in Computational Mathematics, vol. 14. Springer, Berlin (1991)
Higueras, I.: On strong stability preserving time discretization methods. J. Sci. Comput. 21(2), 193–223 (2004)
Higueras, I.: Representations of Runge–Kutta methods and strong stability preserving methods. SIAM J. Numer. Anal. 43(3), 924–948 (2005) (electronic)
Horváth, Z.: Positivity of Runge–Kutta and diagonally split Runge–Kutta methods. Appl. Numer. Math. 28(2–4), 309–326 (1998). Eighth Conference on the Numerical Treatment of Differential Equations (Alexisbad, 1997)
Hundsdorfer, W., Ruuth, S.J.: On monotonicity and boundedness properties of linear multistep methods. Math. Comput. 75(254), 655–672 (2006) (electronic)
Hundsdorfer, W., Ruuth, S.J., Spiteri, R.J.: Monotonicity-preserving linear multistep methods. SIAM J. Numer. Anal. 41(2), 605–623 (2003) (electronic)
in ’t Hout, K.J.: A note on unconditional maximum norm contractivity of diagonally split Runge–Kutta methods. SIAM J. Numer. Anal. 33(3), 1125–1134 (1996)
Ketcheson, D.I., Macdonald, C.B., Gottlieb, S.: Optimal implicit strong stability preserving Runge–Kutta methods (2007, submitted)
Kraaijevanger, J.F.B.M.: Contractivity of Runge–Kutta methods. BIT 31(3), 482–528 (1991)
Layton, A.T., Minion, M.L.: Implications of the choice of quadrature nodes for Picard integral deferred corrections methods for ordinary differential equations. BIT 45(2), 341–373 (2005)
Lenferink, H.W.J.: Contractivity preserving explicit linear multistep methods. Numer. Math. 55(2), 213–223 (1989)
Lenferink, H.W.J.: Contractivity-preserving implicit linear multistep methods. Math. Comput. 56(193), 177–199 (1991)
Macdonald, C.B.: Constructing high-order Runge–Kutta methods with embedded strong-stability-preserving pairs. Master’s Thesis, Simon Fraser University, August 2003
Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Sciences, vol. 153. Springer, New York (2003)
Prothero, A., Robinson, A.: On the stability and accuracy of one-step methods for solving stiff systems of ordinary differential equations. Math. Comput. 28, 145–162 (1974)
Ruuth, S.J.: Global optimization of explicit strong-stability-preserving Runge–Kutta methods. Math. Comput. 75(253), 183–207 (2006) (electronic)
Ruuth, S.J., Spiteri, R.J.: Two barriers on strong-stability-preserving time discretization methods. J. Sci. Comput. 17(1–4), 211–220 (2002). Proceedings of the Fifth International Conference on Spectral and High Order Methods (ICOSAHOM-01) (Uppsala)
Sahinidis, N.V., Tawarmalani, M.: BARON 7.2: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual (2004). Available at http://www.gams.com/dd/docs/solvers/baron.pdf
Shu, C.-W.: Total-variation-diminishing time discretizations. SIAM J. Sci. Statist. Comput. 9(6), 1073–1084 (1988)
Shu, C.-W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes. J. Comput. Phys. 77(2), 439–471 (1988)
Spijker, M.N.: Contractivity in the numerical solution of initial value problems. Numer. Math. 42(3), 271–290 (1983)
Spijker, M.N.: Stepsize conditions for general monotonicity in numerical initial value problems. SIAM J. Numer. Anal. 45(3), 1226–1245 (2007) (electronic)
Spiteri, R.J., Ruuth, S.J.: A new class of optimal high-order strong-stability-preserving time discretization methods. SIAM J. Numer. Anal. 40(2), 469–491 (2002)
Spiteri, R.J., Ruuth, S.J.: Non-linear evolution using optimal fourth-order strong-stability-preserving Runge–Kutta methods. Math. Comput. Simulation 62(1–2), 125–135 (2003). Nonlinear Waves: Computation and Theory, II (Athens, GA, 2001)
Zennaro, M.: Contractivity of Runge–Kutta methods with respect to forcing terms. Appl. Numer. Math. 11(4), 321–345 (1993)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of C.B. Macdonald was partially supported by an NSERC Canada PGS-D scholarship, a grant from NSERC Canada, and a scholarship from the Pacific Institute for the Mathematical Sciences (PIMS).
The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255.
The work of S.J. Ruuth was partially supported by a grant from NSERC Canada.
Rights and permissions
About this article
Cite this article
Macdonald, C.B., Gottlieb, S. & Ruuth, S.J. A Numerical Study of Diagonally Split Runge–Kutta Methods for PDEs with Discontinuities. J Sci Comput 36, 89–112 (2008). https://doi.org/10.1007/s10915-007-9180-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-007-9180-6