A new approach to the algebraic structures for integration methods

The analysis of compositions of Runge–Kutta methods involves manipulations of functions defined on rooted trees. Existing formulations due to Butcher, Hairer and Wanner, and Murua and Sanz-Serna, while equivalent, differ in details. The subject of the present paper is a new recursive formulation of the composition rules. This both simplifies and extends the existing approaches. Instead of using the order conditions based on trees, we propose the construction of the order conditions using a suitably chosen basis on the tree space. In particular, the linear structure of the tree space gives a representation of the C and D simplifying assumptions on trees which is not restricted to Runge–Kutta methods. A proof of the group structure of the set of elementary weight functions satisfying the D simplifying assumptions is also given in this paper.