Alexander Demin

Alexander Demin

A standard way to control expression swell in computer algebra is to use multi-modular or evaluation-interpolation methods. In computations involving Gröbner bases, these techniques typically require repeatedly computing Gröbner bases of specializations of the same ideal. These repeated computations can be accelerated through precomputation, notably using Traverso's tracing. We present Groebner.jl (https://github.com/sumiya11/Groebner.jl), a Julia implementation of the F4 algorithm that exposes Traverso's tracing through a reusable public interface. The implementation supports SIMD-friendly coefficient types, such as tuples of machine integers, which Julia compiles to efficient code with little manual intervention. This lets other Julia software leverage tracing to obtain speedups in applications such as structural identifiability of ordinary differential equation models and polynomial system solving.

Alexander Demin, Fabrice Rouillier

In this note, we present RationalUnivariateRepresentation.jl (https://newrur.gitlabpages.inria.fr/RationalUnivariateRepresentation.jl/), a Julia package for computing rational univariate representations of zero-dimensional polynomial systems. The package uses dense linear algebra and Gaussian elimination for the FGLM-like stage. The purpose of this contribution is to advocate for this choice and explain the implementation details that turn the algorithm into practical software. In particular, we show that our implementation can compute guaranteedly correct parametrizations of ideals with thousands of solutions within seconds.