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 1972], Hairer and Wanner 1974], and Murua and Sanz-Serna 1999], 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 is this paper.