## 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)
Popularity
34 Stars
Updated Last
4 Months Ago
Started In
March 2019

# RootedTrees

A collection of functionality around rooted trees to generate order conditions for Runge-Kutta methods in Julia. This package also provides basic functionality for BSeries.jl.

## API Documentation

The API of RootedTrees.jl is documented in the following. Additional information on each function is available in their docstrings and in the online documentation.

### Construction

`RootedTree`s are represented using level sequences, i.e., `AbstractVector`s containing the distances of the nodes from the root, see

• Beyer, Terry, and Sandra Mitchell Hedetniemi. "Constant time generation of rooted trees". SIAM Journal on Computing 9.4 (1980): 706-712. DOI: 10.1137/0209055

`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)
"[[[τ]τ²]τ⁵]"```

There are also some simple plot recipes for Plots.jl. Thus, you can visualize a rooted tree `t` using `plot(t)` when `using Plots`.

Additionally, there is an un-exported function `RootedTrees.latexify` that can generate LaTeX code for a rooted tree `t` based on the LaTeX package forest. The relevant code that needs to be included in the preamble can be obtained from the docstring of `RootedTrees.latexify` (type `?` and `RootedTrees.latexify` in the Julia REPL). The same format is used when you are `using Latexify` and their function `latexify`, see Latexify.jl.

### 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)` or `symmetry(t)`: 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)` or `density(t)`: 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`.

## Brief Changelog

• v2.16: The LaTeX printing of rooted trees changed to allow representing colored rooted trees. Please update your LaTeX preamble as described in the docstring of `RootedTrees.latexify`.
• v2.0: Rooted trees are considered up to isomorphisms introduced by shifting each coefficient of their level sequence by the same number.

## Referencing

```@article{ketcheson2022computing,
title={Computing with {B}-series},
author={Ketcheson, David I and Ranocha, Hendrik},
journal={ACM Transactions on Mathematical Software},
year={2022},
month={12},
doi={10.1145/3573384},
eprint={2111.11680},
eprinttype={arXiv},
eprintclass={math.NA}
}```

In addition, you can also refer to RootedTrees.jl directly as

```@misc{ranocha2019rootedtrees,
title={{RootedTrees.jl}: {A} collection of functionality around rooted trees
to generate order conditions for {R}unge-{K}utta methods in {J}ulia
for differential equations and scientific machine learning ({SciM}L)},
author={Ranocha, Hendrik and contributors},
year={2019},
month={05},
howpublished={\url{https://github.com/SciML/RootedTrees.jl}},
doi={10.5281/zenodo.5534590}
}```

### Required Packages

View all packages