Misplaced Pages

Revision as of 15:53, 24 June 2009

You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|reason=<Fill reason here>}}, or remove the Cleanup template.
In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher, is an algebraic formalism involving rooted trees that provides formal power series solutions of the non-linear ordinary differential equations modeling the flow of a vector field. It was Arthur Cayley, prompted by the work of James Joseph Sylvester on change of variable in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. In numerical analysis, Butcher's formalism provides a method for analysing solutions of ordinary differential equations by the Runge-Kutta method. It was later realised that his group and the associated Hopf algebra of rooted trees underlie the Hopf algebra introduced by Dirk Kreimer and Alain Connes in their work on renormalization in quantum field theory.

Differentials and rooted trees

A rooted tree is a graph with a distinguished node, called the root, in which every other node is connected to the root by a unique path. If the root of a tree t is removed and the nodes connected to the original node by a single bond are taken as new roots, the tree t breaks up into rooted trees t₁, t₂, ... Reversing this process a new tree t = can be constructed by joining the roots of the trees to a new common root. The number of nodes in a tree is denoted by |t|. A heap-ordering of of a rooted tree t is an allocation of the numbers 1 through |t| to the nodes so that the numbers increase on any path going away from the root. The number of heap-orderings on a particular tree is denoted by α(t) and can be computed using the Butcher's formula:

${\displaystyle \displaystyle \alpha (t)={|t|! \over t!|S_{t}|},}$

where S_t denotes the symmetry group of t and the tree factorial is defined recursively by

${\displaystyle !=||\cdot t_{1}!\cdots t_{n}!}$

with the tree factorial of an isolated root defined to be 1

${\displaystyle \bullet !=1.}$

The ordinary differential equation for the flow of a vector field on an open subset U of R can be written

${\displaystyle \displaystyle {dx(s) \over ds}=f(x(s)),\,\,x(0)=x_{0},}$

where x(s) takes values in U, f is a smooth function from U to R and x₀ is the starting point of the flow at time s = 0.

Cayley (1857) gave a method to compute the higher order derivatives x(s) in terms of rooted trees. His formula can be conveniently expressed using the elementary differentials introduced by Butcher. These are defined inductively by

${\displaystyle \delta _{\bullet }^{i}=f^{i},\,\,\,\delta _{}^{i}=\sum _{j_{1},\dots ,j_{n}}(\delta _{t_{1}}^{j_{1}}\cdots \delta _{t_{n}}^{j_{n}})\partial _{j_{1}}\cdots \partial _{j_{n}}f^{i}.}$

With this notation

${\displaystyle {d^{m}x \over ds^{m}}=\sum _{|t|=m}\alpha (t)\delta _{t},}$

giving the power series expansion

${\displaystyle \displaystyle x(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)\delta _{t}(0).}$

As an example when N = 1, so that x and f are real-valued functions of a single real variable, the formula yields

${\displaystyle x^{(4)}=f^{\prime \prime \prime }f^{3}+3f^{\prime \prime }f^{\prime }f^{2}+f^{\prime }f^{\prime \prime }f^{2}+(f^{\prime })^{2}f^{2},}$

where the four terms correspond to the four rooted trees from left to right in Figure 3 above.

Hopf algebra of rooted trees

This section is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this section while this message is displayed. This page was last edited at 15:53, 24 June 2009 (UTC) (15 years ago) – this estimate is cached, update. Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions.

References

• Cayley, Arthur (1857), "On the theory of analytic forms called trees", Philosophical Magazine, XIII: 172–176 (also in Volume 3 of the Collected Works of Cayley, pages 242-246)
• Butcher, J.C (2009), "Trees and numerical methods for ordinary differential equations", Numerical Algorithms, Springer online
• Hairer, E.; Wanner, G. (1974), "On the Butcher group and general multi-value methods", Computing, 13: 1–15
• Grossman, R.; Larson, R. (1989), "Hopf algebraic structures of families of trees" (PDF), Journal Algebra, 26: 184–210
• Connes, Alain; Kreimer, Dirk (1998), "Hopf Algebras, Renormalization and Noncommutative Geometry", Communications in Mathematical Physics, 199: 203–242
• Brouder, Christian (2000), "Runge-Kutta methods and renormalization", Eur.Phys.J., C12: 521–534
• Gracia Bondía, José; Várilly, Joseph C.; Figueroa, Héctor (2000), Elements of noncommutative geometry, Birkhäuser, ISBN 0817641246, Chapter 14.

This mathematics-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Mathematics stubs
• Combinatorics
• Numerical analysis
• Quantum field theory
• Hopf algebras