## RootedTrees.jl

A collection of functionality around rooted trees to generate order conditions for Runge-Kutta methods in Julia for differential equations and scientific machine learning (SciML)
Author SciML
Popularity
9 Stars
Updated Last
1 Year Ago
Started In
March 2019

# RootedTrees

A collection of functionality around rooted trees to generate order conditions for Runge-Kutta methods in Julia.

## API Documentation

Please note that this project is work in progress. However, we don't expect many breaking changes in the near future.

### Construction

`RootedTree`s are represented using level sequences, i.e., `AbstractVector`s containing the distances of the nodes from the root, cf. Beyer, Terry, and Sandra Mitchell Hedetniemi. "Constant time generation of rooted trees." SIAM Journal on Computing 9.4 (1980): 706-712. `RootedTree`s can be constructed from their level sequence using

```julia> t = rootedtree([1, 2, 3, 2])
RootedTree{Int64}: [1, 2, 3, 2]```

In the notation of Butcher (Numerical Methods for ODEs, 2016), this tree can be written as `[[τ²] τ]` or `(τ ∘ τ) ∘ (τ ∘ τ)`, where `∘` is the non-associative Butcher product of `RootedTree`s, which is also implemented.

To get the representation of a `RootedTree` introduced by Butcher, use `butcher_representation`:

```julia> t = rootedtree([1, 2, 3, 4, 3, 3, 2, 2, 2, 2, 2])
RootedTree{Int64}: [1, 2, 3, 4, 3, 3, 2, 2, 2, 2, 2]

julia> butcher_representation(t)
"[[[τ]τ²]τ⁵]"```

### Iteration over `RootedTree`s

A `RootedTreeIterator(order::Integer)` can be used to iterate efficiently over all `RootedTree`s of a given `order`.

Be careful that the iterator is stateful for efficiency reasons, so you might need to use `copy` appropriately, e.g.,

```julia> map(identity, RootedTreeIterator(4))
4-element Array{RootedTrees.RootedTree{Int64,Array{Int64,1}},1}:
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]

julia> map(copy, RootedTreeIterator(4))
4-element Array{RootedTrees.RootedTree{Int64,Array{Int64,1}},1}:
RootedTree{Int64}: [1, 2, 3, 4]
RootedTree{Int64}: [1, 2, 3, 3]
RootedTree{Int64}: [1, 2, 3, 2]
RootedTree{Int64}: [1, 2, 2, 2]```

### Functions on Trees

The usual functions on `RootedTree`s are implemented, cf. Butcher (Numerical Methods for ODEs, 2016).

• `order(t::RootedTree)`: The order of a `RootedTree`, i.e., the length of its level sequence.
• `σ(t::RootedTree)`: The symmetry `σ` of a rooted tree, i.e., the order of the group of automorphisms on a particular labelling (of the vertices) of `t`.
• `γ(t::RootedTree)`: The density `γ(t)` of a rooted tree, i.e., the product over all vertices of `t` of the order of the subtree rooted at that vertex.
• `α(t::RootedTree)`: The number of monotonic labelings of `t` not equivalent under the symmetry group.
• `β(t::RootedTree)`: The total number of labelings of `t` not equivalent under the symmetry group.

Additionally, functions on trees connected to Runge-Kutta methods are implemented.

• `elementary_weight(t, A, b, c)`: Compute the elementary weight Φ(`t`) of `t::RootedTree` for the Butcher coefficients `A, b, c` of a Runge-Kutta method.
• `derivative_weight(t, A, b, c)`: Compute the derivative weight (ΦᵢD)(`t`) of `t` for the Butcher coefficients `A, b, c` of a Runge-Kutta method.
• `residual_order_condition(t, A, b, c)`: The residual of the order condition `(Φ(t) - 1/γ(t)) / σ(t)` with elementary weight `Φ(t)`, density `γ(t)`, and symmetry `σ(t)` of the rooted tree `t` for the Runge-Kutta method with Butcher coefficients `A, b, c`.

### Required Packages

No packages found.