Optimal implicit strong stability preserving Runge-Kutta methods. (English) Zbl 1157.65046
Summary: Strong stability preserving (SSP) time discretizations were developed for use with spatial discretizations of partial differential equations that are strongly stable under forward Euler time integration. SSP methods preserve convex boundedness and contractivity properties satisfied by forward Euler, under a modified timestep restriction.
We turn to implicit Runge-Kutta methods to alleviate this timestep restriction, and present implicit SSP Runge-Kutta methods which are optimal in the sense that they preserve convex boundedness properties under the largest timestep possible among all methods with a given number of stages and order of accuracy. We consider methods up to order six (the maximal order of SSP Runge-Kutta methods) and up to eleven stages.
The numerically optimal methods found are all diagonally implicit, leading us to conjecture that optimal implicit SSP Runge-Kutta methods are diagonally implicit. These methods allow a larger SSP timestep, compared to explicit methods of the same order and number of stages. Numerical tests verify the order and the SSP property of the methods.
We turn to implicit Runge-Kutta methods to alleviate this timestep restriction, and present implicit SSP Runge-Kutta methods which are optimal in the sense that they preserve convex boundedness properties under the largest timestep possible among all methods with a given number of stages and order of accuracy. We consider methods up to order six (the maximal order of SSP Runge-Kutta methods) and up to eleven stages.
The numerically optimal methods found are all diagonally implicit, leading us to conjecture that optimal implicit SSP Runge-Kutta methods are diagonally implicit. These methods allow a larger SSP timestep, compared to explicit methods of the same order and number of stages. Numerical tests verify the order and the SSP property of the methods.
MSC:
| 65L06 | Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations |
| 65L05 | Numerical methods for initial value problems involving ordinary differential equations |
| 65L20 | Stability and convergence of numerical methods for ordinary differential equations |
| 34A34 | Nonlinear ordinary differential equations and systems |
References:
| [1] | Butcher, J. C., On the implementation of implicit Runge-Kutta methods, BIT, 17, 375-378 (1976) · Zbl 0378.65039 |
| [2] | G. Dahlquist, R. Jeltsch, Generalized disks of contractivity for explicit and implicit Runge-Kutta methods, Tech. rep., Dept. of Numer. Anal. and Comp. Sci., Royal Inst. of Techn., Stockholm, 1979; G. Dahlquist, R. Jeltsch, Generalized disks of contractivity for explicit and implicit Runge-Kutta methods, Tech. rep., Dept. of Numer. Anal. and Comp. Sci., Royal Inst. of Techn., Stockholm, 1979 · Zbl 1106.65062 |
| [3] | Dekker, K.; Verwer, J. G., Stability of Runge-Kutta Methods for Stiff Nonlinear Differential Equations, CWI Monographs, vol. 2 (1984), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0571.65057 |
| [4] | Ferracina, L.; Spijker, M. N., Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods, SIAM Journal of Numerical Analysis, 42, 1073-1093 (2004) · Zbl 1080.65087 |
| [5] | L. Ferracina, M.N. Spijker, Computing optimal monotonicity-preserving Runge-Kutta methods, Tech. Rep. MI2005-07, Mathematical Institute, Leiden University, 2005; L. Ferracina, M.N. Spijker, Computing optimal monotonicity-preserving Runge-Kutta methods, Tech. Rep. MI2005-07, Mathematical Institute, Leiden University, 2005 · Zbl 1058.65098 |
| [6] | Ferracina, L.; Spijker, M. N., An extension and analysis of the Shu-Osher representation of Runge-Kutta methods, Mathematics of Computation, 249, 201-219 (2005) · Zbl 1058.65098 |
| [7] | Ferracina, L.; Spijker, M. N., Strong stability of singly-diagonally-implicit Runge-Kutta methods, Applied Numerical Mathematics, 58, 1675-1686 (2007) · Zbl 1153.65080 |
| [8] | Gottlieb, S., On high order strong stability preserving Runge-Kutta and multi step time discretizations, Journal of Scientific Computing, 25, 105-127 (2005) · Zbl 1203.65166 |
| [9] | Gottlieb, S.; Shu, C.-W., Total variation diminishing Runge-Kutta schemes, Mathematics of Computation, 67, 73-85 (1998) · Zbl 0897.65058 |
| [10] | Gottlieb, S.; Shu, C.-W.; Tadmor, E., Strong stability preserving high-order time discretization methods, SIAM Review, 43, 89-112 (2001) · Zbl 0967.65098 |
| [11] | Hairer, E.; Nørsett, S. P.; Wanner, G., Solving Ordinary Differential Equations I: Nonstiff Problems, Springer Series in Computational Mathematics, vol. 8 (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0789.65048 |
| [12] | Hairer, E.; Wanner, G., Solving Ordinary Differential Equations. II: Stiff and Differential-Algebraic Problems, Springer Series in Computational Mathematics, vol. 14 (1996), Springer-Verlag: Springer-Verlag Berlin · Zbl 0859.65067 |
| [13] | Higueras, I., On strong stability preserving time discretization methods, Journal of Scientific Computing, 21, 193-223 (2004) · Zbl 1074.65095 |
| [14] | Higueras, I., Representations of Runge-Kutta methods and strong stability preserving methods, SIAM Journal of Numerical Analysis, 43, 924-948 (2005) · Zbl 1097.65078 |
| [15] | Hundsdorfer, W.; Verwer, J., Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations, Springer Series in Computational Mathematics, vol. 14 (2003), Springer · Zbl 1030.65100 |
| [16] | D.I. Ketcheson, An algebraic characterization of strong stability preserving Runge-Kutta schemes, B.Sc. thesis, Brigham Young University, Provo, Utah, USA, 2004; D.I. Ketcheson, An algebraic characterization of strong stability preserving Runge-Kutta schemes, B.Sc. thesis, Brigham Young University, Provo, Utah, USA, 2004 |
| [17] | D.I. Ketcheson, Highly efficient strong stability preserving Runge-Kutta methods with low-storage implementations, SIAM Journal on Scientific Computing (2008), doi: 10.1137/07070485X; D.I. Ketcheson, Highly efficient strong stability preserving Runge-Kutta methods with low-storage implementations, SIAM Journal on Scientific Computing (2008), doi: 10.1137/07070485X · Zbl 1168.65382 |
| [18] | D.I. Ketcheson, High order numerical methods for wave propagation, unpublished doctoral thesis, University of Washington; D.I. Ketcheson, High order numerical methods for wave propagation, unpublished doctoral thesis, University of Washington |
| [19] | Ketcheson, D. I.; Macdonald, C. B.; Gottlieb, S., Numerically optimal SSP Runge-Kutta methods (2007), website |
| [20] | Ketcheson, D. I.; Robinson, A. C., On the practical importance of the SSP property for Runge-Kutta time integrators for some common Godunov-type schemes, International Journal for Numerical Methods in Fluids, 48, 271-303 (2005) · Zbl 1071.65121 |
| [21] | Kraaijevanger, J. F.B. M., Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems, Numerische Mathematik, 48, 303-322 (1986) · Zbl 0561.65055 |
| [22] | Kraaijevanger, J. F.B. M., Contractivity of Runge-Kutta methods, BIT, 31, 482-528 (1991) · Zbl 0763.65059 |
| [23] | LeVeque, R. J., Finite Volume Methods for Hyperbolic Problems (2002), Cambridge University Press · Zbl 1010.65040 |
| [24] | C.B. Macdonald, Constructing high-order Runge-Kutta methods with embedded strong-stability-preserving pairs, Master’s thesis, Simon Fraser University, August 2003; C.B. Macdonald, Constructing high-order Runge-Kutta methods with embedded strong-stability-preserving pairs, Master’s thesis, Simon Fraser University, August 2003 |
| [25] | Macdonald, C. B.; Gottlieb, S.; Ruuth, S. J., A numerical study of diagonally split Runge-Kutta methods for PDEs with discontinuities, Journal of Scientific Computing (2008) · Zbl 1203.65167 |
| [26] | Ruuth, S. J., Global optimization of explicit strong-stability-preserving Runge-Kutta methods, Mathematics of Computation, 75, 253, 183-207 (2006), (electronic) · Zbl 1080.65088 |
| [27] | Sahinidis, N. V.; Tawarmalani, M., BARON 7.2: Global Optimization of Mixed-Integer Nonlinear Programs (2004), User’s Manual, available at |
| [28] | Shu, C.-W., Total-variation diminishing time discretizations, SIAM Journal on Scientific and Statistical Computing, 9, 1073-1084 (1988) · Zbl 0662.65081 |
| [29] | Shu, C.-W., A survey of strong stability-preserving high-order time discretization methods, (Collected Lectures on the Preservation of Stability under Discretization (2002), SIAM: SIAM Philadelphia, PA) · Zbl 1494.65063 |
| [30] | Shu, C.-W.; Osher, S., Efficient implementation of essentially non-oscillatory shock-capturing schemes, Journal of Computational Physics, 77, 439-471 (1988) · Zbl 0653.65072 |
| [31] | Spijker, M. N., Contractivity in the numerical solution of initial value problems, Numerische Mathematik, 42, 271-290 (1983) · Zbl 0504.65030 |
| [32] | Spiteri, R. J.; Ruuth, S. J., A new class of optimal high-order strong-stability-preserving time discretization methods, SIAM Journal of Numerical Analysis, 40, 469-491 (2002) · Zbl 1020.65064 |
| [33] | Spiteri, R. J.; Ruuth, S. J., Nonlinear evolution using optimal fourth-order strong-stability-preserving Runge-Kutta methods, Mathematics and Computers in Simulation, 62, 125-135 (2003) · Zbl 1015.65031 |
| [34] | van de Griend, J. A.; Kraaijevanger, J. F.B. M., Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems, Numerische Mathematik, 49, 413-424 (1986) · Zbl 0595.65085 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
