Computation of optimal monotonicity preserving general linear methods

Ketcheson, David

doi:10.1090/S0025-5718-09-02209-1

Computation of optimal monotonicity preserving general linear methods
HTML articles powered by AMS MathViewer

by David I. Ketcheson PDF

Math. Comp. 78 (2009), 1497-1513 Request permission

Abstract:

Monotonicity preserving numerical methods for ordinary differential equations prevent the growth of propagated errors and preserve convex boundedness properties of the solution. We formulate the problem of finding optimal monotonicity preserving general linear methods for linear autonomous equations, and propose an efficient algorithm for its solution. This algorithm reliably finds optimal methods even among classes involving very high order accuracy and that use many steps and/or stages. The optimality of some recently proposed methods is verified, and many more efficient methods are found. We use similar algorithms to find optimal strong stability preserving linear multistep methods of both explicit and implicit type, including methods for hyperbolic PDEs that use downwind-biased operators.

References

J. C. Butcher, Numerical methods for ordinary differential equations, John Wiley & Sons, Ltd., Chichester, 2003. MR 1993957, DOI 10.1002/0470868279
Min-Hung Chen, Bernardo Cockburn, and Fernando Reitich, High-order RKDG methods for computational electromagnetics, J. Sci. Comput. 22/23 (2005), 205–226. MR 2142195, DOI 10.1007/s10915-004-4152-6
Bernardo Cockburn, Jianliang Qian, Fernando Reitich, and Jing Wang, An accurate spectral/discontinuous finite-element formulation of a phase-space-based level set approach to geometrical optics, J. Comput. Phys. 208 (2005), no. 1, 175–195. MR 2144697, DOI 10.1016/j.jcp.2005.02.009
David Gottlieb and Eitan Tadmor, The CFL condition for spectral approximations to hyperbolic initial-boundary value problems, Math. Comp. 56 (1991), no. 194, 565–588. MR 1066833, DOI 10.1090/S0025-5718-1991-1066833-9
Sigal Gottlieb, On high order strong stability preserving Runge-Kutta and multi step time discretizations, J. Sci. Comput. 25 (2005), no. 1-2, 105–128. MR 2231945, DOI 10.1007/s10915-004-4635-5
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
Sigal Gottlieb, David I. Ketcheson, and Chi-Wang Shu. High order strong stability preserving time discretizations. Journal of Scientific Computing, DOI: 10.1007/s10915-008-9239-z.
Sigal Gottlieb and Steven J. Ruuth, Optimal strong-stability-preserving time-stepping schemes with fast downwind spatial discretizations, J. Sci. Comput. 27 (2006), no. 1-3, 289–303. MR 2285782, DOI 10.1007/s10915-005-9054-8
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
E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations. I, 2nd ed., Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1993. Nonstiff problems. MR 1227985
C. Huang. Strong stability preserving hybrid methods. Applied Numerical Mathematics, 2008. doi: 10.1016/j.apnum.2008.03.030.
Rolf Jeltsch and Olavi Nevanlinna, Stability of explicit time discretizations for solving initial value problems, Numer. Math. 37 (1981), no. 1, 61–91. MR 615892, DOI 10.1007/BF01396187
David I. Ketcheson, Highly efficient strong stability-preserving Runge-Kutta methods with low-storage implementations, SIAM J. Sci. Comput. 30 (2008), no. 4, 2113–2136. MR 2407154, DOI 10.1137/07070485X
David I. Ketcheson. Strong stability preserving two-step Runge-Kutta methods, 2008, in preparation.
David I. Ketcheson, Colin B. Macdonald, and Sigal Gottlieb. See the SSP website: http://www.cfm.brown.edu/people/sg/ssp.html.
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
H. W. J. Lenferink, Contractivity preserving explicit linear multistep methods, Numer. Math. 55 (1989), no. 2, 213–223. MR 987386, DOI 10.1007/BF01406515
H. W. J. Lenferink, Contractivity-preserving implicit linear multistep methods, Math. Comp. 56 (1991), no. 193, 177–199. MR 1052098, DOI 10.1090/S0025-5718-1991-1052098-0
Tiao Lu, Wei Cai, and Pingwen Zhang. Discontinuous Galerkin time-domain method for GPR simulation in dispersive media. IEEE Transactions on Geoscience and Remote Sensing, 43(1):72–80, 2005.
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
Jørgen Sand, Circle contractive linear multistep methods, BIT 26 (1986), no. 1, 114–122. MR 833836, DOI 10.1007/BF01939367
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
J. A. van de Griend and J. F. B. M. Kraaijevanger, Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems, Numer. Math. 49 (1986), no. 4, 413–424. MR 853663, DOI 10.1007/BF01389539