Book review: “B-Series: Algebraic Analysis of Numerical Methods” by John C. Butcher

The algebraic analysis of numerical methods is driven along a bridge matching numerical analysis, graph theory, group theory, differentiation of vector fields, and so on. The result of the wise union of these aspects is an effective and elegant theory that is useful for investigating meaningful features of numerical methods for differential equations. One of the pioneering sources of this theory is the brilliant and ingenious work of John C. Butcher. He has authored a remarkable number of seminal contributions to the founding, establishment and development of the modern theory of Runge–Kutta methods and its subsequent extensions.

A building block for the algebraic analysis of numerical methods and, in particular, of their order of convergence, is the connection between rooted trees and the differentiation of vector fields. Such a link lies at the basis of Butcher’s theory and its precursors⁠¹⁠Historical aspects have been described in detail, for instance, in the paper by R. McLachlan et al., Asia Pacific Math. Newsletter 7(1), 1–11 (2017)., such as Arthur Cayley (1821–1895) and Robin H. Merson (1921–1992), a scientist at the Royal Aircraft Establishment, who became popular for his involvement in the computations of an accurate orbit for Sputnik 1, launched in 1957. In the same year, Butcher attended the talk by Merson at the conference ”Data Processing and Automatic Computing Machines” held in Salisbury, South Australia, where Merson described the one-to-one correspondence between derivatives and rooted trees. The full theory will only be provided later by Butcher, but it is worth mentioning that Cayley introduced trees with the same purpose as in Butcher theory (namely, to understand and effectively represent the interaction of vector fields repeatedly applied to one another), and then for one century this aspect was totally forgotten in the literature, and reconsidered with effectiveness only when the theory of numerical methods was established with rigor.

Other two building blocks for the algebraic analysis of numerical methods, allowing to detect and elegantly prove properties of numerical methods for differential problems, are well described in the book under review, namely

• Butcher series (in short, B-series), allowing to represent both exact and numerical solutions to a differential problem in terms of series expansions whose coefficients are functions of rooted trees of a prescribed order;

• the Butcher group (in short, B-group), obtained by equipping the set of homomorphisms of the Hopf algebra of rooted trees into the set of real numbers with an operation of composition of mappings. As mentioned above, the analysis of the group properties of this algebraic structure allows to treat accuracy properties of numerical methods in a very elegant and effective way.

An immediate benefit of the B-series/B-group theory (originally developed for Runge–Kutta methods and subsequently extended to multivalue numerical methods) is that one can achieve a minimal number of conditions for the construction of high-order methods. However, confining the effectiveness and importance of this theory to the sole construction of efficient numerical methods would be somewhat reductive. Indeed, as pointed out by A. Connes and D. Kreimer, the Butcher group had arisen independently in their own works on renormalization in quantum field theory.

Characterized by a very clear and self-contained style, the monograph under review is an excellent contribution, consisting of seven chapters, enriched by exercises and their solutions, study notes, and open-ended projects. Chapter 1 provides a collection of topics useful to contextualize the mathematical problem (i.e., systems of differential equations), its well-posedness, and the ideas behind multistage discretizations, namely Runge–Kutta and multivalue numerical methods. The basic accuracy requirements of consistency, stability and convergence are also recalled, as well as some of the topics more widely explained in later chapters. Chapter 2 contains a comprehensive presentation of trees, forests, and operations on them. The exposition is focused on the basic terminology for trees and forests, their graphical structures, the operations useful to build up trees starting from a single node, how partitions act on trees, the ideas of evolution, stump and antipode, with a close relationship, in several cases, with Hopf-algebra terminology.

The core material of the treatise, oriented to the way trees and forests are useful in the numerics for differential equations, starts in Chapter 3, where the notion of B-series (and composition of B-series) is introduced in detail. B-series allow to write the Taylor expansions of the two mappings describing the exact and numerical solutions, respectively, to the problem via elementary differentials, which can be effectively represented in terms of rooted trees. Chapter 4 relates B-series to the algebraic analysis of numerical methods, with particular reference to the properties of the B-group for the analysis of Runge–Kutta methods, explained in depth in Chapter 5. Specifically, the author describes a very elegant and effective way to provide order conditions for Runge–Kutta methods, analyzing a wide selection of explicit and implicit schemes. The treatise moves, through Chapter 6, to the family of general linear methods, characterized by a combined multivalue and multistage strategy, and explaining the way the B-series approach effectively applies to these methods. Chapter 7 gives interesting insights regarding the application of the B-series approach to the development and analysis of numerical schemes useful for solving Hamiltonian problems, in the spirit of the so-called geometric numerical integration, here oriented to analyzing symplectic Runge–Kutta methods, as well as developing multivalue numerical schemes with near-preservation of invariants.

The author uses a very clear writing style, and each chapter contains an outline and summary, many examples, and a final section of way forward, giving a perspective how the treatise goes on. The approach is self-contained and different levels of in-depth analysis intersect, making the book ideal both for advanced courses of numerical analysis and as a reference monograph in research. Moreover, the large set of applications involving B-series makes the book under review a key reference for all scientists who are effectively using computational modelling for evolutive problems in their work.

John C. Butcher, B-Series: Algebraic Analysis of Numerical Methods, Springer, 2021, 320 pages, Hardback ISBN 978-3-030-70955-6, eBook ISBN 978-3-030-70956-3

Raffaele D’Ambrosio is full professor of numerical analysis at the Department of Information Engineering and Computer Science and Mathematics at the University of L’Aquila and former Fulbright Research Scholar. His research mostly focuses on deterministic and stochastic geometric numerical integration as well as the study of long-time behavior of numerical methods for functional problems. raffaele.dambrosio@univaq.it

1. ¹

   Historical aspects have been described in detail, for instance, in the paper by R. McLachlan et al., Asia Pacific Math. Newsletter 7(1), 1–11 (2017).