Global optimization of explicit strong-stability-preserving Runge-Kutta methods

Ruuth, Steven

doi:10.1090/S0025-5718-05-01772-2

Global optimization of explicit strong-stability-preserving Runge-Kutta methods
HTML articles powered by AMS MathViewer

by Steven J. Ruuth PDF

Math. Comp. 75 (2006), 183-207 Request permission

Abstract:

Strong-stability-preserving Runge-Kutta (SSPRK) methods are a type of time discretization method that are widely used, especially for the time evolution of hyperbolic partial differential equations (PDEs). Under a suitable stepsize restriction, these methods share a desirable nonlinear stability property with the underlying PDE; e.g., positivity or stability with respect to total variation. This is of particular interest when the solution exhibits shock-like or other nonsmooth behaviour. A variety of optimality results have been proven for simple SSPRK methods. However, the scope of these results has been limited to low-order methods due to the detailed nature of the proofs. In this article, global optimization software, BARON, is applied to an appropriate mathematical formulation to obtain optimality results for general explicit SSPRK methods up to fifth-order and explicit low-storage SSPRK methods up to fourth-order. Throughout, our studies allow for the possibility of negative coefficients which correspond to downwind-biased spatial discretizations. Guarantees of optimality are obtained for a variety of third- and fourth-order schemes. Where optimality is impractical to guarantee (specifically, for fifth-order methods and certain low-storage methods), extensive numerical optimizations are carried out to derive numerically optimal schemes. As a part of these studies, several new schemes arise which have theoretically improved time-stepping restrictions over schemes appearing in the recent literature.

References

A. Brooke, D. Kendrick, A. Meeraus, and R. Raman, Gams-a users guide, GAMS Development Corporation, Washington, 1998.
Gams-the solver manuals, GAMS Development Corporation, Washington, 2001.
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
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
Sigal Gottlieb and Lee-Ad J. Gottlieb, Strong stability preserving properties of Runge-Kutta time discretization methods for linear constant coefficient operators, J. Sci. Comput. 18 (2003), no. 1, 83–109. MR 1958936, DOI 10.1023/A:1020338228736
Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical optimization, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1981. MR 634376
Sigal Gottlieb and Chi-Wang Shu, Total variation diminishing Runge-Kutta schemes, Math. Comp. 67 (1998), no. 221, 73–85. MR 1443118, DOI 10.1090/S0025-5718-98-00913-2
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
I. Higueras, Representations of Runge-Kutta methods and strong stability preserving methods, Technical Report No. 2, Departamento de Matematica e Informatica, Universidad Publica de Navarra, 2003.
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
Willem Hundsdorfer, Steven J. Ruuth, and Raymond J. Spiteri, Monotonicity-preserving linear multistep methods, SIAM J. Numer. Anal. 41 (2003), no. 2, 605–623. MR 2004190, DOI 10.1137/S0036142902406326
Reiner Horst and Hoang Tuy, Global optimization, 2nd ed., Springer-Verlag, Berlin, 1993. Deterministic approaches. MR 1274246, DOI 10.1007/978-3-662-02947-3
Christopher A. Kennedy, Mark H. Carpenter, and R. Michael Lewis, Low-storage, explicit Runge-Kutta schemes for the compressible Navier-Stokes equations, Appl. Numer. Math. 35 (2000), no. 3, 177–219. MR 1793508, DOI 10.1016/S0168-9274(99)00141-5
J. F. B. M. Kraaijevanger, Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems, Numer. Math. 48 (1986), no. 3, 303–322. MR 826471, DOI 10.1007/BF01389477
J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, DOI 10.1007/BF01933264
C. B. Macdonald, High-order embedded Runge-Kutta pairs for the time evolution of hyperbolic conservation laws, Master’s thesis, Simon Fraser University, Burnaby, BC, Canada, 2003.
B. A. Murtagh and M. A. Saunders, MINOS 5.1 User’s Guide, Report SOL 83-20R, Department of Operations Research, Stanford University, 1987.
Steven J. Ruuth and Willem Hundsdorfer, High-order linear multistep methods with general monotonicity and boundedness properties, J. Comput. Phys. 209 (2005), no. 1, 226–248. MR 2145787, DOI 10.1016/j.jcp.2005.02.029
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
Steven J. Ruuth and Raymond J. Spiteri, High-order strong-stability-preserving Runge-Kutta methods with downwind-biased spatial discretizations, SIAM J. Numer. Anal. 42 (2004), no. 3, 974–996. MR 2112790, DOI 10.1137/S0036142902419284
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
Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes, J. Comput. Phys. 77 (1988), no. 2, 439–471. MR 954915, DOI 10.1016/0021-9991(88)90177-5
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
Raymond J. Spiteri and Steven J. Ruuth, A new class of optimal high-order strong-stability-preserving time discretization methods, SIAM J. Numer. Anal. 40 (2002), no. 2, 469–491. MR 1921666, DOI 10.1137/S0036142901389025
Raymond J. Spiteri and Steven J. Ruuth, Non-linear evolution using optimal fourth-order strong-stability-preserving Runge-Kutta methods, Math. Comput. Simulation 62 (2003), no. 1-2, 125–135. Nonlinear waves: computation and theory, II (Athens, GA, 2001). MR 1983581, DOI 10.1016/S0378-4754(02)00179-9
N. V. Sahinidis and M. Tawarmalani, GAMS The Solver Manuals, GAMS Development Corporation, Washington, 2004, pp. 9–20.
Mohit Tawarmalani, Shabbir Ahmed, and Nikolaos V. Sahinidis, Product disaggregation in global optimization and relaxations of rational programs, Optim. Eng. 3 (2002), no. 3, 281–303. Special issue on mixed-integer programming and its applications to engineering. MR 1955959, DOI 10.1023/A:1021043227181
Mohit Tawarmalani and Nikolaos V. Sahinidis, Convexification and global optimization in continuous and mixed-integer nonlinear programming, Nonconvex Optimization and its Applications, vol. 65, Kluwer Academic Publishers, Dordrecht, 2002. Theory, algorithms, software, and applications. MR 1961018, DOI 10.1007/978-1-4757-3532-1
Mohit Tawarmalani and Nikolaos V. Sahinidis, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program. 99 (2004), no. 3, Ser. A, 563–591. MR 2051712, DOI 10.1007/s10107-003-0467-6
P. J. van der Houwen, Explicit Runge-Kutta formulas with increased stability boundaries, Numer. Math. 20 (1972/73), 149–164. MR 317547, DOI 10.1007/BF01404404
P. J. van der Houwen, Construction of integration formulas for initial value problems, North-Holland Series in Applied Mathematics and Mechanics, Vol. 19, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0519726
J. H. Williamson, Low-storage Runge-Kutta schemes, J. Comput. Phys. 35 (1980), no. 1, 48–56. MR 566473, DOI 10.1016/0021-9991(80)90033-9
A.A. Wray, Minimal storage time advancement schemes for spectral methods, Tech. report, NASA Ames Research Center, Moffett Field, CA, 1986.