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.
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.
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.
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]
The usual functions on RootedTree
s are implemented, cf.
Butcher (Numerical Methods for ODEs, 2016).
order(t::RootedTree)
: The order of aRootedTree
, i.e., the length of its level sequence.σ(t::RootedTree)
orsymmetry(t)
: The symmetryσ
of a rooted tree, i.e., the order of the group of automorphisms on a particular labelling (of the vertices) oft
.γ(t::RootedTree)
ordensity(t)
: The densityγ(t)
of a rooted tree, i.e., the product over all vertices oft
of the order of the subtree rooted at that vertex.α(t::RootedTree)
: The number of monotonic labelings oft
not equivalent under the symmetry group.β(t::RootedTree)
: The total number of labelings oft
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
) oft::RootedTree
for the Butcher coefficientsA, b, c
of a Runge-Kutta method.derivative_weight(t, A, b, c)
: Compute the derivative weight (ΦᵢD)(t
) oft
for the Butcher coefficientsA, 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 treet
for the Runge-Kutta method with Butcher coefficientsA, b, c
.
- 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.
If you use RootedTrees.jl for your research, please cite the paper
@article{ketcheson2023computing,
title={Computing with {B}-series},
author={Ketcheson, David I and Ranocha, Hendrik},
journal={ACM Transactions on Mathematical Software},
volume={49},
number={2},
year={2023},
month={06},
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}
}