Kurusch Ebrahimi-Fard

Daniil Shmelev, Kurusch Ebrahimi-Fard, Nikolas Tapia et al.

Symmetry is a key property of numerical methods. The geometric properties of symmetric schemes make them an attractive option for integrating Hamiltonian systems, whilst their ability to exactly recover the initial condition without the need to store the entire solution trajectory makes them ideal for the efficient implementation of Neural ODEs. In this work, we present a Hopf algebraic approach to the study of symmetric B-series methods. We show that every B-series method can be written as the composition of a symmetric and "antisymmetric" component, and explore the structure of this decomposition for Runge-Kutta schemes. A major bottleneck of symmetric Runge-Kutta schemes is their implicit nature, which requires solving a nonlinear system at each step. By introducing a new set of order conditions which minimise the antisymmetric component of a scheme, we derive what we call Explicit and Effectively Symmetric (EES) schemes -- a new class of explicit Runge-Kutta schemes with near-symmetric properties. We present examples of second-order EES schemes and demonstrate that, despite their low order, these schemes readily outperform higher-order explicit schemes such as RK4 and RK5, and achieve results comparable to implicit symmetric schemes at a significantly lower computational cost.

Damien Calaque, Kurusch Ebrahimi-Fard, Dominique Manchon

Hopf algebra structures on rooted trees are by now a well-studied object, especially in the context of combinatorics. In this work we consider a Hopf algebra H by introducing a coproduct on a (commutative) algebra of rooted forests, considering each tree of the forest (which must contain at least one edge) as a Feynman-like graph without loops. The primitive part of the graded dual is endowed with a pre-Lie product defined in terms of insertion of a tree inside another. We establish a surprising link between the Hopf algebra H obtained this way and the well-known Connes-Kreimer Hopf algebra of rooted trees by means of a natural H-bicomodule structure on the latter. This enables us to recover recent results in the field of numerical methods for differential equations due to Chartier, Hairer and Vilmart as well as Murua.

Kurusch Ebrahimi-Fard, Alexander Lundervold, Simon J. A. Malham et al.

We investigate the algebraic structure underlying the stochastic Taylor solution expansion for stochastic differential systems.Our motivation is to construct efficient integrators. These are approximations that generate strong numerical integration schemes that are more accurate than the corresponding stochastic Taylor approximation, independent of the governing vector fields and to all orders. The sinhlog integrator introduced by Malham & Wiese (2009) is one example. Herein we: show that the natural context to study stochastic integrators and their properties is the convolution shuffle algebra of endomorphisms; establish a new whole class of efficient integrators; and then prove that, within this class, the sinhlog integrator generates the optimal efficient stochastic integrator at all orders.

Charles Curry, Kurusch Ebrahimi-Fard, Hans Munthe-Kaas

We explain the notion of a post-Lie algebra and outline its role in the theory of Lie group integrators.

Joscha Diehl, Kurusch Ebrahimi-Fard, Nikolas Tapia

We explore the algebraic properties of a generalized version of the iterated-sums signature, inspired by previous work of F.~Király and H.~Oberhauser. In particular, we show how to recover the character property of the associated linear map over the tensor algebra by considering a deformed quasi-shuffle product of words on the latter. We introduce three non-linear transformations on iterated-sums signatures, close in spirit to Machine Learning applications, and show some of their properties.

Joscha Diehl, Kurusch Ebrahimi-Fard, Nikolas Tapia

Aiming for a systematic feature-extraction from time series, we introduce the iterated-sums signature over arbitrary commutative semirings. The case of the tropical semiring is a central, and our motivating example. It leads to features of (real-valued) time series that are not easily available using existing signature-type objects. We demonstrate how the signature extracts chronological aspects of a time series, and that its calculation is possible in linear time. We identify quasisymmetric expressions over semirings as the appropriate framework for iterated-sums signatures over semiring-valued time series.

Joscha Diehl, Kurusch Ebrahimi-Fard, Nikolas Tapia

In data science, one is often confronted with a time series representing measurements of some quantity of interest. Usually, as a first step, features of the time series need to be extracted. These are numerical quantities that aim to succinctly describe the data and to dampen the influence of noise. In some applications, these features are also required to satisfy some invariance properties. In this paper, we concentrate on time-warping invariants. We show that these correspond to a certain family of iterated sums of the increments of the time series, known as quasisymmetric functions in the mathematics literature. We present these invariant features in an algebraic framework, and we develop some of their basic properties.

W. Steven Gray, Luis A. Duffaut Espinosa, Kurusch Ebrahimi-Fard

A convenient way to represent a nonlinear input-output system in control theory is via a Chen-Fliess functional expansion or Fliess operator. The general goal of this paper is to describe how to approximate Fliess operators with iterated sums and to provide accurate error estimates for two different scenarios, one where the series coefficients are growing at a local convergence rate, and the other where they are growing at a global convergence rate. In each case, it is shown that the error estimates are achievable in the sense that worst case inputs can be identified which hit the error bound. The paper then focuses on the special case where the operators are rational, i.e., they have rational generating series. It is shown in this situation that the iterated sum approximation can be realized by a discrete-time state space model which is a rational function of the input and state affine. In addition, this model comes from a specific discretization of the bilinear realization of the rational Fliess operator.

Kurusch Ebrahimi-Fard, Alexander Lundervold, Hans Munthe-Kaas

We consider pairs of Lie algebras $g$ and $\bar{g}$, defined over a common vector space, where the Lie brackets of $g$ and $\bar{g}$ are related via a post-Lie algebra structure. The latter can be extended to the Lie enveloping algebra $U(g)$. This permits us to define another associative product on $U(g)$, which gives rise to a Hopf algebra isomorphism between $U(\bar{g})$ and a new Hopf algebra assembled from $U(g)$ with the new product. For the free post-Lie algebra these constructions provide a refined understanding of a fundamental Hopf algebra appearing in the theory of numerical integration methods for differential equations on manifolds. In the pre-Lie setting, the algebraic point of view developed here also provides a concise way to develop Butcher's order theory for Runge--Kutta methods.