Misplaced Pages

Revision as of 18:16, 25 June 2009

In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Hairer & Wanner (1974), 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 Cayley (1857), prompted by the work of 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. Brouder (2000) pointed out that the Butcher group and the associated Hopf algebra of rooted trees underlie the Hopf algebra introduced by Connes & Kreimer (1998) 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.

In a single variable this formula is the same as Faà di Bruno's formula of 1855; however in several variables it has to be written more carefully in the form

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

where the tree structure is crucial.

Definition using Hopf algebra of rooted trees

The Hopf algebra H of rooted trees was defined by Connes & Kreimer (1998) in connection with Kreimer's previous work on renormalization in quantum field theory. It was later discovered that the Hopf algebra was the dual of a Hopf algebra defined earlier by Grossman & Larsen (1989) harvtxt error: no target: CITEREFGrossmanLarsen1989 (help) in a different context. The characters of H, i.e. the homomorphisms of the underlying commutative algebra into R, form a group, called the Butcher group. It corresponds to the formal group structure discovered in numerical analysis by Butcher (1972).

The Hopf algebra of rooted trees H is defined to be the polynomial ring in the variables t, where t runs through rooted trees.

• Its comultiplication ${\displaystyle \Delta :H\rightarrow H\otimes H}$ is defined by

${\displaystyle \Delta (t)=t\otimes I+I\otimes t+\sum _{s\subset t}s\otimes ,}$

where the sum is over all proper rooted subtrees s of t; ${\displaystyle }$ is the monomial given by the product the variables t_i formed by the rooted trees that arise on erasing all the nodes of s and connected links from t.

• Its counit is the homomorphism ε of H into R sending each varεiable t to zero.

• Its antipode S can be defined recursively by the formula

${\displaystyle S(t)=-t-\sum _{s\subset t}S()s,\,\,\,S(\bullet )=-\bullet .}$

The Butcher group is defined to be the set of algebra homomorphims φ of H into R with group structure

${\displaystyle \varphi _{1}\star \varphi _{2}(t)=(\varphi _{1}\otimes \varphi _{2})\Delta (t).}$

The inverse in the Butcher group is given by

${\displaystyle \varphi ^{-1}(t)=\varphi (St)}$

and the identity by the counit ε.

Butcher series and Runge–Kutta method

The non-linear ordinary differential equation

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

can be solved approximately by the Runge-Kutta method. This iterative scheme requires an m x m matrix

${\displaystyle A=(a_{ij})}$

and a vector

${\displaystyle b=(b_{i})}$

with m components.

The scheme defines vectors x_n by first finding a solution X₁, ... , X_m of

${\displaystyle X_{i}=x_{n-1}+h\sum _{j=1}^{m}a_{ij}f(X_{j})}$

and then setting

${\displaystyle x_{n}=x_{n-1}+h\sum _{j=1}^{m}b_{j}f(x_{j}).}$

Butcher (1963) showed that the solution of the corresponding ordinary differential equations

${\displaystyle X_{i}(s)=x_{0}+s\sum _{j=1}^{m}a_{ij}f(X_{j}(s)),\,\,\,x(s)=x_{0}+s\sum _{j=1}^{m}b_{j}f(X_{j}(s))}$

has the power series expansion

${\displaystyle X_{i}(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\sum _{j=1}^{m}a_{ij}\varphi _{j}(t)\delta _{t}(0),\,\,\,\,x(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),}$

where φ_j and φ are determined recursively by

${\displaystyle \varphi _{j}(\bullet )=1.\,\,\,\varphi _{i}()=\sum _{j_{1},\dots ,j_{k}}a_{ij_{1}}\dots a_{ij_{k}}\varphi _{j_{1}}(t_{1})\dots \varphi _{j_{k}}(t_{k})}$

and

${\displaystyle \varphi (t)=\sum _{j=1}^{m}b_{j}\varphi _{j}(t).}$

The power series above are called Butcher series. The corresponding assignment φ is an element of the Butcher group. The homomorphism corresponding to the actual flow has

${\displaystyle \Phi (t)={1 \over t!}.}$

Butcher showed that the Runge-Kutta method gives an nth order approximation of the actual flow provided that φ and Φ agree on all trees with n nodes or less. Moreover Butcher (1972) showed that the homomorphisms defined by the Runge-Kutta method form a dense subgroup of the Butcher group: in fact he showed that, given a homomorphism φ', there is a Runge-Kutta homomorphism φ agreeing with φ' to order n; and that if given homomorphims φ and φ' corresponding to Runge-Kutta data (A, b) and (A' , b' ), the product homomorphism ${\displaystyle \varphi \star \varphi ^{\prime }}$ corresponds to the data

${\displaystyle {\begin{pmatrix}A&0\\0&A^{\prime }\\\end{pmatrix}},\,\,(b,b^{\prime }).}$

Hairer & Wanner (1974) proved that the Butcher group acts naturally on the functions f. Indeed setting

${\displaystyle \varphi \circ f=1+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),}$

they proved that

${\displaystyle \varphi _{1}\circ (\varphi _{2}\circ f)=(\varphi _{1}\star \varphi _{2})\circ f.}$

Lie algebra

Connes & Kreimer (1998) showed that associated with the Butcher group G is an infinite-dimensional Lie algebra. The existence of this Lie algebra is predicted by a theorem of Milnor & Moore (1965): the commutativity and natural grading on H implies that the dual H* can be identified with the universal enveloping algebra of a Lie algebra ${\displaystyle {\mathfrak {g}}}$. Connes and Kreimer explicitly identify ${\displaystyle {\mathfrak {g}}}$ with a space of derivations θ of H into R, i.e. linear maps such that

${\displaystyle \theta (ab)=\varepsilon (a)\theta (b)+\theta (a)\varepsilon (b),}$

the formal tangent space of G at the identity ε. This forms a Lie algebra with Lie bracket

${\displaystyle (t)=(\theta _{1}\otimes \theta _{2}-\theta _{2}\otimes \theta _{1})\Delta (t).}$

${\displaystyle {\mathfrak {g}}}$ is generated by the derivations θ_t defined by

${\displaystyle \theta _{t}(t^{\prime })=\delta _{tt^{\prime }},}$

for each rooted tree t.

Renormalization

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 18:16, 25 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.

Connes & Kreimer (1998) provided a general context for using Hopf algebraic methods to give a simple mathematical formulation of renormalization in the Lagrangian formulation of quantum field theory. Renormalization was interpreteted as Birkhoff factorization of loops in the character group of the associated Hopf algebra. The models considered by Kreimer (1999) harvtxt error: no target: CITEREFKreimer1999 (help) had Hopf algebra H and character group G, the Butcher group. Brouder (2000) has given an account of this renormalization processes in term of flows of Runge-Kutta data.

Notes

1. Butcher 2008
2. Brouder 2000

References

• Gracia Bondía, José; Várilly, Joseph C.; Figueroa, Héctor (2000), Elements of noncommutative geometry, Birkhäuser, ISBN 0817641246, Chapter 14.
• Brouder, Christian (2000), "Runge–Kutta methods and renormalization", Eur.Phys.J., C12: 521–534
• Butcher, J.C (1963), "Coefficients for the study of Runge-Kutta integration processes", J. Austral. Math. Soc., 3: 185–201
• Butcher, J.C (1972), "An algebraic theory of integration methods", Math. Comput., 26: 79–106
• Butcher, John C. (2008), Numerical methods for ordinary differential equations (2nd ed.), John Wiley & Sons Ltd., ISBN 978-0-470-72335-7, MR2401398
• Butcher, J.C (2009), "Trees and numerical methods for ordinary differential equations", Numerical Algorithms, Springer online
• 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)
• Connes, Alain; Kreimer, Dirk (1998), "Hopf Algebras, Renormalization and Noncommutative Geometry", Communications in Mathematical Physics, 199: 203–242
• Grossman, R.; Larson, R. (1989), "Hopf algebraic structures of families of trees" (PDF), Journal Algebra, 26: 184–210
• Hairer, E.; Wanner, G. (1974), "On the Butcher group and general multi-value methods", Computing, 13: 1–15
• Milnor, John W.; Moore, John C. (1965), "On the structure of Hopf algebras", Ann. of Math., 81: 211–264

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