The birth of B-series

$$\def\tree{\text{t} }$$

The birth of B-series

$\quad\ \ $John Butcher

This is a personal story. It is my recollection of what I was trying to do in 1970 and in the few years before and after 1970.

Following [J.C. Butcher, 1963] , I came to appreciate something that now seems obvious: Runge–Kutta methods have a natural group structure which is both worthy of mathematical study and useful for the practical analysis of numerical methods. My attempt to put these ideas into writing led, in 1968, to a manuscript which seemed to be unpublishable although it was widely distributed as a departmental report and became the subject of a talk I gave from place to place in Europe and North America. Hans Stetter must have felt that there was something to it and I believe, without any real evidence, that he had an influence in getting it finally accepted [J.C. Butcher, 1972].

As a consequence of the group structure, "effective order" [J.C. Butcher, 1969], also known as "conjugate order" becomes a real possibility.

Suppose $R_h$ and $S_h$ are the mappings associated with two Runge–Kutta methods, $M$ and $N$, so that \( y_2 = R_h y_1 = R_h S_h y_0, \) is the result of operating on $y_0$ with $S_h$ and $R_h$ in sequence, where $y_1=S_h y_0$. Also write $S_h^{-1}$ so that $y_0=S_h^{-1} y_1$. The mapping $S_h^{-1} R_h S_h$ is conjugate to $R_h$. If $M$ and $N$ are represented by tableaux, then $NMN^{-1}$ is a tableau which represents $S_h^{-1} R_h S_h$.

Definition $M$ has effective order $p$ if $N$ exists such that $NMN^{-1}$ has order $p$.

It is known [J.C. Butcher, 1964] that no method exists with $s$ stages and order $p$ if $s=p>4$. But methods exist with $s=5$ and effective order $5$.

In the late 1960s, I met a famous North American numerical analyst and I hoped he would not only be interested but even a little encouraging. When I tried to tell him about effective order, he told me it wouldn't work even before I had actually told him anything.

But it does work!

I was not able to take part in the bienniel Dundee conference held in the end of June 1969, but my talk was presented for me by Jack Lambert. From what I heard from other people, Jack gave an excellent performance and I am grateful to him for this. My talk later appeared in the proceedings of that conference [J.C. Butcher, 1969].

An account of my visit to Queen's University (Kingston) and working with Jim Verner on a program to verify the orders of Runge–Kutta methods is given elsewhere Our first B-series program. Later in 1970, I visited the UK and continental Europe for the first time and gave talks about the algebaic theory.

In my final visit, to the University of Innsbruck, I met Ernst Hairer and Gerhard Wanner. They would, soon afterwards, write their important papers [E. Hairer and G. Wanner, 1973], [E. Hairer and G. Wanner, 1974], and my own paper [J.C. Butcher, 1972] appeared in print.

Thus, B-series was born!

[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, 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],
algebraic theory of integration methods, Math. Comp., 26, 79–106.
[J.C. Butcher, 2021],
B-Series: An algebraic analysis of numerical methods, Springer–Verlag , 310 pages.
[E. Hairer and G. Wanner, 1973],
Multistep-multistage-multiderivative methods for ordinary differential equations. Computing 11, 287–303.
[E. Hairer and G. Wanner, 1974],
On the Butcher group and general multi-value methods, Computing, 13, 1–15.

$\to$ Jim and John 1970
$\to$ Our first B-series program
$\to$ B-series book