## This is the "Seminar" web page of the PolSys Team.

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
We also organize reading groups on important computer algebra algorithms.
location
Laboratoire d'Informatique de Paris 6 (UMR CNRS 7606)
Campus Pierre et Marie Curie
Sorbonne Université
Paris France
organizers

## Next seminars

### Characterizing Positively Invariant Sets: Inductive and Topological Methods

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)

### Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation

6 nov. 2020

10:30-12:00

Room ?

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.

## Past seminars

### Symbolic/Numeric Computation with Matrix Polynomials

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

### Computing the $N$-th term of a $q$-holonomic sequence

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.

### Gröbner bases of syzygy modules and multivariate Padé approximation

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.

### The quest of efficiency and certification in polynomial optimization

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.

### Exact semidefinite programming bounds for packing problems

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.

### On the complexity of modular composition of generic polynomials

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, Eric Schost, Gilles Villard

Vincent Neiger

XLIM, Univ. Limoges.

### Nonlinear algebra for computer vision

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.

## Past events

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