This seminar focuses mainly on computer algebra algorithms and implementations for solving mathematical problems exactly, with a special focus on polynomial system solving and its broad range of applications.

Among others, topics which are covered are:- Foundational computer algebra algorithms for polynomials, series and matrices
- Polynomial system solving with algebraic and/or certified numerical methods
- Applications of non-linear algebra algorithms such as cryptography, polynomial optimization, and computational geometry

Location

Laboratoire
d'Informatique de Paris 6 (UMR CNRS 7606)

Campus Pierre-et-Marie-Curie

Sorbonne Université

4 place Jussieu

75005 Paris, France

Campus Pierre-et-Marie-Curie

Sorbonne Université

4 place Jussieu

75005 Paris, France

Former Organizers

2020/09/01 – 2021/08/31

2020/09/01 – 2021/08/31

Alin
Bostan,
rf.airni@natsob.nila

Frédéric Chyzak, rf.airni@kazyhc.cirederf

Huu Phuoc Le, rf.6pil@el.couhp-uuh

Mohab Safey El Din, rf.6pil@yefas.bahom

Frédéric Chyzak, rf.airni@kazyhc.cirederf

Huu Phuoc Le, rf.6pil@el.couhp-uuh

Mohab Safey El Din, rf.6pil@yefas.bahom

*To receive further anouncements, register for the
mailing list here:*

via semi-numerical algorithms for polynomial systems

18 June 2021

11:00

Online seminar

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.

Bruno
Salvy,

Inria, LIP, ENS Lyon.

21 May 2021

11:00

Online seminar

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.

Didier
Henrion,

LAAS-CNRS Toulouse and Czech Tech. Univ. Prague.

7 May 2021

Online seminar

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.

Pierre Vanhove,

CEA (France) and HSE University (Moscow, Russia).

9 Apr. 2021

11:00

Online seminar

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.

Virginia Vassilevska Williams,

MIT (USA).

2 Apr. 2021

11:00

Online seminar

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.

Manfred
Buchacher,

Johannes Kepler Universität, Linz.

12 Mar. 2021

15:00-16:00

Online seminar

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.

Bernd
Sturmfels,

UC Berkeley and MPI Leipzig.

5 Mar. 2021

14:00-15:00

Online seminar

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.

Michela
Ceria,

Polytechnic University of Bari (Italy).

26 Feb. 2021

11:00-12:00

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.

Philippe
Moustrou,

U. Tromsø, (Norway).

19 Feb. 2021

11:00-12:00

Online seminar

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.

Ilaria
Zappatore,

Inria Saclay, (France).

12 Feb. 2021

11:00-12:00

Online seminar

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.

Thibaut
Verron,

Inst. for Algebra (Univ. J. Kepler, Austria).

4 Feb. 2021

14:00-15:00

Online seminar

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.

Simon
Abelard,

LIX, École polytechnique (France)

22 Jan. 2021

11:00-12:00

Online seminar

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.

Rémi
Imbach,

Courant Inst. (NYU, USA).

4 dec. 2020

11:00-12:00

Online seminar

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.

Gleb
Pogudin,

LIX, École polytechnique (France)

13 nov. 2020

15-16:30

Online seminar

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.

Diego Cifuentes,

MIT (USA)

6 nov. 2020

11:00-12:00

Room 25-26/105 + online

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.

Vincent
Neiger

XLIM, Univ. Limoges.

9 oct. 2020

11:00-12:00

Online seminar

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.

Khalil
Ghorbal,

Inria, Univ. Rennes 1 (France)

11 sep. 2020

15:00-16:00

Online seminar

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

George Labahn

Univ. Waterloo, Canada

3 july 2020

10:30-11:30

Online seminar

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.

Alin Bostan

INRIA.

19 june 2020

11:00-12:00

Online seminar

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.

Simone Naldi

XLIM, Univ. Limoges.

13 mars 2020

11:00-12:30

26-00/332

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.

Victor Magron

LAAS

28 fev. 2020

15:00-17:00

26-00/332

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.

Philippe Moustrou

Univ. of Tromso, Norway.

14 nov. 2019

10:30-12:00

24-25/405

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

Vincent
Neiger

XLIM, Univ. Limoges.

25 sep. 2019

13:00-14:00

24-25/405

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.

Anton Leykin

Georgia Tech., USA.

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

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

Jan. 29th, Feb. 5th, Feb. 17th 2021

conference

ITN POEMA 3rd workshop. Oct. Nov. Dec. 2020