rooted_trees
¶

class
nodepy.rooted_trees.
RootedTree
(strg)[source]¶ A rooted tree is a directed acyclic graph with one node, which has no incoming edges, designated as the root. Rooted trees are useful for analyzing the order conditions of multistage numerical ODE solvers, such as RungeKutta methods and other general linear methods.
The trees are represented as strings, using one of the notations introduced by Butcher (the third column of Table 300(I) of Butcher’s text). The character ‘T’ is used in place of $\tau$ to represent a vertex, and braces ‘{ }’ are used instead of brackets ‘[ ]’ to indicate that everything inside the braces is joined to a single parent node. Thus the first four trees are:
‘T’, ‘{T}’, ‘{T^2}’, {{T}}’
These can be generated using the function list_trees(), which returns a list of all trees of a given order:
>>> from nodepy import * >>> for p in range(4): print(rt.list_trees(p)) [''] ['T'] ['{T}'] ['{{T}}', '{T^2}']
Note that the tree of order 0 is indicated by an empty string.
If the tree contains an edge from vertex A to vertex B, vertex B is said to be a child of vertex A. A vertex with no children is referred to as a leaf.
Warning
One important convention is assumed in the code; namely, that at each level, leaves are listed first (before any other subtrees), and if there are $n$ leaves, we write ‘T^n’.
Note
Currently, powers cannot be used for subtrees; thus
‘{{T}{T}}’
is valid, while
‘{{T}^2}’
is not. This restriction may be lifted in the future.
Examples:
>>> from nodepy import rooted_trees as rt >>> tree=rt.RootedTree('{T^2{T{T}}{T}}') >>> tree.order() 9 >>> tree.density() 144 >>> tree.symmetry() 2
Topologically equivalent trees are considered equal:
>>> tree2=RootedTree('{T^2{T}{T{T}}}') >>> tree2==tree True
We can generate Python code to evaluate the elementary weight corresponding to a given tree for a given class of methods:
>>> rk.elementary_weight_str(tree) 'dot(b,dot(A,c)*dot(A,c*dot(A,c))*c**2)'
 References:
 TODO:  Check validity of strg more extensively
 Accept any leaf ordering, but convert it to our convention
 convention for ordering of subtrees?

order
()[source]¶ The order of a rooted tree, denoted $r(t)$, is the number of vertices in the tree.
Examples:
>>> from nodepy import rooted_trees as rt >>> tree=rt.RootedTree('{T^2{T{T}}}') >>> tree.order() 7

density
()[source]¶ The density of a rooted tree, denoted by $\gamma(t)$, is the product of the orders of the subtrees.
Examples:
>>> from nodepy import rooted_trees as rt >>> tree=rt.RootedTree('{T^2{T{T}}}') >>> tree.density() 56
Reference:
 [butcher2003] p. 127, eq. 301(c)

symmetry
()[source]¶ The symmetry $\sigma(t)$ of a rooted tree is...
Examples:
>>> from nodepy import rooted_trees as rt >>> tree=rt.RootedTree('{T^2{T{T}}}') >>> tree.symmetry() 2
Reference:
 [butcher2003] p. 127, eq. 301(b)

Dmap
()[source]¶ Butcher’s function $D(t)$. Represents differentiation. Defined by $D(t)$=0 except for D(‘T’)=1.
 Reference:

lamda
(alpha, extraargs=[])[source]¶ Computes Butcher’s functional lambda on a given tree for the function alpha. This is used to compute the product of two functions on trees.
INPUT:
 alpha – a function on rooted trees
 extraargs – a list containing any additional arguments that must be passed to alpha
 OUTPUT:
 tprod – a list of trees [t1, t2, ...]
 fprod – a list of numbers [a1, a2, ...]
The meaning of the output is that $\lambda(\alpha,t)(\beta)=a1*\beta(t1)+a2*\beta(t2)+...$
Examples:
>>> from nodepy import rt >>> tree = rt.RootedTree('{T{T}}') >>> tree.lamda(rt.Emap) (['T', '{T}', '{{T}}', '{T}', '{T^2}', '{T{T}}'], [1/2, 1, 1, 1/2, 1, 1])
 Reference:
 [butcher2003] pp. 275276

lamda_str
(alpha, extraargs=[])[source]¶ Alternate version of lamda above, but returns a string. Hopefully we can get rid of this (and the other str functions) when SAGE can handle noncommutative symbolic algebra.

Gprod
(alpha, beta, alphaargs=[], betaargs=[])[source]¶ Returns the product of two functions on a given tree.
 INPUT:
 alpha, beta – two functions on rooted trees
 that return symbolic or numeric values
 alphaargs – a string containing any additional arguments
 that must be passed to function alpha
 betaargs – a string containing any additional arguments
 that must be passed to function beta
 OUTPUT:
 (alpha*beta)(self) i.e., the function that is the product (in G) of the functions alpha and beta. Note that this product is not commutative.
The product is given by
$(\alpha*\beta)(‘’)=\beta(‘’)$
$(\alpha*\beta)(t) = \lambda(\alpha,t)(\beta) + \alpha(t)\beta(‘’)$
Note
Gprod can be used to compute products of more than two functions by passing Gprod itself in as beta, and providing the remaining functions to be multiplied as betaargs.
Examples:
>>> from nodepy import rt >>> tree = rt.RootedTree('{T{T}}') >>> tree.Gprod(rt.Emap,Dmap) 1/2
Reference: [butcher2003] p. 276, Thm. 386A

Gprod_str
(alpha, beta, alphaargs=[], betaargs=[])[source]¶ Alternate version of Gprod, but operates on strings. Hopefully can be eliminated later in favor of symbolic manipulation.

plot
(nrows=1, ncols=1, iplot=1, ttitle='')[source]¶ Plots the rooted tree.
 INPUT: (optional)
 nrows, ncols – number of rows and columns of subplots in the figure
 iplot – index of the subplot in which to plot this tree
These are only necessary if plotting more than one tree in a single figure using subplot.
OUTPUT: None.
The plot is created recursively by plotting the root, parsing the subtrees, plotting the subtrees’ roots, and calling _plot_subtree on each child

list_equivalent_trees
()[source]¶ Returns a list of all strings (subject to our assumptions) equivalent to a given tree
 INPUT:
 self – any rooted tree
 OUTPUT:
 treelist – a list of all the ‘legal’ tree strings
 that produce the same tree.
The list of equivalent trees is obtained by taking all permutations of the (nonleaf) subtrees. This routine is used to test equality of trees.

nodepy.rooted_trees.
plot_all_trees
(p, title='str')[source]¶ Plots all rooted trees of order p.
Example:
Plot all trees of order 4:
>>> from nodepy import rt >>> rt.plot_all_trees(4) <matplotlib.figure.Figure object at ...>

nodepy.rooted_trees.
list_trees
(p, ind='all')[source]¶ Returns rooted trees of order p.
INPUT:
p – order of trees desired
 ind – if given, returns a single tree corresponding to this index.
Not very useful since the ordering isn’t obvious.
OUTPUT: list of all trees of order p (or just one, if ind is provided).
Generates the rooted trees using Albrecht’s ‘Recursion 3’.
Examples:
Produce column of Butcher’s Table 302(I):
>>> for i in range(1,11): ... forest=list_trees(i) ... print(len(forest)) 1 1 2 4 9 20 48 115 286 719
Warning
This code is complete only up to order 10. We need to extend it by adding more subloops for p>10.
 TODO: Implement Butcher’s formula (Theorem 302B) for the number
 of trees and determine to what order this is valid.
Reference: [albrecht1996]

nodepy.rooted_trees.
Dprod
(tree, alpha)[source]¶ Evaluate (alpha*D)(t). Note that this is not equal to (D*alpha)(t). This function is necessary (rather than just using Gprod) in order to avoid infinite recursions.
Examples:
>>> from nodepy import rt >>> tree = rt.RootedTree('{T{T}}') >>> Dprod(tree,Emap) 1/2

nodepy.rooted_trees.
Dmap
(tree)[source]¶ Butcher’s function D(t). Represents differentiation. Defined by D(t)=0 except for D(‘T’)=1.

nodepy.rooted_trees.
Gprod
(tree, alpha, beta, alphaargs='', betaargs=[])[source]¶ Returns the product of two functions on a given tree. See Butcher p. 276, Thm. 386A

nodepy.rooted_trees.
Emap
(tree, a=1)[source]¶ Butcher’s function E^a(t). Gives the Bseries for the exact solution advanced ‘a’ steps in time.
Examples:
>>> from nodepy import rooted_trees as rt >>> tree=rt.RootedTree('{T^2{T{T}}}') >>> rt.Emap(tree) 1/56 >>> rt.Emap(tree,a=2) 16/7
Reference:

nodepy.rooted_trees.
recursiveVectors
(p, ind='all')[source]¶ Generate recursive vectors using Albrecht’s ‘recursion 1’. These are essentially the order conditions for RungeKutta methods, excluding those that correspond to bushy trees. More specifically, these are the vectors that must be orthogonal to the vector of weights b.
Note that the individual order conditions obtained from this algorithm are different from those obtained using Butcher’s approach. But as a set of conditions up to some order they are, of course, equivalent.
Follows [albrecht1996] p. 1718
Warning
This code is complete only up to order 12. We need to extend it by adding more subloops for p>12.
Example
Count number of conditions for order 12:
>>> from nodepy import rt >>> v = rt.recursiveVectors(12) >>> print(len(v)) 4769