$$\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

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

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