The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables. This is joint work with Stephen Melczer.

The moment-SOS hierarchy can be used to approximate numerically the volume of a semialgebraic set $X$ at the price of solving increasingly large convex optimization problems. In its original form, the dual SOS problem in the hierarchy consists of approximating from above the indicator function of $X$ with a polynomial of increasing degree, thereby suffering from the Gibbs effect (large overshoots near the discontinuity points).
In this talk we explain how to suppress this effect by adding redundant linear constraints in the primal moment problem. These constraints are a consequence of Stokes' theorem. This results in a significant acceleration of the hierarchy.
This is joint work with Matteo Tacchi and Jean Bernard Lasserre, see arXiv:2009.12139 or hal:02947268.

In this talk we will present various methods for computing the Picard-Fuchs equations for Feynman integrals that arise in quantum field theory. After reviewing the main properties of Feynman integrals, we will discuss two methods for deriving their ideal of differential equations, a first one using the Gel'fand-Kapranov-Zelevinsky construction and the other one using the creative telescoping. In this talk we will compare the two approaches and give a physical intepretation of the certificate.

This based on some work done in collaboration with Charles Doran and Andrey Novoseltsev.

The complexity of matrix multiplication is measured in terms of $\omega$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n\cdot \omega + \varepsilon)$ field operations for all $\varepsilon > 0$; the best bound until now is $\omega \leq 2.37287$ [Le Gall '14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the “value” of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date: $\omega \leq 2.37286$. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.

Joint work with Josh Alman.

We present an algorithm which for any given ideal $I \subseteq \mathbb{K}[x,y]$ computes $I \cap (\mathbb{K}[x] + \mathbb{K}[y])$. Our motivation for looking at the problem came from enumerative combinatorics in the context of lattice walks: an elimination of this kind appears in Bousquet-Mélou's proof of the algebraicity of the generating function of Gessel's walks. The problem also arises when one wants to compute the intersection of two $\mathbb{K}$-algebras.

This is joint work with Manuel Kauers and Gleb Pogudin.

We discuss algebraic methods for solving systems of homogeneous linear partial differential equations with constant coefficients. The setting is the Fundamental Principle established by Ehrenpreis and Palamodov in the 1960’s. Our approach rests on recent advances in commutative algebra, and it offers new vistas on schemes and coherent sheaves in computational algebraic geometry.

Given a finite set of simple points, it is possible to find a basis for the quotient algebra of the polynomial ring modulo the ideal of such points without the need of computing the ideal itself, neither its Gröbner basis. In this talk, we will see an algorithm (Iterative Lex Game) for this aim, computing, as such basis, the lexicographical Gröbner escalier associated to a finite set of simple points by means of combinatorial operations on the points' coordinates. We will also compare the Iterative Lex Game with the other two existing algorithms designed for the same aim (Cerlienco-Mureddu algorithm and the Lex Game).
Then, we will give an application to Coding Theory of such algorithm. The study of the escalier of a suitable finite set of simple points, indeed, is a crucial step for efficient decoding of binary cyclic codes by means of the constructions of special polynomials, the Half Error Locator polynomials.

In the first part of the talk, we will discuss symmetric polynomial ideals, namely ideals of polynomials closed under permutations of variables. The Specht polynomials are fundamental in the understanding of the representations of the symmetric group. We show a connection between the leading monomials of polynomials in a symmetric ideal and the Specht polynomials contained in the ideal. This provides applications in several contexts, in particular for algorithmic purposes. Most notably, this connection gives information about the points in the corresponding algebraic variety. From another perspective, it restricts the isotypic decomposition of the ideal viewed as a representation of the symmetric group.This allows further algorithmic consequences, in particular for non-negativity certifications of symmetric polynomials on symmetric variety via sums of squares.
Besides sums of squares, alternative methods have been recently introduced to certify the non-negaitivity of polynomials. The second part of the talk will focus on methods based on Sums of Arithmetic-Geometric Exponentials (SAGE) and Sums Of Non-negative Circuit polynomials (SONC) for symmetric polynomials. We will discuss the theoretical aspects such as the comparison between these cones and the cone of non-negative symmetric polynomials, as well as symmetry-reduction techniques for the corresponding algorithms.

Based on joint works with Helen Naumann, Cordian Riener, Thorsten Theobald and Hugues Verdure.

The simultaneous rational function reconstruction (SRFR) is the problem of reconstructing a vector of rational functions with the same denominator given its evaluations (or more generally given its remainders modulo different polynomials).
The peculiarity of this problem consists in the fact that the common denominator constraint reduces the number of evaluation points needed to guarantee the existence of a solution, possibly losing the uniqueness.
One of the main contributions presented in this talk consists in the proof that uniqueness is guaranteed for almost all instances of this problem.
This result was obtained by elaborating some other contributions and techniques derived by the applications of SRFR, from the polynomial linear system solving to the decoding of Interleaved Reed-Solomon codes.
In this talk it is also presented another application of the SRFR problem, concerning the problem of constructing fault-tolerant algorithms: algorithms resilient to computational errors.
These algorithms are constructed by introducing redundancy and using error correcting codes tools to detect and possibly correct errors which occur during computations. In this application context, we improve an existing fault-tolerant technique for polynomial linear system solving by interpolation-evaluation, by focusing on the related SRFR.

Contains joint works with Eleonora Guerrini and Romain Lebreton.

Tate series are a generalization of polynomials introduced by John Tate in 1962, when defining a $p$-adic analogue of the correspondence between algebraic geometry and analytic geometry. This $p$-adic analogue is called rigid geometry, and Tate series, similar to analytic functions in the complex case, are its fundamental objects. Tate series are defined as multivariate formal power series over a $p$-adic ring or field, with a convergence condition on a closed ball.
Tate series are naturally approximated by multivariate polynomials over $\mathbb{F}_p$ or $\mathbb{Z}/p^n \mathbb{Z}$, and it is possible to define a theory of Gröbner bases for ideals of Tate series, which opens the way towards effective rigid geometry. In this talk, I will present those definitions, as well as different algorithms to compute Gröbner bases for Tate series.

Joint work with Xavier Caruso and Tristan Vaccon.

In this talk we will discuss two different algorithmic problems related to algebraic curves : counting points and computing Riemann-Roch spaces, both of them having applications in various fields of computer science such as cryptography and coding theory. These tasks are actually closely related to well-known problems from computer algebra.
The first problem mostly boils down to solving polynomial systems. We will see how the underlying structure of these systems helps to derive better complexity bounds and to perform practical computations.
For the second problem, previous algorithms (Khuri-Makdisi in 2007, Le Gluher and Spaenlehauer in 2018) compute Riemann-Roch spaces through the use of linear algebra. The main novelty of our work is to rely on a $K[X]$-module structure instead so that we can replace linear algebra by faster algorithms for computing interpolation bases (such as the one of Neiger in 2016), thus deriving a subquadratic complexity bound. We will also talk about the ongoing implementation of this algorithm.

The first part of the talk contains joint work with P. Gaudry and P.-J. Spaenlehauer, the second part is joint work with A. Couvreur and G. Lecerf.

We are interested in computing clusters of complex roots of polynomials and square polynomials systems. Root clustering differs of root isolation in that it can be performed softly, i.e. avoiding some decisions of zero. This allows clustering algorithms to be robust to multiple roots and to accept inputs given by black boxes for approximation, for instance polynomials which coefficients are in towers of field extensions. The starting point of our talk is the existence of a clustering algorithm for roots of univariate polynomials. We will show how this algorithm can be embedded in an algorithm for computing clusters of roots of triangular systems of polynomials resulting in particular of a symbolic step to process non-triangular systems. We will also present recent practical improvements for the univariate case.

Elimination of unknowns in systems of polynomial equations is a standard tool of computational algebra and algebraic geometry going back to the pioneers of the subject. An analogous question of elimination of unknowns in differential-algebraic equations can be stated as follows: given a system of nonlinear differential equations in two groups of variables, $x$'s and $y$'s, describe all the consequences of the system depending solely on $x$'s. Such a differential elimination problem has been studied already by Joseph Ritt, the founder of differential algebra, who proposed the first algorithm for solving it in 1930's. Collective effort of many researchers in the field aimed at understanding and improving this algorithm culminated in modern differential elimination algorithms such as the Rosenfeld-Gröbner algorithm which is now a part of the Maple standard library.
I will talk about differential elimination from the point of view of applications to modeling. Differential elimination is the key step in one of the approaches to the parameter identifiability problem (to decide whether or not parameters can in principle be recovered from the observations). A big portion of dynamical models used in sciences are ODE system, that is, are of the form $x' = f(x)$. General algorithms like the Rosenfeld-Gröbner algorithm are applicable in this situation but there is a price to pay for their generality and versatility: many interesting instances cannot be tackled by them in reasonable time. I will describe a new projection-based elimination algorithm tailored to ODE systems which allows to perform elimination (and then assess parameter identifiability) for systems that could not be tackled before. I will conclude by speculating about potential applications of this algorithm in other domains where ODE systems often appear, for example, for computations with differential-algebraic functions.

This is based on joint work in progress with Ruiwen Dong, Emilie Dufresne, Christian Goodbrake, and Heather Harrington.

The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks. In particular, the notion of chordality and treewidth play a pivotal role in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. Our main contribution is the introduction of a new representation of structured polynomial systems: “chordal networks”. Chordal networks provide a computationally convenient decomposition of the system into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. We illustrate through examples from different application domains that algorithms based on chordal networks can significantly outperform existing techniques.

This talk presents joint work with J. Rosenkilde and G. Solomatov, about new algorithms for bivariate multi-point evaluation, interpolation and modular composition, which under certain assumptions have quasi-linear complexity. For multi-point evaluation and interpolation we assume that the set of points is generic and available for precomputation. In the case of modular composition, similar assumptions are made on a bivariate ideal which depends on part of the input. The key tool is an algorithm that reshapes the degree bounds of a given bivariate polynomial while preserving its membership in a coset of some fixed bivariate ideal available for precomputation.

Set positive invariance is an important concept in the theory of dynamical systems and one which also has practical applications in areas of computer science, such as formal verification, as well as in control theory. Great progress has been made in understanding positively invariant sets in continuous dynamical systems and powerful computational tools have been developed for reasoning about them; however, many of the insights from recent developments in this area have largely remained folklore and are not elaborated in existing literature. This presentation contributes an explicit development of modern methods for checking positively invariant sets of ordinary differential equations and describes two possible characterizations of positive invariants: one based on the real induction principle, and a novel alternative based on topological notions. The two characterizations, while in a certain sense equivalent, lead to two different decision procedures for checking whether a given semi-algebraic set is positively invariant under the flow of a system of polynomial ordinary differential equations.

This is a joint work with Andrew Sogokon from University of Southampton, UK.

Given a nonsingular matrix polynomial $A$ whose coefficients are floating point numbers, we discuss a number of "nearest" approximation algebra problems. This includes finding the nearest singular matrix polynomial, the nearest polynomial matrix having a specified rank and finding a nearest interesting Smith normal form. We show that solving such problems are amenable to numeric computation as optimization problems. This includes determining the geometry and existence of nearest solutions and providing iterative numerical methods for computing these solutions.

This is joint work with Mark Giesbrecht and Joseph Haraldson

In 1977, Strassen invented a famous baby-step / giant-step algorithm that computes the factorial $N!$ in arithmetic complexity quasi-linear in $\sqrt{N}$. In 1988, the Chudnovsky brothers generalized Strassen’s algorithm to the computation of the $N$-th term of any holonomic sequence in the same arithmetic complexity. We design $q$-analogues of these algorithms.
We first extend Strassen's algorithm to the computation of the $q$-factorial of $N$, then Chudnovskys' algorithm to the computation of the $N$-th term of any $q$-holonomic sequence. Both algorithms work in arithmetic complexity quasi-linear in $\sqrt{N}$.
We describe various algorithmic consequences, including the acceleration of polynomial and rational solving of linear $q$-differential equations, and the fast evaluation of large classes of polynomials including a family recently considered by Nogneng and Schost.

Given elements $f_1, \ldots, f_m$ in a quotient $R^n / N$ of finite dimension as a $K$-vector space, where $R = K[X_1,\ldots,X_r]$ and $N$ is an $R$-submodule of $R^n$, we consider the problem of computing a Gröbner basis of the module of syzygies of $(f_1, \ldots, f_m)$, that is, of the set of vectors $(p_1, \ldots, p_m) \in R^m$ such that $p_1 f_1+\cdots+p_m f_m = 0$.
An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of the base module as the kernel of a collection of linear functionals. Following this viewpoint, we design a divide-and-conquer algorithm, which can be interpreted as a generalization to several variables of Beckermann-Labahn's recursive approach for matrix Padé and rational interpolation problems.
To highlight the interest of this method, we focus on the specific case of bivariate Padé approximation and show that it improves upon the best known complexity bounds.

Joint work with Vincent Neiger.

In 2001, Lasserre introduced a nowadays famous hierarchy of relaxations, called the moment-sums of squares hierarchy, allowing one to obtain a converging sequence of lower bounds for the minimum of a polynomial over a compact semialgebraic set. Each lower bound is computed by solving a semidefinite program (SDP).
There are two common drawbacks related to this hierarchy. First, the size of the SDP problems arising from the hierarchy grows rapidly. Second, one relies on numerical SDP solvers, implemented in finite-precision, thus providing only approximate certificates.
In this talk, we explain how to address these two efficiency and certification issues.
In the first part, we recall how to exploit the sparsity pattern arising in polynomial optimization problems. We present one application for an optimization problem in commuting variables, which is a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. Then we present one application for optimization problems in non-commuting variables, which is a converging hierarchy of SDP relaxations for eigenvalue and trace optimization.
In the second part, we provide a hybrid symbolic-numeric algorithm computing exact rational sums of squares (SOS) decompositions for polynomials lying in the interior of the SOS cone. This algorithm computes an approximate decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact decomposition is obtained thanks to the perturbation terms. Then, we apply this algorithm to compute exact Polya and Putinar’s representations respectively for positive definite forms and polynomials positive over basic compact semialgebraic sets.

In the first part of the talk, we present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E8 is the unique solution for the kissing number problem on the hemisphere in dimension 8.
However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, we explain how, via our rounding procedure, we can obtain an exact rational solution of semidefinite program from an approximate solution in floating point given by the solver.

Joint work with Maria Dostert and David de Laat.

This talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials $a$ and $g$ over a commutative field, modular composition asks to compute $h(a) \mod g$ for some given $h$, while the minimal polynomial problem is to compute h of minimal degree such that $h(a) = 0 \mod g$. For generic $g$ and $a$, we propose algorithms whose complexity bound improves upon previous algorithms and in particular upon Brent and Kung's approach (1978); the new complexity bound is subquadratic in the degree of $g$ and $a$ even when using cubic-time matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals, and from efficient operations with these bases thanks to fast univariate polynomial matrix algorithms.

Contains joint work with Seung Gyu Hyun, Bruno Salvy, Éric Schost, Gilles Villard

3D reconstruction of points and lines from images is an important and frequently studied problem. So-called minimal problems are essential ingredients in the structure-from-motion pipeline used for 3D reconstruction. We produce complete catalogs of minimal problems in two natural settings.
The first catalog consists of 30 minimal problems assuming complete visibility. The second one lists more than 100,000 classes of equivalence of nonreducible noncollinear problems in the partial visibility setting. Using fast implementations of Groebner bases and homotopy continuation methods we computed the degrees (numbers of solutions) of the problems in the first catalog. Finding interesting problems and their degrees in the second catalog is an ongoing project --- some of these provide a challenge to the aforementioned computational methods.

Joint work with Tim Duff, Kathlen Kohn, and Tomas Pajdla.

conference SESAME day 15 Feb. 2021.
conference ITN POEMA workshop. Jan.-Feb. 2021.
conference ITN POEMA learning weeks. May-Sep. 2020.
conference SESAME days, Jul. 2020
conference Oberwolfach workshop on Real Algebraic Geometry with a View Toward Hyperbolic Programming and Free Probability, Mar. 2020
conference ANR SESAME Meeting at IRISA, Rennes, Feb. 2020
conference ANR DRN kick-off meeting, Saclay, Feb. 2020
conference ITN POEMA workshop, Firenze, Italy, Jan. 2020