Butcher group

In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Hairer & Wanner (1974), is an infinite-dimensional Lie group first introduced in numerical analysis to study solutions of non-linear ordinary differential equations by the Runge–Kutta method. It arose from an algebraic formalism involving rooted trees that provides formal power series solutions of the differential equation modeling the flow of a vector field. It was Cayley (1857), prompted by the work of Sylvester on change of variables in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Hairer & Wanner (1974), is an infinite-dimensional Lie group first introduced in numerical analysis to study solutions of non-linear ordinary differential equations by the Runge–Kutta method. It arose from an algebraic formalism involving rooted trees that provides formal power series solutions of the differential equation modeling the flow of a vector field. It was Cayley (1857), prompted by the work of Sylvester on change of variables in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. Connes & Kreimer (1999) pointed out that the Butcher group is the group of characters of the Hopf algebra of rooted trees that had arisen independently in their own work on renormalization in quantum field theory and Connes' work with Moscovici on local index theorems. This Hopf algebra, often called the Connes-Kreimer algebra, is essentially equivalent to the Butcher group, since its dual can be identified with the universal enveloping algebra of the Lie algebra of the Butcher group. As they commented: A rooted tree is a graph with a distinguished node, called the root, in which every other node is connected to the root by a unique path. If the root of a tree t is removed and the nodes connected to the original node by a single bond are taken as new roots, the tree t breaks up into rooted trees t1, t2, ... Reversing this process a new tree t = can be constructed by joining the roots of the trees to a new common root. The number of nodes in a tree is denoted by |t|. A heap-ordering of a rooted tree t is an allocation of the numbers 1 through |t| to the nodes so that the numbers increase on any path going away from the root. Two heap orderings are equivalent, if there is an automorphism of rooted trees mapping one of them on the other. The number of equivalence classes of heap-orderings on a particular tree is denoted by α(t) and can be computed using the Butcher's formula: where St denotes the symmetry group of t and the tree factorial is defined recursively by