---
tag: 6MH1DHMCPF
kind: object
name: Butcher group
msc: [65L06, 16T05, 05C05]
instance_of: [G5S1M9]
uses: [0Y0JGC2K9T, 7DBPJKYC6C, RH8BD7PW5F, 7XFYP0N84H]
sources:
  - url: https://en.wikipedia.org/wiki/Butcher_group
same_as:
  wikidata: Q5002457
  wikipedia: Butcher group
---

## Description

Let $\mathcal{T}$ be the set of finite non-planar [[rooted trees|0Y0JGC2K9T]].
They are written recursively: $\bullet$ is the tree with one vertex, and $[t_1, \ldots, t_k]$ is the tree whose root is joined to the roots of $t_1, \ldots, t_k$.
Let $H$ be the commutative polynomial algebra over $\R$ generated by $\mathcal{T}$, whose monomials are rooted forests.
Give $H$ the coproduct $\Delta(t) = t \otimes 1 + 1 \otimes t + \sum_{c} P^c(t) \otimes R^c(t)$, where $c$ runs over the admissible cuts of $t$.
Here $R^c(t)$ is the part that keeps the root and $P^c(t)$ is the forest cut off.
Then $H$ is the Connes–Kreimer [[Hopf algebra|7XFYP0N84H]] of rooted trees.

The *Butcher group* $G$ is the set of algebra homomorphisms $\varphi \colon H \to \R$.
Such a $\varphi$ is the same as a map $\mathcal{T} \to \R$, extended multiplicatively to forests.
The product of $\varphi, \psi \in G$ is the convolution
$$(\varphi \psi)(t) = (\varphi \otimes \psi)\big(\Delta(t)\big).$$
It is a [[group|G5S1M9]]: the product is associative because $\Delta$ is coassociative, and the identity is the counit, which is $0$ on every tree.
The inverse of $\varphi$ is $\varphi \circ S$, where $S$ is the antipode of $H$.

## Remarks

Each [[Runge–Kutta method|7DBPJKYC6C]] with [[Butcher tableau|RH8BD7PW5F]] $(A, b, c)$ gives an element $\Phi$ of $G$ through its elementary weights: $\Phi(t) = \sum_i b_i \Phi_i(t)$, where $\Phi_i(\bullet) = 1$ and $\Phi_i([t_1, \ldots, t_k]) = \prod_{m=1}^{k} \sum_j a_{ij} \Phi_j(t_m)$.
The exact flow of the differential equation corresponds to $e(t) = 1/\gamma(t)$, where $\gamma(\bullet) = 1$ and $\gamma([t_1, \ldots, t_k]) = \abs{t} \, \gamma(t_1) \cdots \gamma(t_k)$, with $\abs{t}$ the number of vertices.
A method has order $p$ if and only if $\Phi(t) = 1/\gamma(t)$ for every tree with at most $p$ vertices; these are Butcher's order conditions.
Check for small trees: $\Phi(\bullet) = \sum_i b_i$ must equal $1$, and $\Phi([\bullet]) = \sum_i b_i c_i$ with $c_i = \sum_j a_{ij}$ must equal $\frac{1}{\gamma([\bullet])} = \frac12$.
With a suitable ordering convention, applying one method after another corresponds to the product in $G$, which explains the name: the group encodes composition of methods.
John C. Butcher introduced this group in 1972 in his algebraic theory of integration methods.

## Explanations

### L1 human

Every Runge–Kutta method can be described by a list of numbers, one for each rooted tree.
The trees keep track of how the derivatives of the right-hand side combine in the Taylor expansion of the solution.
Doing two steps with two methods in a row gives a new list, and this operation turns the set of all such lists into a group.
A method is accurate to order $p$ when its numbers agree with those of the exact solution on all trees with at most $p$ vertices.

### L2 human

The Butcher group organises the theory of B-series, the formal series indexed by rooted trees that describe Runge–Kutta methods and many other integrators.
Its identification with the character group of the Connes–Kreimer Hopf algebra links numerical analysis with the renormalization of quantum field theory, where the same Hopf algebra appears.
Effective order, the composition of methods and the backward error analysis of geometric integrators are all computations in this group.