Contents

Overview

NodePy (Numerical ODEs in Python) is a Python package for designing, analyzing, and testing numerical methods for initial value ODEs. Its development was motivated by my own research in time integration methods for PDEs. I found that I was frequently repeating tasks that could be automated and integrated. Initially I developed a collection of MATLAB scripts, but this became unwieldy due to the large number of files that were necessary and the more limited capability for code reuse.

NodePy represents an object-oriented approach, in which the basic object is a numerical ODE solver. The idea is to design a laboratory for such methods in the same sense that MATLAB is a laboratory for matrices. Some distinctive design goals are:

  • Plug-and-play: any method can be applied to any problem using the same syntax. Also, properties of different kinds of methods are available through the same syntax. This makes it easy to compare different methods.

  • Abstract representations: Generally, the most abstract (hence powerful) representaton of an object is used whenever possible. Thus, order conditions are generated using products on rooted trees (or other recursions) rather than being hard-coded.

  • Numerical representation: The most precise representation possible is used for quantities such as coefficients: rational numbers (using SymPy’s Rational class) when available, floating-point numbers otherwise. Where necessary, method properties are determined by numerical calculations, using appropriate tolerances. Thus the “order” of a method with floating-point coefficients is determined by checking whether the order conditions are satisfied to within a small value (near machine-epsilon). For efficiency reasons, coefficients are always converted to floating-point for purposes of applying the method to a problem.

In general, user-friendliness of the interface and readability of the code are prioritized over performance.

NodePy includes capabilities for applying the methods to solve systems of ODEs. This is mainly intended for testing and comparison; for realistic problems of interest in most fields, time-stepping in Python will be too slow. One way around this is to wrap Fortran or C functions representing the right-hand-side of the ODE, and we are looking into this.

Note

The online documentation is not comprehensive. For more complete documentation, it is best to refer to the docstrings of specific functions and classes.

Dependencies

  • Works with Python 3.5+

  • Requires: Numpy, Matplotlib, Sympy

  • SymPy (note: NodePy is now compatible with SymPy 0.7.1)

  • Optional: networkx (for some Runge-Kutta stage dependency graphing), cvxpy (for finding optimal downwind perturbations), scipy

Classes of Numerical ODE Solvers

NodePy includes classes for the following types of methods:

Arbitrary methods in these classes can be instantiated by specifying their coefficients.

Analysis of Methods

NodePy includes functions for analyzing many properties, including:
  • Stability:
    • Absolute stability (e.g., plot the region of absolute stability)

    • Strong stability preservation

  • Accuracy
    • Order of accuracy

    • Error coefficients

    • Relative accuracy efficiency

    • Generation of Python and MATLAB code for order conditions

Testing Methods

NodePy includes implementation of the actual time-stepping algorithms for the various classes of methods. A wide range of initial value ODEs can be loaded, including the DETEST suite of problems. Arbitrary initial value problems can be instantiated and solved simply by calling a method with the initial value problem as argument. For methods with error estimates, adaptive time-stepping can be used based on a specified error tolerance. NodePy also includes automated functions for convergence testing.

In the future, NodePy may also support solving semi-discretizations of initial boundary value PDEs.

NodePy Manual

Modules Reference

Indices and tables

Alb96

Peter Albrecht. The Runge–Kutta Theory in a Nutshell. SIAM Journal on Numerical Analysis, 33(5):1712 – 1735, 1996.

BCF+85

Randolph E Bank, William M Coughran, Wolfgang Fichtner, Eric H Grosse, Donald J Rose, and R Kent Smith. Transient simulation of silicon devices and circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 4(4):436–451, 1985.

BS96

P Bogacki and Lawrence F Shampine. An efficient Runge-Kutta (4, 5) pair. Computers & Mathematics with Applications, 32(6):15–28, 1996.

BS89

Przemyslaw Bogacki and Lawrence F Shampine. A 3 (2) pair of runge–kutta formulas. Applied Mathematics Letters, 2(4):321–325, 1989.

But08

J. C. Butcher. Numerical Methods for Ordinary Differential Equations. Wiley, 2 edition, 2008.

BT97

J. C. Butcher and S. Tracogna. Order conditions for Two-Step Runge–Kutta methods. Applied Numerical Mathematics, 24:351–364, 1997.

But64

John C Butcher. Implicit runge–kutta processes. Mathematics of Computation, 18(85):50–64, 1964.

CMRandez90

M Calvo, JI Montijano, and L Rández. A new embedded pair of runge–kutta formulas of orders 5 and 6. Computers & Mathematics with Applications, 20(1):15–24, 1990.

CK90

Jeff R Cash and Alan H Karp. A variable order runge–kutta method for initial value problems with rapidly varying right-hand sides. ACM Transactions on Mathematical Software (TOMS), 16(3):201–222, 1990.

Chi71

FH Chipman. A-stable runge–kutta processes. BIT Numerical Mathematics, 11(4):384–388, 1971.

CFS18

Sidafa Conde, Imre Fekete, and John N Shadid. Embedded error estimation and adaptive step-size control for optimal explicit strong stability preserving Runge-Kutta methods. 2018. arXiv:1806.08693.

DV84

K. Dekker and J. G. Verwer. Stability of Runge–Kutta methods for stiff nonlinear differential equations. Volume 2 of CWI Monographs. North-Holland Publishing Co., 1984.

DP80

J.R. Dormand and P.J. Prince. A family of embedded Runge-Kutta formulae. Journal of Computational and Applied Mathematics, 6(1):19–26, 1980.

DGR00

Alok Dutt, Leslie Greengard, and Vladimir Rokhlin. Spectral deferred correction methods for ordinary differential equations. BIT Numerical Mathematics, 40(2):241–266, 2000.

Ehl69

Byron L Ehle. On Padé approximations to the exponential function and A-stable methods for the numerical solution of initial value problems. PhD thesis, University of Waterloo Waterloo, Ontario, 1969.

EP87

W. H. Enright and JD Pryce. Two FORTRAN packages for assessing initial value methods. ACM Transactions on Mathematical Software, 13(1):1–27, 1987.

Feh69

Erwin Fehlberg. Klassische runge–kutta-formeln fünfter und siebenter ordnung mit schrittweiten-kontrolle. Computing, 4(2):93–106, 1969.

GKS09

Sigal Gottlieb, David I Ketcheson, and Chi-Wang Shu. High order strong stability preserving time discretizations. Journal of Scientific Computing, 38(3):251–289, 2009.

GST01

Sigal Gottlieb, Chi-Wang Shu, and Eitan Tadmor. Strong stability-preserving high-order time discretization methods. SIAM review, 43(1):89–112, 2001.

HNorW93

Ernst Hairer, Syvert P. Nø rsett, and G. Wanner. Solving ordinary differential equations \I\: Nonstiff Problems. Springer Series in Computational Mathematics. Springer, Berlin, second edition, 1993.

HW96

Ernst Hairer and G. Wanner. Solving ordinary differential equations \II\: Stiff and differential-algebraic problems. Volume 14 of Springer Series in Computational Mathematics. Springer, Berlin, second edition, 1996.

Heu00

Karl Heun. Neue methoden zur approximativen integration der differentialgleichungen einer unabhängigen veränderlichen. Z. Math. Phys, 45:23–38, 1900.

HH90

Desmond J Higham and George Hall. Embedded runge–kutta formulae with stable equilibrium states. Journal of computational and applied mathematics, 29(1):25–33, 1990.

Hig05

Inmaculada Higueras. Representations of Runge–Kutta methods and strong stability preserving methods. Siam Journal On Numerical Analysis, 43:924–948, 2005.

JT95

Zdzislaw Jackiewicz and S. Tracogna. A general class of two-step Runge–Kutta methods for ordinary differential equations. SIAM Journal on Numerical Analysis, 32:1390–1427, 1995.

KCL00

C. A. Kennedy, M. H. Carpenter, and R Michael Lewis. Low-storage, explicit Runge–Kutta schemes for the compressible Navier–Stokes equations. Applied Numerical Mathematics, 35(3):177–219, November 2000.

Ket08

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.

Ket10

David I. Ketcheson. Runge–Kutta methods with minimum storage implementations. Journal of Computational Physics, 229(5):1763–1773, March 2010.

KMG09

David I. Ketcheson, Colin B. Macdonald, and Sigal Gottlieb. Optimal implicit strong stability preserving Runge–Kutta methods. Applied Numerical Mathematics, 59(2):373–392, February 2009.

Kra91

J. F. B. M. Kraaijevanger. Contractivity of Runge–Kutta Methods. BIT Numerical Mathematics, 31:482–528, 1991.

LeV07

Randall J. LeVeque. Finite Difference Methods for Ordinary and Partial Differential Equations: steady-state and time-dependent problems. SIAM, 2007.

Nor74

Syvert P Norsett. Semi explicit Runge–Kutta methods. Matematisk Institut, Universitet I, 1974.

PD81

P.J. Prince and J.R. Dormand. High order embedded Runge–Kutta formulae. Journal of Computational and Applied Mathematics, 7(1):67–75, March 1981.

RS04

Steven J. Ruuth and Raymond J Spiteri. High-order strong-stability-preserving Runge–Kutta methods with downwind-biased spatial discretizations. SIAM Journal on Numerical Analysis, 42:974–996, 2004.

San86

J Sand. Circle contractive linear multistep methods. BIT Numerical Mathematics, 26:114–122, 1986.

SS93

Philip W Sharp and E Smart. Explicit Runge-Kutta pairs with one more derivative evaluation than the minimum. SIAM Journal on Scientific Computing, 14(2):338–348, 1993. doi:10.1137/0914021.

SO88

Chi-Wang Shu and Stanley Osher. Efficient implementation of essentially non-oscillatory shock-capturing schemes. Journal of Computational Physics, 77(2):439–471, August 1988.

Tsi11

Ch Tsitouras. Runge–kutta pairs of order 5 (4) satisfying only the first column simplifying assumption. Computers & Mathematics with Applications, 62(2):770–775, 2011.

VS04

Jan G Verwer and Ben P Sommeijer. An implicit-explicit runge–kutta–chebyshev scheme for diffusion-reaction equations. SIAM Journal on Scientific Computing, 25(5):1824–1835, 2004.

WS07

Rong Wang and Raymond J Spiteri. Linear Instability of the Fifth-Order WENO Method. SIAM Journal on Numerical Analysis, 45:1871–1901, 2007.