2.4. Deriving order conditions using trees

In the previous section we derived the order conditions for a second-order Runge-Kutta method by comparing Taylor series expansions. While this approach works well for low order methods, the algebra becomes increasingly difficult as the order increases. For example, deriving a fourth-order method requires many higher derivatives and lengthy Taylor expansions. Rooted trees provide a systematic way of generating order conditions without explicitly computing these derivatives.

---

2.4.1. Rooted Trees

The derivatives appearing in Taylor series expansions have a recursive structure. Surprisingly, this structure can be represented using simple diagrams called rooted trees. A rooted tree is a tree where a single node is designated as the root. Rooted trees are usually drawn with the root node at the bottom of the tree.

Fig. 2.3 An example of a rooted tree.

The order of a rooted tree \(\tau\), denoted by \(r(\tau)\), is the total number of nodes in the tree. \(\tau\) is the Greek letter tau which is similar to the Latin letter t

2.4.1.1. Determining derivatives

For simplicity, we consider the autonomous ODE \(y' = f(y)\). The resulting rooted-tree theory extends naturally to the general Runge-Kutta order conditions. Repeatedly differentiating the ODE gives

(2.12)\[\begin{split} \begin{align*} y' &= f(y), \\ y'' &= f'(y)y' \\ &= (f'f)(y), \\ y''' &= f''(y)(y', y') + f'(y)y'' \\ &= (f''(f,f) + f'f'f)(y) \\ &\vdots \end{align*}\end{split}\]

As you can see this soon becomes complicated, however, English mathematician Robert Merson Merson [1957] noticed that the structure of rooted trees matches that of the derivatives of \(f(y)\). Defining a rooted tree notation where \(\mathbf{f}\) denotes a node of the tree and the number of children the node has is denoted by a prime, e.g., \(\mathbf{f}''\) denotes a node has two children. A child node is written immediately following the parent node and sibling nodes are separated by a comma (using brackets if there are more than one child).

Each rooted tree corresponds to a differential expression called an elementary differential denoted by \(F(\tau)\).

\(\tau\)
\(F(\tau)\)	\(\mathbf{f}\)	\(\mathbf{f}'\mathbf{f}\)	\(\mathbf{f}''(\mathbf{f},\mathbf{f})\)	\(\mathbf{f}'\mathbf{f}'\mathbf{f}\)

So how do rooted trees relate to the derivatives of \(f(y)\)? Consider the only rooted tree of order 2 which is \(\mathbf{f}'\mathbf{f}\). If we write \(\mathbf{f} = f(y)\) then

\[\mathbf{f}'\mathbf{f} = (f'f)(y)\]

which as we saw in equation (2.12) is equal to \(y''\). We can extend this to determine the derivative \(y'''\), the two rooted trees of order 3 are \(\mathbf{f}''(\mathbf{f},\mathbf{f})\) and \(\mathbf{f}'\mathbf{f}'\mathbf{f}\). Summing these gives

\[ \mathbf{f}''(\mathbf{f},\mathbf{f}) + \mathbf{f}'\mathbf{f}'\mathbf{f} = (f''(f,f) + f'f'f)(y) = y'''\]

So we can determine the \(n\)-th derivative \(y^{(n)}\) where \(y'=f(y)\) by summing the rooted tree notation of all the possible \(n\)-th order rooted trees. Therefore, rooted trees provide a compact representation of all the derivative terms that appear in the Taylor expansion of the exact solution.

2.4.1.2. Density of a rooted tree

The density of a rooted tree \(\tau\), denoted by \(\gamma(\tau)\), is a measure related to the number of nodes and the children of the nodes in the tree. The density can be calculated using the following:

1. Assign a value of 1 to each leaf node in the tree

2. Moving towards the root node, assign each non-leaf node a value of \(1 + \text{sum(child nodes)}\)

3. Multiply all node values together

Example 2.3

Determine the order and density of the rooted tree shown below.

---

Solution

There are 7 nodes in this tree so \(r(\tau)=7\).

The nodes of the tree are assigned values based on:

• the three leaf nodes are assigned a value of 1.

• the parent node of the two leaf nodes is assigned a value \(1 + (1 + 1) = 3\).

• the parent node of the single leaf node is assigned a value \(1 + 1 = 2\).

• the root node is assigned a value of \(1 + (3 + 2 + 1) = 7\).

Therefore \(\gamma(\tau) = 7 \times 3 \times 2 \times 1 \times 1 \times 1 \times 1 = 42\)

---

2.4.2. Order conditions of an ERK method using trees

We can also derive the order conditions of a Runge-Kutta method using rooted trees. To determine the values of \(a_{ij}\), \(b_i\) and \(c_i\) in the Butcher tableau we define a set of elementary weights, denoted by \(\Phi(\tau)\) which are generated using the following steps:

• associate a label \(i\) to the root node and for all non-leaf nodes associate unique labels \(j\), \(k\), \(\ell\) etc;

• write down a sequence of factors for which the first is \(b_i\);

• for each edge that does not terminate in a leaf node, write down another factor \(a_{pq}\) where \(p\) and \(q\) are the labels associated with the parent and child node respectively;

• for each leaf node write down a factor \(c_p\) where \(p\) is the label associated with the parent node;

• sum the product of factors for all possible choices of the labels.

For example, for the tree

we associate the label \(i\) for the root node and \(j\) for the child of the root node. So the elementary weight is

\[ \Phi(\tau) = \sum_{i,j} b_i a_{ij} c_j. \]

Example 2.4

Determine the elementary weight for the rooted tree shown below.

---

Solution

Assigning the labels to the non-leaf nodes gives

So the elementary weight is

\[ \begin{align*} \Phi(\tau) &= \sum_{i,j,k} b_ia_{ij} a_{ik} c_ic_jc_jc_k = \sum_{i,j,k} b_ia_{ij} a_{ik} c_ic_j^2c_k. \end{align*} \]

Butcher noticed that comparing the Taylor series expansions for the autonomous ODE \(y'=f(y)\) and the general form of a Runge-Kutta method gives the order condition [1]

Theorem 2.2 (Order conditions for a Runge-Kutta method)

A Runge-Kutta method satisfies the order condition associated with a rooted tree \(\tau\) if

(2.13)\[\Phi(\tau) = \dfrac{1}{\gamma(\tau)}.\]

So to derive the order conditions for a \(k\)-th order \(s\)-stage Runge-Kutta method we determine the set \(T\) of all rooted trees of order up to and include \(k\). We then use the condition from equation (2.13) for each tree in \(T\) to determine the order conditions. In addition to these order conditions there is also a condition placed on the value of \(c_i\)

(2.14)\[c_i = \sum_{j=1}^sa_{ij}, \]

i.e., the values of \(c_i\) are equal to the sum of the rows of the \(A\) matrix, hence this is called the row sum condition. This condition ensures that the stage abscissae \(c_i\)​ are consistent with the locations at which the stages are evaluated.

Example 2.5

Use trees to derive the order conditions for a 2-stage second-order explicit Runge-Kutta method.

---

Solution

The set of all rooted trees up to and including order 2 is \(T = \left\{ \tau_1, \tau_2 \right\} = \left\{ \right.\) \(,\)\(\left. \right\}\)

The elementary weights and densities of these trees are

\[\begin{split} \begin{align*} \Phi(\tau_1) &= \sum_{i = 1}^2 b_i, & \gamma(\tau_1) &= 1, \\ \Phi(\tau_2) &= \sum_{i = 1}^2 b_ic_i, & \gamma(\tau_2) &= 2. \end{align*} \end{split}\]

Using equation (2.13) and the row sum condition from equation (2.14) we have the following order conditions

\[\begin{split} \begin{align*} b_1 + b_2 &= 1, \\ b_1c_1 + b_2c_2 &= \frac{1}{2}, \\ c_1 &= a_{11} + a_{12}, \\ c_2 &= a_{21} + a_{22}. \end{align*} \end{split}\]

Since we are deriving an ERK method, \(a_{11} = a_{12} = a_{22} = c_1 = 0\) and the order conditions simplify to

\[\begin{split} \begin{align*} b_1 + b_2 &= 1, \\ b_2c_2 &= \frac{1}{2}, \\ c_2 &= a_{21}. \end{align*} \end{split}\]

These are the same order conditions for a second-order ERK method derived in the previous section.

In the next section we use these rooted-tree order conditions to derive a fourth-order explicit Runge-Kutta method. The rooted-tree approach makes this practical; a direct Taylor-series derivation would be considerably more involved.

---

[1]

I’ve skipped the derivation here, for details see Butcher [2008].