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.     

Combinatorics of rooted trees and Hopf algebras

We begin by considering the graded vector space with a basis consisting of rooted trees, with grading given by the count of non-root vertices. We define two linear operators on this vector space, the growth and pruning operators, which respectively raise and lower grading; their commutator is the operator that multiplies a rooted tree by its number of vertices, and each operator naturally associates a multiplicity to each pair of rooted trees. By using symmetry groups of trees we define an inner product with respect to which the growth and pruning operators are adjoint, and obtain several results about the associated multiplicities.

Now the symmetric algebra on the vector space of rooted trees (after a degree shift) can be endowed with a coproduct to make a Hopf algebra; this was defined by Kreimer in connection with renormalization. We extend the growth and pruning operators, as well as the inner product mentioned above, to Kreimer's Hopf algebra. On the other hand, the vector space of rooted trees itself can be given a noncommutative multiplication: with an appropriate coproduct, this leads to the Hopf algebra of Grossman and Larson. We show that the inner product on rooted trees leads to an isomorphism of the Grossman-Larson Hopf algebra with the graded dual of Kreimer's Hopf algebra, correcting an earlier result of Panaite.

     

Combinatorial Hopf algebras from renormalization

In this paper we describe the right-sided combinatorial Hopf structure of three Hopf algebras appearing in the context of renormalization in quantum field theory: the non-commutative version of the Faà di Bruno Hopf algebra, the non-commutative version of the charge renormalization Hopf algebra on planar binary trees for quantum electrodynamics, and the non-commutative version of the Pinter renormalization Hopf algebra on any bosonic field.     

A noncommutative symmetric system over the Grossman-Larson Hopf algebra of labeled rooted trees

In this paper, we construct explicitly a noncommutative symmetric ( CS) system over the Grossman-Larson Hopf algebra of labeled rooted trees. By the universal property of the CS system formed by the generating functions of certain noncommutative symmetric functions, we obtain a specialization of noncommutative symmetric functions by labeled rooted trees. Taking the graded duals, we also get a graded Hopf algebra homomorphism from the Connes-Kreimer Hopf algebra of labeled rooted forests to the Hopf algebra of quasi-symmetric functions. A connection of the coefficients of the third generating function of the constructed CS system with the order polynomials of rooted trees is also given and proved.     

Integrable Renormalization II: The General Case

We extend the results we obtained in an earlier work [1]. The cocommutative case of ladders is generalized to a full Hopf algebra of (decorated) rooted trees. For Hopf algebra characters with target space of Rota-Baxter type, the Birkhoff decomposition of renormalization theory is derived by using the double Rota-Baxter construction, respectively Atkinsons theorem. We also outline the extension to the Hopf algebra of Feynman graphs via decorated rooted trees.submitted 16/03/04, accepted 09/09/04This revised version was published online in May 2005 with correction to the addresses.     

The Hopf Algebra of Rooted Trees in Epstein-Glaser Renormalization

We show how the Hopf algebra of rooted trees encodes the combinatorics of Epstein-Glaser renormalization and coordinate space renormalization in general. In particular, we prove that the Epstein-Glaser time-ordered products can be obtained from the Hopf algebra by suitable Feynman rules, mapping trees to operator-valued distributions. Twisting the antipode with a renormalization map formally solves the Epstein-Glaser recursion and provides local counterterms due to the Hochschild 1-closedness of the grafting operator B₊.submitted 29/03/04, accepted 01/06/04     

An improvement of the numerical stability results for nonlinear neutral delay-integro-differential equations

This paper deals with stability of the extended Runge–Kutta methods for nonlinear neutral delay-integro-differential equations. The stability results in the reference [Y. Yu, L. Wen, S. Li, Nonlinear stability of Runge–Kutta methods for neutral delay integro-differential equations, Appl. Math. Comput. 191 (2007) 543–549] are improved. With this improvement, several new numerical stability criteria are obtained, it is proven that the extended Runge–Kutta methods are globally and asymptotically stable under the suitable conditions.     

Commutative combinatorial Hopf algebras

We propose several constructions of commutative or cocommutative Hopf algebras based on various combinatorial structures and investigate the relations between them. A commutative Hopf algebra of permutations is obtained by a general construction based on graphs, and its noncommutative dual is realized in three different ways, in particular, as the Grossman–Larson algebra of heap-ordered trees. Extensions to endofunctions, parking functions, set compositions, set partitions, planar binary trees, and rooted forests are discussed. Finally, we introduce one-parameter families interpolating between different structures constructed on the same combinatorial objects.     

Subquadrature expansions for TSRK methods

The representation of order conditions for general linear methods formulated using an algebraic theory by Butcher, and the alternative using B-series by Hairer and Wanner for treating vector initial value problems in ordinary differential equations are well-known. Each relies on a recursion over rooted trees; yet tractable forms—for example, those which may be solved to yield particular methods—often are obtained only after extensive computation. In contrast, for Runge–Kutta methods, tractable forms have been used by various authors for obtaining methods. Here, the corresponding recursion formula for two-step Runge–Kutta methods is revised to yield tractable forms which may be exploited to derive such methods and to motivate the selection of efficient algorithms in an obvious way. The new recursion formula is utilized in a MAPLE code.     

Comparison of Hopf algebras on trees

Several Hopf algebra structures on vector spaces of trees can be found in the literature (cf. [10], [8], [2]). In this paper, we compare the corresponding notions of trees, the multiplications and comultiplications. The Hopf algebras are connected graded or, equivalently, complete Hopf algebras. The Hopf algebra structure on planar binary trees introduced by Loday and Ronco [10] is noncommutative and not cocommutative. We show that this Hopf algebra is isomorphic to the noncommutative version of the Hopf algebra of Connes and Kreimer [3]. We compute its first Lie algebra structure constants in the sense of [7], and show that there is no cogroup structure compatible with the Hopf algebra on planar binary trees.     

Experiments with a New Fifth Order Method

Almost Runge–Kutta methods were introduced to obtain many of the advantages of Runge–Kutta methods without their disadvantages. We consider the construction of fourth order methods of this type with a special choice of the free parameters to ensure that, at least for constant stepsize, order 5 behaviour is achieved. It is shown how this can be extended to variable stepsize.     

The tree and forest spaces with applications to initial-value problem methods

Tree and forest spaces, which are at the heart of the theory of Runge–Kutta methods, are formulated recursively, and it is shown that the forest space is an algebra. To obtain order conditions in a systematic manner, Banach algebras are introduced to generate both the elementary weights for a general Runge–Kutta method and the corresponding quantities based on the Picard integral. To connect these two concepts, the Picard integral is written as the limiting case of an s-stage Runge–Kutta method, equivalent to s steps of the Euler method, as s tends to infinity. This approach makes it possible to make direct use of the tree space without going over to the dual space. By choosing linear combinations of trees, appropriate to a particular application, it is shown how to obtain alternative ways of writing the order conditions. This leads to a simpler and more direct derivation of particular methods.     

Explicit General Linear Methods with Inherent Runge–Kutta Stability

A class of general linear methods is derived for application to non-stiff ordinary differential equations. A property known as inherent Runge–Kutta stability guarantees the stability regions of these methods are the same as for Runge–Kutta methods. Methods with this property have high stage order which enables asymptotically correct error estimates and high order interpolants to be computed conveniently. Some preliminary numerical experiments are given comparing these methods with some well known Runge–Kutta methods.     

Passive Runge–Kutta Methods—Properties, Parametric Representation, and Order Conditions

In this paper, a new class of Runge–Kutta methods is introduced. Some basic properties of this subgroup of algebraically stable methods are presented and a complete parametric representation is given. Necessary and sufficient order conditions for lower order methods as well as sufficient order conditions for higher order methods are derived yielding a significantly reduced number of conditions when compared with general Runge–Kutta methods. Design examples conclude this paper.     

Unconditionally Stable General Linear Methods for Ordinary Differential Equations

We describe a new approach to the construction of general linear methods with inherent Runge–Kutta stability properties, which are unconditionally stable for any stepsize pattern. These methods permit an accurate, efficient and reliable estimation of the local discretization errors. This is confirmed by numerical experiments.     

Dissipativity of Runge–Kutta methods for neutral delay integro-differential equations

This paper is concerned with the numerical dissipativity of a class of nonlinear neutral delay integro-differential equations. The dissipativity results are obtained for algebraically stable Runge–Kutta methods when they are applied to above problems.     

Strong A-Acceptability for Rational Functions

In this note a simple characterization of 'strong' A-acceptability for a rational function is given. This fact meets applications in stability theory for Runge–Kutta or semi-implicit methods. In particular, strongly A-stable methods give (long time) stable integrations on autonomous differential systems possessing a semi-stable equilibrium.     

Runge–Kutta methods for first-order periodic boundary value differential equations with piecewise constant arguments

In this paper we deal with the numerical solutions of Runge–Kutta methods for first-order periodic boundary value differential equations with piecewise constant arguments. The numerical solution is given by the numerical Green’s function. It is shown that Runge–Kutta methods preserve their original order for first-order periodic boundary value differential equations with piecewise constant arguments. We give the conditions under which the numerical solutions preserve some properties of the analytic solutions, e.g., uniqueness and comparison theorems. Finally, some experiments are given to illustrate our results.     

Renormalization as a functor on bialgebras

The Hopf algebra of renormalization in quantum field theory is described at a general level. The products of fields at a point are assumed to form a bialgebra B and renormalization endows T(T(B)⁺), the double tensor algebra of B, with the structure of a noncommutative bialgebra. When the bialgebra B is commutative, renormalization turns S(S(B)⁺), the double symmetric algebra of B, into a commutative bialgebra. The usual Hopf algebra of renormalization is recovered when the elements of S¹(B) are not renormalized, i.e., when Feynman diagrams containing one single vertex are not renormalized. When B is the Hopf algebra of a commutative group, a homomorphism is established between the bialgebra S(S(B)⁺) and the Faà di Bruno bialgebra of composition of series. The relation with the Connes-Moscovici Hopf algebra is given. Finally, the bialgebra S(S(B)⁺) is shown to give the same results as the standard renormalization procedure for the scalar field.     

Faà di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations

We consider the combinatorial Dyson-Schwinger equation X=B⁺(P(X)) in the non-commutative Connes-Kreimer Hopf algebra of planar rooted trees HNCK, where B⁺ is the operator of grafting on a root, and P a formal series. The unique solution X of this equation generates a graded subalgebra AN,P of HNCK. We describe all the formal series P such that AN,P is a Hopf subalgebra. We obtain in this way a 2-parameters family of Hopf subalgebras of HNCK, organized into three isomorphism classes: a first one, restricted to a polynomial ring in one variable; a second one, restricted to the Hopf subalgebra of ladders, isomorphic to the Hopf algebra of quasi-symmetric functions; a last (infinite) one, which gives a non-commutative version of the Faà di Bruno Hopf algebra. By taking the quotient, the last class gives an infinite set of embeddings of the Faà di Bruno algebra into the Connes-Kreimer Hopf algebra of rooted trees. Moreover, we give an embedding of the free Faà di Bruno Hopf algebra on D variables into a Hopf algebra of decorated rooted trees, together with a non-commutative version of this embedding.