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

Build Status Coverage Status codecov

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

RootedTrees are represented using level sequences, i.e., AbstractVectors 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. RootedTrees 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 RootedTrees, 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 RootedTrees

A RootedTreeIterator(order::Integer) can be used to iterate efficiently over all RootedTrees 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 RootedTrees 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.