Numerical analysis Ordinary differential equations Object

Butcher group

Builds on Rooted tree Runge–Kutta methods Butcher tableau Hopf algebra

Description

Let $\mathcal{T}$ be the set of finite non-planar rooted trees. 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 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: 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 with Butcher tableau $(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.

Going deeper

For a student

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.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`6MH1DHMCPF`
URI	`m2://6MH1DHMCPF`
Kind	object
Writing	W0 stub
MSC	65L06, 16T05, 05C05
Instance of	Group
Uses	Rooted tree, Runge–Kutta methods, Butcher tableau, Hopf algebra
Same as	Wikidata Q5002457 Wikipedia Butcher group