Jim and John 1970

$$\def\tree{\!\text{ t }\!} \def\h{\!\!\!\!} \def\m{\;\;} \def\g{\!\!} \def\C{\!\!&\!} \def\ss{\sqrt5}\def\f#1#2{\!\!\!\frac{#1\ss}{#2}\!\!} \def\s{\;\;} \def\C{\!\!&\!\!}$$

Our first B-series program

John Butcher and Jim Verner

The first day of January 1970 was an important day in our lives. After several days of discussion and shared interaction, John, who with his family was staying with Jim at Queen’s University, Kingston, Ontario, proposed that we might work on a certain project. As we realised later, that day was also an auspicious day in the history of computing: it was the start of the Unix Epoch.

To us that day was, as far as we were aware, the start of the computer analysis of Runge–Kutta methods era.

We started with the assumption that an $s$ stage Runge–Kutta method would be given, and defined by a tableau \[ \begin{array}{c|c} c & A\\ \hline & b^T \end{array}. \] To have order $p$, the method must satisfy a family of algebraic equations of the form $\Phi(\tree) = 1/\tree!$, [J.C. Butcher, 2021] where $\tree$ ranges over all rooted trees such that $|\tree|\le p$. In many early publications, the notation $\gamma(\tree)$ was used in place of $\tree!$.

Our project was to write a program which would read in the coefficients of a given explicit or implicit Runge–Kutta tableau, and generate and test all the required order conditions. It would then print out the value of $\Phi(\tree) -1/\tree!$ for each of the required trees. If these error values were zero to within computer accuracy, we would assess the method as having the order determined as if these nearly zero values were exactly zero.

When we arrived at the Queen's Department of Mathematics, we realised that there was no computing service available on this public holiday. It was one of the early days of time-sharing, using connections over telephone lines, and Jim was able to get onto a service at Laval University in Quebec. We received a friendly New Year greeting from the operator in Laval, and then turned to the task at hand.

We each understood the structure required for our program, and we rapidly developed a workable scheme for what we expected would be a successful collaboration. John sketched out the sequence of commands on a chalk-board, using the Algol language, and Jim typed a translation into the system using the APL language.

An exact copy of our original APL code is reproduced here. An implementation in Maple is the subject of another story. John: add link

APL  code

The present story, in addition to commemorating the day we wrote this program, attempts to provide some context. In the case of Jim, the context is the derivation of 11 stage methods of order 8 Runge–Kutta methods, First eighth order [J.H. Verner, 1969], [G.J. Cooper and J.H. Verner, 1972] and, in the case of John, the context was his early work on the algebraic approach to Runge–Kutta methods leading to The birth of B-series [J.C. Butcher, 1972].

[J.C. Butcher, 1963]
Coefficients for the study of Runge–Kutta integration processes, J. Austral. Math. Soc., 3, 185–201.
[J.C. Butcher, 1964]
On Runge–Kutta processes of high order, J. Austral. Math. Soc., 4, 179–194.
[J.C. Butcher, 1966]
On the convergence of numerical solutions to ordinary differential equations, Math. Comp., 20, 1–10.
[J.C. Butcher, 1969]
The effective order of Runge–Kutta methods, Conf. on the Numerical Solution of Differential Equations, Dundee, Springer–Verlag, 133–139.
[J.C. Butcher, 1972]
An algebraic theory of integration methods, Math. Comp., 26, 79–106.
[J. C. Butcher, 2021]
B-Series: Algebraic analysis of numerical methods, Springer–Verlag , 310 pages.
G.J. Cooper and J.H. Verner, 1972]
Some explicit Runge–Kutta methods of high order, SIAM J. Numer. Anal., 9, 389–405.
[A.R. Curtis, 1970]
An eighth order Runge–Kutta process with eleven function evaluations per step, Numer. Math., 16, 268–277.
[James H. Verner, 1969]
Numerical Solution of Differential Equations, Ph.D. Thesis, Computing Science, University of Edinburgh, Scotland, 187 pages.
[J.H. Verner, 1976]
The derivation of high order Runge–Kutta methods, Univ. of Auckland, New Zealand, Report No. 93, 27 pages.
[J.H. Verner, 1994]
Strategies for deriving new Runge–Kutta pairs. Annals of Numerical Mathematics, 1, 225–244.

$\to$ The birth of B-series
$\to$ The first eighth order methods
$\to$ B-series book