{'fraction_non_alphanumeric': 0.05355886679030505, 'fraction_numerical': 0.010615847029481358, 'mean_word_length': 3.7079632696071054, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Backward error analysis and the substitution law for Lie group integrators

Butcher series are combinatorial devices used in the study of numerical methods for differential equations evolving on vector spaces. More precisely, they are formal series developments of differential operators indexed over rooted trees, and can be used to represent a large class of numerical methods. The theory of backward error analysis for differential equations has a particularly nice description when applied to methods represented by Butcher series. For the study of differential equations evolving on more general manifolds, a generalization of Butcher series has been introduced, called Lie--Butcher series. This paper presents the theory of backward error analysis for methods based on Lie--Butcher series.


Introduction
A fundamental tool in the field of numerical integration of ordinary differential equations on R n is the theory of Butcher series (B-series). These are formal series expansions of vector fields and flows, expanded over the set of rooted trees. Many numerical methods can be formulated in terms of B-series, and they can be used to, for example, study order theory, structure preserving properties of integrators, backward error analysis and modified vector fields [3,17,8,7,10,9,23]. In the more general setting of differential equations of the form y = F (y), y ∈ M, F : M → T M, where M is a (homogeneous) manifold and F a vector field on M , the role of B-series is played by the Lie-Butcher series (LB-series) [28,22,23]. Considering the importance of classical B-series, LB-series are objects of great interest. The B-series are based on the elementary differentials associated to vector fields, and these can be constructed as homomorphisms from the free pre-Lie algebra (or Vinberg algebra) into the pre-Lie algebra of vector fields [5]. In the setting of LB-series we get a similar picture, only now the pre-Lie algebras are replaced by the so-called post-Lie algebras, defined in [34,27].
In the present paper we will explore the substitution law for Lie-Butcher series, formulated in the language of enveloping algebras of post-Lie algebras: the D-algebras of [28]. Once the substitution law is understood, it can be applied to backward error analysis. The basic idea of backward error analysis is to interpret the numerical solution of a differential equation as the exact solution of a modified equation, and then use this equation to study the numerical method. Analogous to classical backward error analysis (as developed in [16,17,8,5]), its generalization to the Lie group setting has a particularly nice description for methods based on Lie-Butcher series.
Note that the construction of series expansions in the present paper is purely formal: there will be no study of convergence. This separation between the algebraic and the analytic framework for backward error analysis is also present in the setting of B-series, where the main algebraic references are [17,8,5,9] and the analytic references are [1,32,17]. An analytic study of backward error analysis for Lie group methods can be found in [14].
The present study of the backward error and substitution law for Lie group integrators is interesting from a purely algebraic point of view, as this work provides an explicit description of automorphisms of post-Lie algebras. From a numerical point of view, the theory has several applications. The algebraic structures of backward error analysis is important in the analysis of numerical integration algorithms. Additionally, in the case of classical B-series, such algebraic techniques have recently been applied more directly as a computational tool [8]. Similar techniques in the setting of Lie group integrators is a promising approach to structure preserving integration of problems of computational mechanics, such as Lie-Poisson systems.

Lie-Butcher series
In this section we will define D-algebras, and show how they give rise to Lie-Butcher series. In the next section we will apply them to the study of the substitution law and backward error analysis for Lie group integrators on manifolds.

Trees and D-algebras
Ordered rooted trees and forests. Some basic definitions follow. For a more comprehensive introduction to the combinatorics of trees applied to numerical integration, see [4] or [19]. Let OT denote the alphabet of all ordered (i.e. planar) rooted trees:

.}.
The root is the bottom vertex and we consider the trees to grow upwards from the root. The trees being ordered implies that = . This is different from classical B-series theory, where the order of the branches is of no significance. Let OF denote the set of ordered forests, i.e. all possible empty and non-empty words written with letters from the alphabet OT: where I denotes the empty word. On OF we define the concatenation product ω 1 , ω 2 → ω 1 ω 2 , which creates a longer word by joining ω 1 and ω 2 end-to-end. This is an associative, non-commutative product with unit I. Let B + : OF → OT denote the operation of adding a root to a word, e.g.
All of OF is generated from I by concatenation and adding roots. The order of a forest, |ω| = |τ 1 . . . τ k |, is defined by the recursion |I| = 0, |τ 1 . . . τ k | = |τ 1 | + · · · + |τ k |, |B + ω| = |ω| + 1, i.e. the order counts the number of vertices in a forest. Let k be a field of characteristic 0, e.g. k = R or k = C. The k-vector space of all finite k-linear combinations of elements in OF is the non-commutative polynomial ring over OT 1 , denoted by N = k OT . The k-vector space of infinite linear combinations of OF is N * = k OT . N * is the dual space of N , with the dual pairing ·, · : N * × N → k defined such that the words in OF form a orthonormal basis: ω 1 , ω 2 = 0 if ω 1 = ω 2 , and ω, ω = 1. Thus for a ∈ N * we have a(ω) = a, ω and a = ω∈OF a(ω)ω. In the latter sum we understand N * as the projective limit N * = lim ← − N k , where N k = span{ω ∈ OF : |ω| ≤ k}. An infinite a ∈ N * is uniquely defined by its finite projections a k ∈ N k for all k ∈ Z, where a k = |ω|≤k a(ω)ω is the orthogonal projection of a onto the subspace N k ⊂ N . Remark 2.1. In many applications it is necessary to generalize to spaces built from trees with colored vertices. The theory extends from the above presentation with only minor modifications. Let C be a (finite or infinite) set of colors. A coloring of a tree or a forest is a map from its vertices to C. Let OT C and OF C denote colored trees and forests. For each c ∈ C we have the operation B + c : OF C → OT C creating a tree by adding a root of color c to a word. We identify C ⊂ OT C ⊂ OF C as the subset of single vertex trees. In the colored context we permit more general gradings | · | on OT C . We allow the assignment of arbitrary positive integer weights |c| ∈ N to the single vertex trees C ⊂ OT C , extended to OF C by |τ 1 . . . τ k | = |τ 1 | + · · · + |τ k | and |B + c ω| = |ω| + |c|. The definitions of finite and infinite linear combinations of forests N C = k OT C and N * C = k OT C are similar to the uni-color case.
Definition 2.2. The left grafting product · · : N ⊗ N → N is defined recursively as follows: let τ ∈ OT and ω, ω 1 , ω 2 ∈ OF. Then The product is extended to all of N and N * by linearity and projective limits.
It is clear that if we write ω 1 [ω 2 ] for ω 1 ω 2 , we have the following structure on N : 28]). Let A be a unital associative algebra with product f, g → f g, unit I and equipped with a non-associative composition (.) [.] : Write D(A) for the set of all f ∈ A such that f [·] is a derivation: Then A is called a D-algebra if for any derivation f ∈ D(A) and any g ∈ A we have The free D-algebra. We note that a morphism   28]). Let OT be planar trees decorated with colors C. The vector space N = R OT is a free D-algebra over C. That is, for any D-algebra A and any map ν : C → D(A) there exists a unique D-algebra homomorphism F ν : N → A such that F ν (c) = ν(c) for all c ∈ C.
We will see that based on this result we can construct elementary differentials and Lie-Butcher series for Lie group integrators, and also define the substitution law. To achieve this we utilize D-algebra structure of differential operators on manifolds [28].
The D-algebra of differential operators. There is a D-algebra based on the space of vector fields 2 on the manifold M . Consider the space C ∞ (M, g) =: g M , where g ⊂ X M is a Lie subalgebra of the set of all vector fields on M . For Ψ ∈ g M and V ∈ g, the Lie derivative V is a scalar function 3 . The Lie derivative gives rise to differential operators of higher degrees through concatenation: the concatenation of V, W ∈ g is a second-degree differential ]. The C ∞ (M, R)-module of all differential operators, including the ones of higher degree, and the degree zero operator spanned by the identity operator I, is called the universal enveloping algebra U (g) of g. We extend the structure to the space C ∞ (M, U (g)) =: U (g) M as follows: for f, g ∈ U (g) M , f [g] ∈ U (g) M is defined by and f g ∈ U (g) M is defined as f g(p) := f (p)g(p).
The latter operation is called the frozen composition of f and g. For two vector fields f and g written in terms of the standard coordinate frame {∂/∂x i }, the operations take the following form: The operations (3) and (4) endows the space U (g) M with the structure of a D-algebra, where the derivations are the vector fields in g M : Lemma 2.6. Let f ∈ g M and g, h ∈ U (g) M . Then Hence U (g) M is a D-algebra.
The composition of f and g as differential operators, defined by (f g) ], is called non-frozen composition. 4 Post-Lie algebras. The theory of Lie-Butcher series can be reformulated in terms of post-Lie algebras. These were first studied in the setting of operads by Vallette [34], and also by the authors in [27]. Our main motivation for the construction of post-Lie algebras was their relation to the D-algebras defined above, which are universal enveloping algebras of post-Lie algebras.

Lie-Butcher series
Classical B-series. Recall (see e.g. [17]) that a B-series is a (formal) series indexed over the set NT of non-planar rooted trees (i.e. trees without any ordering of the branches) and can for a vector field f be written as Here σ(τ ) is the symmetry factor for τ ∈ NT, and a is a map a : NT → R. The map F f (τ ) : R n → R n is the elementary differential of the tree τ , obtained recursively from f and its derivatives: where τ = B + (τ 1 , . . . τ m ) and f (m) is the mth derivative of the vector field. The parameter h represents the step-size of the numerical method giving rise to the B-series.
LB-series. We will consider a more general setting: that of differential equations evolving on manifolds. Let M be a manifold and X M the Lie algebra of vector fields F : The fundamental assumption for numerical Lie group integrators is the existence of a frame on T M , defined as a finite number of vector fields {E 1 , E 2 , . . . , E m } spanning the tangent space T p M at each point p ∈ M . The frame is allowed to be overdetermined. It generates a Lie algebra g, and it is assumed that flows of vector fields in g can be computed exactly [25,31]. Any vector field F : M → T M can be written as F (p) = a i E i (p). We will study vector fields of the form We say that f p has coefficients frozen relative to the frame. In other words, to each such F ∈ X M there is an associated f ∈ g M so that F (p) = f p · p, where f p · p denotes evaluation of f p in p. We will often refer to such f ∈ g M as vector fields.
The general differential equation (1) can now be written as The Lie-Butcher series are expansions over OT associated to integrators of this equation, just as B-series are associated to differential equations expressing the flow of vector fields in R n . The non-commutativity of combining vector fields is reflected in the planarity of the trees in OT. Now we can construct the elementary differentials needed to define Lie-Butcher series. As in the classical case they can be expressed recursively by a function F based on trees.
Definition 2.7. The elementary differentials associated to a vector field f : M → g is the Dalgebra morphism F f : N → U (g) M we get from Proposition 2.5 by associating the tree to f (i.e. C = { } and ν : → f in Proposition 2.5). Hence F f is defined by When the vector field f is clear from the context we will occasionally write F instead of F f .
For a vector field f this can also be written as the commutative diagram where B f is the unique D-algebra homomorphism given by Proposition 2.5.
Remark 2.9. By coloring the vertices of the trees vi a map ν we can define F and B for multiple vector fields. The elementary differentials F ν are still obtained from Proposition 2.5, but the set C will contain multiple colors.

Some algebraic constructions
Before we show how LB-series can be used to represent flows of vector fields on manifolds we must conduct a closer study of the space where the coefficients α live. To understand the various ways we can represent such flows it will also be helpful to look at some Lie idempotents, namely the eulerian and Dynkin idempotents (Section 2.3.2), and also certain non-commutative polynomials called Bell polynomials (Section 2.3.3). We will follow the presentation in [28] and [22].

It is well known that inserting a B-series
The product a · b on the set of maps a : OT → R with a(I) = 1 gives rise to a group, called the Butcher group [3,18]. This is the group of characters in a variant of the Connes-Kreimer Hopf algebra of renormalization [11,2]. A similar result holds for LB-series, where the Hopf algebra of Connes-Kreimer is replaced by a more general Hopf algebraic structure on the set of rooted trees. This Hopf algebra was introduced in [28]. See also [22,23]. Note first that the vector space R OT spanned by trees can be turned into a Hopf algebra by using concatenation as product and deshuffling as coproduct. The deshuffling coproduct ∆ Sh is results from requiring the trees to be primitive, and extending by concatenation: where τ , τ 1 , τ 2 are trees. The antipode is defined by and the unit η and counit by η(1) = I, and (I) = 1, (ω) = 0, for all ω ∈ OF \I. The vector space N = R OT can also be turned into an algebra using the shuffle product for τ 1 , τ 2 ∈ OT, ω 1 , ω 2 ∈ OF. 5 This algebra can be given the structure of a bialgebra in several different ways. We can equip it with the coproduct ∆ c : N → N ⊗ N given by deconcatenation of words: where ω = τ 1 · · · τ n . This results in the shuffle bialgebra, which equipped with the same antipode, unit and counit as the deshuffle Hopf algebra defines the shuffle Hopf algebra H Sh . 6 If we instead equip N with the coproduct ∆ N : N → N ⊗N defined recursively as ∆ N (I) = I⊗I and where τ ∈ OT, ω ∈ OF, we get another bialgebra H N . Here ¡· : N ⊗4 → N ⊗ N denotes shuffle on the left and concatenation on the right: ). An explicit description of the coproduct in terms of tree cuts can be found in Section 3.1 below, and in [28], where it was shown that ∆ N is the dual of the Grossman-Larson product and that H N forms a Hopf algebra. 7 This is the Hopf algebra governing composition of LB-series (Theorem 2.10).
To simplify the expressions we introduce a magmatic structure (i.e. the structure of a set equipped with a closed binary operation with no further relations) on OF. Additional details and motivation for the introduction of this structure can be found in Section 4. Let ω 1 , ω 2 be two elements of OF and define the operation × : OF × OF → OF by For example, This operation is magmatic, and the empty tree I freely generates all of OF. The operation is extended to N = R OT via linearity. If ω = v 1 × v 2 , ω = I, then we call v 1 the left part ω L of ω and v 2 the right part ω R . The shuffle of two elements of the magma can be defined as ω ¡ I = I ¡ ω = ω, and we notice that the coproduct in H N can be written as where ¡× now denotes shuffle on the left, magma operation on the right.
Characters and the composition of LB-series. Recall that a character of a Hopf algebra (H, ∆, ·) over a field k is an algebra morphism α : H → k, e.g. α(a · b) = α(a)α(b), and α(1 H ) = 1, where a, b ∈ H, and 1 H denotes the unit. The convolution product α * β of two characters is defined by H This gives the set of characters G(H) of H the structure of a group. In fact, the field k can be replaced by any commutative algebra A, giving rise to A-valued characters. Another type of character we will need later are the infinitesimal characters. An A-valued infinitesimal character is a linear map α : where µ A is the product in A and δ is the composition of the counit of H and the unit of A, δ = η A • . The characters and infinitesimal characters are connected via the exponential and logarithm, see e.g. [24]. The group structure of the characters in H N exactly corresponds to the composition of LBseries.
Theorem 2.10 ( [28]). The composition of two LB-series is again a LB-series: where * is the convolution product in H N . 6 Note that the concatenation deshuffling Hopf algebra is dual to the shuffle deconcatenation Hopf algebra. 7 Being a graded and connected bialgebra H N is automatically a Hopf algebra. A more direct argument, and formulas for the antipode, can be found in [28]

Lie idempotents
A Lie polynomial over an algebra A is an element of the smallest submodule of R A that is closed under the bracket [P, Q] := P Q − QP in R A . The Lie algebra of these polynomials is the free Lie algebra Lie(A) on A [33]. There are several important idempotent maps, called Lie idempotents, from R A to Lie(A).
Eulerian idempotent Let H be a commutative, connected and graded Hopf algebra. Consider End k (H) = Hom k (H, H) equipped with the convolution product * . Let Id ∈ End k (H) be the identity endomorphism and δ = η • ∈ End k (H) the unit of convolution.
where J = Id −δ. Letting Y (ω) = #(ω)ω denote the grading operator, where #(ω) is word length, it is known that the Dynkin idempotent Y −1 • D is an idempotent projection on Lie(A). As in [12], the Dynkin operator can be written as the convolution of the antipode S and the grading operator Y : D = S * Y . This description can be generalized to any graded, connected and commutative Hopf algebra H:

The non-commutative Bell polynomials
In [26] some non-commutative polynomials B n were introduced to express the Butcher order theory of Runge-Kutta methods on manifolds. In [22] it was observed that these polynomials were a noncommutative analogue of Bell polynomials, and that they could be used to study more general flows on manifolds. We recall their definition here. Let I = {d j } ∞ j=1 be an infinite alphabet in 1-1 correspondence with N + , and consider the free associative algebra D = R I with the grading given by |d j | = j and |d j1 · · · d j k | = j 1 + · · · + j k . Let ∂ : D → D be the derivation given by ∂(d i ) = d i+1 , linearity and the Leibniz rule ∂(ω 1 ω 2 ) = ∂(ω 1 )ω 2 + ω 1 ∂(ω 2 ) for all ω 1 , ω 2 ∈ I * . We let #(ω) denote the length of the word ω. The first few are We write B n,k := B n,k (d 1 , . . . , d n−k+1 ) for the part of B n consisting of the words of length k, e.g.
It is often useful to employ the polynomials Q n and Q n,k related to B n and B n,k by the following rescaling: These polynomials can be used to define an operator Q on any graded Hopf algebra H. Let d i be defined on H * by where α i is the degree i component of α and * is the convolution product. The operator Q is a bijection from infinitesimal characters to characters of H (for details, see [22]).

Lie-Butcher series and flows of vector fields
Flows y 0 → y(t) = Ψ t (y 0 ) on the manifold M can be represented by LB-series in several different ways. Here are three procedures, giving rise to what we will call LB-series of Type 1, 2 and 3: 1. In terms of pullback series: Find α ∈ G(H N ) such that This representation is used in the analysis of Crouch-Grossman methods by Owren and Marthinsen [31]. In the classical setting this is called a S-series [29].
2. In terms of an autonomous differential equation: Find β ∈ g(H N ) such that y(t) solves This is called backward error analysis (confer Section 3.3).
3. In terms of a non-autonomous equation of Lie type (time dependent frozen vector field): Find γ ∈ g(H Sh ) such that y(t) solves This representation is used in [25,26]. In the classical setting this is (close to) the standard definition of B-series.
The algebraic relationships between the coefficients α, β and γ in the above LB-series are [22]: By using these relationships one can convert between the various representations of flows.
In the notation in the following examples of LB-series we suppress the vector fields and elementary differentials, and phrase the LB-series in terms of the (dual of the) coefficient functions.
Example 2.16 (The exact solution). The exact solution of a differential equation can be written as the solution of y = F t ·y, y(0) = y 0 , where F t = F (y(t)) ∈ g is the pullback of F along the time dependent flow of F . Let F t = ∂ ∂t B t (γ). By [22,Proposition 4.9] the pullback is given by Note that this is reminiscent of a so-called combinatorial Dyson-Schwinger equation [15]. Solving by iteration yields Note that a formula for the LB-series for the exact solution was given in [31]. We observe that there cannot be any commutators of trees in this expression. Therefore, in LB-series of numerical integrators, commutators of trees must be zero up to the order of the method.
Example 2.17 (The exponential Euler method). The exponential Euler method [19] can be written as follows: y n+1 = exp(hf (y n ))y n , or, by rescaling the vector field f , as (Here the Grossman-Larson product is the same as concatenation). Note that exp( ) = Q( ), so the Type 3 LB-series for the Euler method is simply Example 2.18 (The implicit midpoint method). The implicit midpoint method [19] can be presented as: We make the following ansatz: i.e. that σ can be written as an infinitesimal LB-series. From Equation 24, we get that Since there are no forests in this expression, we must have α([ω, ω ]) = 0 for all ω, ω ∈ OT. If we write τ = B + (τ 1 · · · τ j ), then by combining Equation 27 with the ansatz, we see that coefficients of the LB-series are given recursively as α( ) = 1 2 , Hence

Substitution law for Lie-Butcher-series
In this section we will generalize the substitution law for B-series [7] to LB-series. Once the substitution law has been established we will apply it to backward error analysis for numerical methods based on LB-series.

The substitution law
Consider N as a D-algebra where the derivations are the Lie polynomials D(N ) = g(H N ) ∩ N . By the universal property of N , we know that for any map a : C → D(N ) there exists a unique D-algebra homomorphism F a : N → N such that F a (c) = a(c) for all a ∈ C. This is called the substitution law.
The theorem is easily proven by using the following lemma: Proof. It is enough to prove this for Lie polynomials 9 . Since B f is a D-algebra homomorphism it maps trees to derivations, so the only thing we have to check is that the commutator [V, W ] = V W − W V of two derivations V and W is a derivation. This is a straightforward calculation.
Proof of Theorem 3.2. Except for the use of Lemma 3.3, the proof is purely categorical. Let B f be a B-series. The composition of B f with the map β can be written in diagrammatic form as Many of the useful properties of the substitution law follow immediately from the fact that a is a D-algebra homomorphism. For example, a : N → N is a linear map which for any n, n ∈ N satisfies a I = I a (nn ) = (a n)(a n ) a (n n ) = (a n) (a n ) a (n n ) = (a n) (a n ) a (n•S) = (a n)•S a (n•e) = (a n)•e where S is the antipode and e is Euler map in H N . The free D-algebra N is the universal enveloping algebra of the free post-Lie algebra g of rooted trees [27]. By defining a coproduct by requiring that the elements of g are primitive (e.g. the deshuffle coproduct of Section 2.3.1), it is a bialgebra. The unique D-algebra morphism a is a coalgebra morphism for this coproduct: The map a is a coalgebra morphism with respect to the coproduct given by deshuffling of words (Section 2.3.1). That is, where ∆ Sh denotes the deshuffling coproduct.
Proof. The result is easily proven for primitive elements. The general case follows by induction on the length of words.
Remark 3.5 (The Hopf algebra for the substitution law). Based on the results in [5] and the fact that the operad governing post-Lie algebras is known, it is possible to describe the Hopf algebra for the substitution law following the program in [5]. This is a project currently under development [13].

A formula for the substitution law
The substitution law can be calculated recursively using a formula involving trees. To write down the formula we need to look at cutting operations on trees and forests.
Cutting trees and forest. Let τ ∈ OT be an ordered rooted tree. An elementary left cut c of τ is a choice of a set of branches E of τ to be removed from τ . These are chosen in a systematic manner: if an edge e is in E then all the branches on the same level and to the left of e must also be in E. Each cut splits τ into two components: the pruned part P c el (τ ) consisting of the trees that were cut off concatenated together, and the remaining part R c el (τ ) consisting of the tree containing the root. We also consider the empty cut, i.e. the cut c so that P c el (τ ) = I and R c el (τ ) = τ , to be an elementary cut.
A left admissible cut on τ consists of a collection of elementary cuts applied to τ with the property that any path from the root to any vertex of τ crosses at most one elementary cut. The pruned parts corresponding to each elementary cut are shuffled together, with no internal shuffling of the trees resulting from each elementary cut. An admissible cut of a tree results in a collection of shuffles of forests P c (τ ) and a tree R c (τ ). The collection of all left admissible cuts for a tree τ is written as LAC(τ ).
We extend these cutting operations to forests ω ∈ OF by applying the B + operator to ω and then cut it as a tree without using cuts of branches growing out of the root, before finally applying the B − operator to R c (ω) to remove the added root.
The coproduct ∆ N of the Hopf algebra H N (Section 2.3) can be formulated in terms of these cuts [28]. First one must extend the left admissible cuts to include the full cut of a tree, which cuts "below" the root, so that P c el (τ ) is again τ . The set of all left admissible cuts, including the full cut, is denoted by FLAC, and the coproduct ∆ N can be written as: Table 1 gives the result of this coproduct applied to all forests up to order 4. If we let∆ N (ω) consist only of forests resulting from not using the empty nor the full cut, we get ∆ N (ω) = 1 ⊗ ω + ω ⊗ 1 +∆ N (ω). The operation∆ N is called the reduced coproduct.
A formula for the substitution law. We will give a formula for the dual of the substitution, i.e. a formula for a T , where a b, ω = b, a T (ω) . The formula is based on the pruning operation P on forests.
Proof. An elementary cut at an edge growing out of a node n of a forest ω is the dual operation of attaching trees via edges to the node n in a certain order, e.g.
where the white nodes indicates where the attachment is done. The shuffling in P c (ω) corresponds to the dual of attaching forests in all possible ways to different nodes. Hence the dual of grafting is given by Theorem 3.7. We have if ω = I, and a T (I) = I. Here ∆ c denotes deconcatenation (Section 2.3).
Note that using the magmatic product × defined in Section 2.3, this can also be written as: where µ is concatenation, ∆ N is the coproduct in H N , and ∆ N (ω) = ∆ N (ω) − ω ⊗ I for all forests ω.
Proof. We first prove the formula for ordered trees. Let π OT denote the projection of forests onto trees: π OT (ω) = τ ∈OT τ, ω ω. Recall that We have Hence, The general formula is established by the following calculation, where τ is a tree: (a T ω (1) )(π OT (a T ω (2) )).
As an example, the formula applied to the tree yields See Table 2 where this formula is computed for all forests up to order 4, under the assumption that a is an infinitesimal character.
Proposition 3.8. The map a T is a character for the shuffle product: Proof. The shuffle product is dual to the deshuffle coproduct, so the result follows from Lemma 3.4 by dualization.
Remark 3.9. There is a similar formula for the substitution of B-series, only with the coproduct ∆ N replaced by the Connes-Kreimer coproduct ∆ CK = c∈AC(τ ) P c CK (τ ) ⊗ R c CK (τ ): The proof of this formula is analogous to the proof of Theorem 3.7. This gives a recursive version of the coproduct in the substitution bialgebra H CEF M of [5]

Backward error analysis and modified vector fields
Recall the results on backward error analysis in [7]: Given a B-series method B f (α) there is a modified vector fieldf so that the B-series method applied to f generates the exact flow off . Moreover,f can be written as a B-series with coefficients β satisfying β γ Exact = α, where γ Exact is the coefficient function for the B-series of the exact flow, and is the substitution law for characters in the Connes-Kreimer Hopf algebra H CK . To generalize to LB-series, consider a numerical solution of the differential equation written in terms of a LB-series B f (α). We interpret it as the exact solution of a modified differential equation y =f (y) · y. As in the classical case, it turns out that the modified vector field can be written as a LB-seriesf = B f (β). Furthermore,f is such that where γ Exact represents the coefficients of the exact solution as described in Section 2.4. This result follows by applying Proposition 3.2.
Example 3.11 (The exponential Euler method). The exponential Euler method is given by y n+1 = exp(hf (y n ))y n .
In Example 2.17 the coefficients of the LB-series for this method was seen to be γ = . To get the backward error, we calculate β = Q( ) • e, or log * (Q( )) (cf. Section 2.4) β = − In the classical setting this logarithm has been studied as log * (δ), for a certain character δ [6,30].

Implementation
As pointed out in Section 2.3, the set of forests F can be generated recursively using a magmatic product × defined on two forests ω 1 and ω 2 by by starting with the empty tree I. Each forest in F can uniquely be written as a word in I and ×.
Representing the free magma: One way to represent the free magma is by using well-formed words of parentheses '(' and ')'. A word w is well-formed if it is made of parentheses coming in pairs of one left and one right bracket, such that the left bracket appears on the left of the corresponding right bracket in w. For example, (())() is a well-formed word. The set of forests equipped with the product × is then isomorphic to this free magma via the recursion I = (), ω 1 × ω 2 = (ω 1 )ω 2 .
The authors have implemented a variant of the free magma, with elements represented by parentheses, and also the basic operations discussed in this paper. In future work, this implementation will be used to do backward error analysis on interesting test cases, like the dynamics of rigid bodies.