kauri 1.0.0

Algebraic manipulation of non-planar rooted trees in Python

Kauri is a Python package for symbolic and algebraic manipulation of rooted trees, often used in the study of B-series, Runge-Kutta methods, and backward error analysis. It implements Hopf algebraic structures and provides tools for symbolic computation and visualization.

Installation

pip install kauri

Documentation

Full documentation is available at https://kauri.readthedocs.io

Functionalities

The main goal of the kauri package is to provide implementations of:

• The Butcher-Connes-Kreimer (BCK) Hopf algebra of (un)labelled non-planar rooted trees [Connes & Kreimer, 1999], used for the analysis of B-series and Runge-Kutta schemes
• The Calaque, Ebrahimi-Fard and Manchon (CEM) Hopf algebra [Calaque, Ebrahimi-Fard & Manchon, 2011], used for backward error analysis of B-series and Runge-Kutta schemes
• Evaluation and manipulation of Runge-Kutta schemes, including symbolic expressions for elementary weights functions and order conditions
• Evaluation and symbolic manipulation of truncated B-series over unlabelled trees.

Simple Examples

Unlabelled BCK coproduct

import kauri as kr
import kauri.bck as bck

t = kr.Tree([[], [[]]])
cp = bck.coproduct(t)
kr.display(cp)

Output:

Labelled BCK antipode

import kauri as kr
import kauri.bck as bck

t = kr.Tree([[[3],2],[1],0])
s = bck.antipode(t)
kr.display(s)

Output:

Runge-Kutta order conditions

import kauri as kr

t = kr.Tree([[],[]])
print(kr.rk_order_cond(t, s = 3, explicit = True))

Output:

a10**2*b1 + b2*(a20 + a21)**2 - 1/3

Truncated B-series of RK4

import kauri as kr
import sympy as sp
import numpy as np
import matplotlib.pyplot as plt

y1 = sp.symbols('y1')
y = sp.Matrix([y1])
f = sp.Matrix([y1 ** 2])

m = kr.rk4.elementary_weights_map()
bs = kr.BSeries(y, f, weights = m, order = 5)
print(bs.series())

t = np.linspace(0, 0.9, 100)
true = [1 / (1 - x) for x in t]
plt.plot(t, true, linestyle="--", color="black")
plt.plot(t, [bs([1], h) for h in t], color = 'firebrick')
plt.show()

The BCK Hopf Algebra

The Butcher-Connes-Kreimer Hopf algebra of (un)labelled non-planar rooted trees [Connes & Kreimer, 1999], is given by $(\mathcal{H}, \Delta_{BCK},\mu,\varepsilon_{BCK}, \emptyset, S_{BCK})$, where

• $\mathcal{H}$ is the set of all linear combinations of forests of (un)labelled trees
• Multiplication $\mu$ is defined as the commutative juxtaposition of trees
• Comultiplication $\Delta_{BCK}$ is defined by

\Delta_{BCK}(t) = t \otimes \emptyset + \emptyset \otimes t + \sum_{s \subset t} s \otimes [t\setminus s]

where the sum is over proper rooted subtrees $s$ of $t$, and $[t\setminus s]$ is the product of all branches formed when $s$ is erased from $t$.

• The unit $\emptyset$ is the empty tree
• The counit $\varepsilon_{BCK}$ is given by $\varepsilon(\tau) = 1$ if $\tau = \emptyset$ and $0$ otherwise
• The antipode $S_{BCK}$ is defined by

S_{BCK}(t) = -t - \sum_{s \subset t} S([t \setminus s])s, \quad S_{BCK}(\bullet) = -\bullet

Given two maps $f,g : \mathcal{H} \to \mathcal{H}$, we define their product map by

(f\cdot g)(\tau) = \mu \circ (f \otimes g) \circ \Delta(\tau).

The CEM Hopf Algebra

The Calaque, Ebrahimi-Fard and Manchon (CEM) [Calaque, Ebrahimi-Fard & Manchon, 2011] Hopf algebra $(\widetilde{H}, \Delta_{CEM}, \mu, \varepsilon_{CEM}, \bullet, S_{CEM})$ is defined as follows.

• $\widetilde{H}$ is the space of non-empty unlabelled trees, defined as $\widetilde{H} = H / J$ where $H$ is the space of unlabelled non-planar rooted trees and $J$ is the ideal generated by $\bullet - \emptyset$.
• The unit is the single-node tree, $\bullet$.
• The counit map is defined by $\varepsilon_{CEM}(\bullet) = 1$, $\varepsilon_{CEM}(t) = 0$ for all $\bullet \neq t \in \widetilde{H}$.
• Multiplication $\mu : \widetilde{H} \otimes \widetilde{H} \to \widetilde{H}$ is defined as the commutative juxtaposition of two forests.
• Comultiplication $\Delta : \widetilde{H} \to \widetilde{H} \otimes \widetilde{H}$ is defined as

\Delta_{CEM}(t) = \sum_{s \subset t} s \otimes t / s

where the sum runs over all possible subforests $s$ of $t$, and $t / s$ is the tree obtained by contracting each connected component of $s$ onto a vertex [Calaque, Ebrahimi-Fard & Manchon, 2011].

• The antipode $S_{CEM}$ is defined by $S_{CEM}(\bullet) = \bullet$ and

S_{CEM}(t) = -t - \sum_{t, \bullet \neq s \subset t} S_{CEM}(s) \,\, t / s.

Truncated B-series

Consider an ODE of the form

\frac{dy}{ds} = f(y)

Given a weights function $\varphi$, the associated truncated B-Series is

B_h(\varphi, y_0) := \sum_{|t| \leq n} \frac{h^{|t|}}{\sigma(t)} \varphi(t) F(t)(y_0),

where the sum runs over all trees of order at most $n$, $\sigma(t)$ is the symmetry factor of a tree, and $F(t)(y_0)$ are the elementary differentials, defined recursively on trees by:

F(\emptyset) = y,

F(\bullet) = f(y),

F([t_1, t_2, \ldots, t_k])(y) = f^{(k)}(y)(F(t_1)(y), F(t_2)(y), \ldots, F(t_k)(y)).

Citation

@misc{shmelev2025kauri,
  title={Kauri: Algebraic manipulation of non-planar rooted trees in Python},
  author={Shmelev, Daniil},
  year={2025},
  howpublished={\url{https://github.com/daniil-shmelev/kauri}}
}

References

• Connes, A., & Kreimer, D. (1999). Hopf algebras, renormalization and noncommutative geometry. In Quantum field theory: perspective and prospective (pp. 59–109). Springer.
• Calaque, D., Ebrahimi-Fard, K., & Manchon, D. (2011). Two interacting Hopf algebras of trees: A Hopf-algebraic approach to composition and substitution of B-series. Advances in Applied Mathematics, 47(2), 282–308. Elsevier.
• Beyer, T., & Hedetniemi, S. M. (1980). Constant time generation of rooted trees. In SIAM Journal on Computing 9.4 (pp. 706-712)