Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computation of optimal monotonicity preserving general linear methods

Author: David I. Ketcheson
Journal: Math. Comp. 78 (2009), 1497-1513
MSC (2000): Primary 65L06
Published electronically: January 22, 2009
MathSciNet review: 2501060
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. J.C. Butcher.
    Numerical Methods for Ordinary Differential Equations.
    Wiley, 2003. MR 1993957 (2004e:65069)
  • 2. M.-H. Chen, B. Cockburn, and F. Reitich.
    High-order RKDG methods for computational electromagnetics.
    Journal of Scientific Computing, 22-23:205-226, 2005. MR 2142195 (2005m:65208)
  • 3. 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.
    Journal of Computational Physics, 208:175-195, 2005. MR 2144697 (2006a:65124)
  • 4. D. Gottlieb and E. Tadmor.
    The CFL condition for spectral approximations to hyperbolic initial-boundary value problems.
    Mathematics of Computation, 56:565-588, 1991. MR 1066833 (91k:65137)
  • 5. Sigal Gottlieb.
    On high order strong stability preserving Runge-Kutta and multi step time discretizations.
    Journal of Scientific Computing, 25:105-127, 2005. MR 2231945 (2007f:65029)
  • 6. Sigal Gottlieb and Lee-Ad J. Gottlieb.
    Strong stability preserving properties of Runge-Kutta time discretization methods for linear constant coefficient operators.
    Journal of Scientific Computing, 18:83-109, 2003. MR 1958936 (2003m:65161)
  • 7. 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.
  • 8. Sigal Gottlieb and Steven J. Ruuth.
    Optimal strong-stability-preserving time-stepping schemes with fast downwind spatial discretizations.
    Journal of Scientific Computing, 27:289-303, 2006. MR 2285782 (2008j:65122)
  • 9. Sigal Gottlieb and Chi-Wang Shu.
    Total variation diminishing Runge-Kutta schemes.
    Mathematics of Computation, 67:73-85, 1998. MR 1443118 (98c:65122)
  • 10. Sigal Gottlieb, Chi-Wang Shu, and Eitan Tadmor.
    Strong stability preserving high-order time discretization methods.
    SIAM Review, 43:89-112, 2001. MR 1854647 (2002f:65132)
  • 11. E. Hairer, S.P. Norsett, and G. Wanner.
    Solving ordinary differential equations I: Nonstiff Problems.
    Springer Series in Computational Mathematics. Springer, Berlin, 1993. MR 1227985 (94c:65005)
  • 12. C. Huang.
    Strong stability preserving hybrid methods.
    Applied Numerical Mathematics, 2008.
    doi: 10.1016/j.apnum.2008.03.030.
  • 13. Rolf Jeltsch and Olavi Nevanlinna.
    Stability of explicit time discretizations for solving initial value problems.
    Numerische Mathematik, 37:61-91, 1981. MR 615892 (82g:65042)
  • 14. David I. Ketcheson.
    Highly efficient strong stability preserving Runge-Kutta methods with low-storage implementations.
    SIAM Journal on Scientific Computing, 30(4):2113-2136, 2008. MR 2407154
  • 15. David I. Ketcheson.
    Strong stability preserving two-step Runge-Kutta methods,
    in preparation.
  • 16. David I. Ketcheson, Colin B. Macdonald, and Sigal Gottlieb. See the
    SSP website:
  • 17. J. F. B. M. Kraaijevanger.
    Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems.
    Numerische Mathematik, 48:303-322, 1986. MR 826471 (87c:65084)
  • 18. J. F. B. M. Kraaijevanger.
    Contractivity of Runge-Kutta methods.
    BIT, 31:482-528, 1991. MR 1127488 (92i:65120)
  • 19. H W. J. Lenferink.
    Contractivity-preserving explicit linear multistep methods.
    Numerische Mathematik, 55:213-223, 1989. MR 987386 (90f:65058)
  • 20. H W. J. Lenferink.
    Contractivity-preserving implicit linear multistep methods.
    Math. Comp., 56:177-199, 1991. MR 1052098 (91i:65129)
  • 21. 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.
  • 22. Steven J. Ruuth and Willem Hundsdorfer.
    High-order linear multistep methods with general monotonicity and boundedness properties.
    Journal of Computational Physics, 209:226-248, 2005. MR 2145787 (2005m:65143)
  • 23. J. Sand.
    Circle contractive linear multistep methods.
    BIT, 26:114-122, 1986. MR 833836 (87h:65124)
  • 24. C.-W. Shu and S. Osher.
    Efficient implementation of essentially non-oscillatory shock-capturing schemes.
    Journal of Computational Physics, 77:439-471, 1988. MR 954915 (89g:65113)
  • 25. M. N. Spijker.
    Contractivity in the numerical solution of initial value problems.
    Numerische Mathematik, 42:271-290, 1983. MR 723625 (85b:65067)
  • 26. 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.
    Numerische Mathematik, 49:413-424, 1986. MR 853663 (87m:65102)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65L06

Retrieve articles in all journals with MSC (2000): 65L06

Additional Information

David I. Ketcheson
Affiliation: Department of Applied Mathematics, University of Washington, Seattle, Washington 98195-2420

Received by editor(s): May 13, 2008
Received by editor(s) in revised form: August 19, 2008
Published electronically: January 22, 2009
Additional Notes: This work was supported by a U.S. Department of Energy Computational Science Graduate Fellowship under grant number DE-FG02-97ER25308, and by AFOSR grant number FA9550-06-1-0255.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society