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:
- Runge-Kutta Methods
Implicit

Explicit

Embedded pairs

Low-storage methods

Extrapolation methods

Integral deferred correction methods

Strong stability preserving methods

Runge-Kutta-Chebyshev 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¶

- Quick Start Guide
- Classes of ODE solvers
- Testing Methods: Solving Initial Value Problems
- Analyzing Stability Properties
- Rooted Trees
- What’s new in version 1.0
- What’s new in version 0.9
- What’s new in version 0.8
- What’s new in version 0.7
- What’s new in Version 0.6.1
- What’s new in Version 0.6
- What’s new in Version 0.5
- What’s new in Version 0.4
- Planned Future Development
- About NodePy

## 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.