On the Hopf Algebraic Structure of Lie Group Integrators

A commutative but not cocommutative graded Hopf algebra H_N, based on ordered (planar) rooted trees, is studied. This Hopf algebra is a generalization of the Hopf algebraic structure of unordered rooted trees H_C, developed by Butcher in his study of Runge-Kutta methods and later rediscovered by Connes and Moscovici in the context of noncommutative geometry and by Kreimer where it is used to describe renormalization in quantum field theory. It is shown that H_N is naturally obtained from a universal object in a category of noncommutative derivations and, in particular, it forms a foundation for the study of numerical integrators based on noncommutative Lie group actions on a manifold. Recursive and nonrecursive definitions of the coproduct and the antipode are derived. The relationship between H_N and four other Hopf algebras is discussed. The dual of H_N is a Hopf algebra of Grossman and Larson based on ordered rooted trees. The Hopf algebra H_C of Butcher, Connes, and Kreimer is identified as a proper Hopf subalgebra of H_N using the image of a tree symmetrization operator. The Hopf algebraic structure of the shuffle algebra H_Sh is obtained from H_N by a quotient construction. The Hopf algebra H_P of ordered trees by Foissy differs from H_N in the definition of the product (noncommutative concatenation for H_P and shuffle for H_N) and the definitions of the coproduct and the antipode, however, these are related through the tree symmetrization operator.