Formal series and numerical integrators: some history and some new techniques

Abstract

This paper provides a brief history of B-series and the associated Butcher group and presents the new theory of word series and extended word series. B-series (Hairer and Wanner 1976) are formal series of functions parameterized by rooted trees. They greatly simplify the study of Runge-Kutta schemes and other numerical integrators. We examine the problems that led to the introduction of B-series and survey a number of more recent developments, including applications outside numerical mathematics. Word series (series of functions parameterized by words from an alphabet) provide in some cases a very convenient alternative to B-series. Associated with word series is a group G of coe cients with a composition rule simpler than the corresponding rule in the Butcher group. From a more mathematical point of view, integrators, like Runge-Kutta schemes, that are a ne equivariant are represented by elements of the Butcher group, integrators that are equivariant with respect to arbitrary changes of variables are represented by elements of the word group G.