Joint MATHEXP–PolSys Seminar. (Archive)

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
LIP6 (UMR CNRS 7606)
Campus Pierre-et-Marie-Curie
Sorbonne Université
4 place Jussieu
75005 Paris, France
or
Inria Saclay – Île-de-France
Bâtiment Alan Turing
Campus de l'École polytechnique
1 rue Honoré d'Estienne d'Orves
91120 Palaiseau, France
Organizers
Former Organizers
2020/09/01 – 2021/08/31

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

https://listes.lip6.fr/sympa/subscribe/polsys-seminar

Upcoming seminars and events

• 1s July 2022, 11:00
seminar
with GT TC

Sums of powers of binomials, their Apéry limits, and Franel's suspicions
Armin Straub

Department of Mathematics and Statistics, Univ. of South Alabama

• 5th–9th Sept. 2022
workshop
• Sept.–Dec. 2023
conference
• 2024
conference

Next seminars

Sums of powers of binomials, their Apéry limits, and Franel's suspicions

1st July 2022

11:00

25-26/105 & online

Co-organized with Groupe de travail « Transcendance et combinatoire »

Apéry's proof of the irrationality of $\zeta(3)$ relies on representing that value as the limit of the quotient of two rational solutions to a three-term recurrence. We review such Apéry limits and explore a particularly simple instance. We then explicitly determine the Apéry limits attached to sums of powers of binomial coefficients. As an application, we prove a weak version of Franel's conjecture on the order of the recurrences for these sequences. This is based on joint work with Wadim Zudilin.

Armin Straub

Department of Mathematics and Statistics, University of South Alabama

Past seminars

Sparse polynomial interpolation and exact division over $\mathbb{Z}$

10 June 2022

11:00

25-26/105 & online

We present a new Monte Carlo randomized algorithm to recover an integer polynomial $f(x)$ given a way to evaluate $f(a) \bmod m$ for any chosen integers $a$ and $m$. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. The best previously known results have at least a cubic dependency on the bit-length of the exponents. This is a joint work with Pascal Giorgi, Bruno Grenet and Daniel S. Roche.

Armelle Perret du Cray

Team ECO, LIRMM
Université de Montpellier

Validated Numerics and Formal Proof for Computer-Aided Proofs in Mathematics: A Case Study on Abelian Integrals

13 May 2022

11:00

Inria Saclay, amphitheatre Sophie-Germain & online

Validated Numerics and Formal Proof for Computer-Aided Proofs in Mathematics: A Case Study on Abelian Integrals Last decades saw the emergence of validated numerics (i.e., numerical computations with rigorous error bounds) in computer-aided proofs for mathematics, with major achievements notably in analysis and dynamical systems. This raises questions and challenges which computer scientists are familiar with, such as complexity (how long does is take to compute N correct digits?) and reliability (can we trust an implementation the same way we do for pen-and-paper mathematics?). In this talk, we will illustrate these challenges with a concrete problem, namely the rigorous numerical evaluation of Abelian integrals. These functions play an essential role in Hilbert's sixteenth problem, since their zeros are connected to the limit cycles of perturbed planar Hamiltonian vector fields. Using truncated Fourier series and rigorous error bounds obtained via fixed- point theorems, we design an efficient algorithm that is also suitable for a formal proof implementation in the Coq theorem prover. Also, we will discuss strategies to compute continuous representations (Taylor, Chebyshev...) of such functions via the associated Picard-Fuchs ODE, and the perspectives of formalizing them in Coq. This is a joint work with Nicolas Brisebarre, Mioara Joldes and Warwick Tucker.

Florent Bréhard

Centre de Recherche en Informatique, Signal et Automatique de Lille

Modeling piecewise polynomial functions with polynomial minimizers

22 April 2022

11:00

25-26/105 & online

In data science, the quantity to be approximated numerically can be a discontinuous function, e.g. the solution of a nonlinear PDE with shocks, or a bang-bang optimal control. Numerical algorithms may face troubles when approximating such functions, e.g. standard polynomial approximations suffer from the Gibbs phenomenon, namely large oscillations near the discontinuity points that do not vanish when the polynomial degree goes to infinity. In this talk, we introduce a new family of functions designed to deal with such discontinuities. We propose to model or approximate a function of a vector x by the minimizer with respect to additional (lifting) variables y of a polynomial of x and y. We show that piecewise polynomial functions can be modeled exactly this way. For any Lebesgue measurable function, we describe a systematic method to construct a family of approximants of increasing degree such that their minimizers converge to the function pointwise almost everywhere and in the Lebesgue one norm. These approximants are polynomial sums of squares generated from the moments or the samples of the function.

Didier Henrion

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

$p$-adic Algorithm to Find a Basis of Bivariate Primary Components

25 February 2022

15:00

Online

Inspired by the characterization of a Gröbner cell from Conca and Valla [2007], we will present a quadratic convergent $p$-adic algorithm that we developed to find a basis of a primary component of a zero-dimensional ideal $I \subset \mathbb{K}[x,y]$, where $\mathbb{K}$ is a rational function field (or the rationals). We will also discuss the probability of finding a "good prime" for the $p$-adic expansion and bound the growth of the coefficients in a basis.

Catherine St-Pierre,

University of Waterloo.

On Finite Convergence and Convergence Rates in Polynomial Optimization

18 February 2022

11:00

Online

In Polynomial Optimization, finite convergence of the Lasserre's Moment and Sums of Squares hierarchies is often observed in applications, but it is less understood theoretically. We show that finite convergence happens under the so-called Boundary Hessian Conditions at the minimizers, and that this degree is related to the Castelnuovo-Mumford regularity of the ideal they define. On the contrary, the general, theoretical convergence rate is not well understood, and is deduced from effective versions of Putinar's Positvstellensatz. We give new polynomial bounds for this theorem: these bounds involve a Łojasiewicz exponent associated to the description of the semialgebraic set and, under regularity conditions, to the conditioning number of the Jacobian matrix of the defining inequalities.
Based on joint works with Bernard Mourrain.

Lorenzo Baldi,

Team AROMATH, Inria Sophia Antipolis-Méditerranée.

New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems

21 January 2022

11:00

Online

We present a new data structure to approximate accurately and efficiently a polynomial f of degree d given as a list of coefficients. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multipoint evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2.

Guillaume Moroz,

Team Gamble, Inria Nancy – Grand Est.

Multiplication in finite fields with Chudnovsky-type algorithms over the projective line.

10 December 2021

10:30

25-26/105 & online

We propose a generic construction of interpolation algorithms over the projective line for the multiplication in any finite extension of finite fields. This is a specialization of the method of interpolation on algebraic curves introduced by David and Gregory Chudnovsky. We will use generalizations of this method, in particular the evaluation at places of arbitrary degrees. Our algorithms correspond to usual techniques of polynomial interpolation in small extensions and are defined recursively as the degree of the extension increases. We show that their bilinear complexity is competitive and that they can be constructed in polynomial time.

Bastien Pacifico,

I2M, Aix Marseille Université.

Fast list decoding of algebraic geometry codes

22 November 2021

14:00

24-25/509 & online

In this talk, we present an efficient list decoding algorithm for algebraic geometry (AG) codes. They are a natural generalization of Reed-Solomon codes and include some of the best codes in terms of robustness to errors. The proposed decoder follows the Guruswami-Sudan paradigm and is the fastest of its kind, generalizing the decoder for one-point Hermitian codes by J. Rosenkilde and P. Beelen to arbitrary AG codes. In this fully general setting, our decoder achieves the complexity $\widetilde{\mathcal{O}}(s \ell^{\omega}\mu^{\omega - 1}(n+g))$, where $n$ is the code length, $g$ is the genus, $\ell$ is the list size, $s$ is the multiplicity and $\mu$ is the smallest nonzero element of the Weierstrass semigroup at some special place.
Joint work with J. Rosenkilde and P. Beelen.

Grigory Solomatov,

Department of Applied Mathematics and Computer Science Mathematics, Danmarks Tekniske Universitet.

Computing the Smith normal form and multipliers of a nonsingular integer matrix

19 November 2021

11:00

25-26/105 & online

The Smith normal form of an $n \times n$ matrix $A$of integers or polynomials is a diagonal matrix S$= \operatorname{diag}(s_1, s_2, … , s_n)$ satisfying $s_1 | s_2 | .. | s_n$ with $A V = U S$, where $U$ and $V$ are unimodular matrices (i.e. $\det U = \det V = \pm 1$ (integers) or a constant (polynomials). The $U$ and $V$ matrices represent row and column operations converting $A$ into $S$.
In this talk we give a Las Vegas randomized algorithm for computing $S, U, V$ in the case where the matrix $A$ is a nonsingular integer matrix. The expected running time of our algorithm is about the same as the cost required to multiply two matrices of the same dimension and size of entries of $A$. We also give explicit bounds on the sizes of the entries of our unimodular multipliers. The main tool used in our construction is the so called Smith massager, a relaxed version of our column multiplier $V$.
This is joint work with Stavros Birmpilis and Arne Storjohann

George Labahn,

Cheriton School of Computer Science, University of Waterloo.

C2-finite sequences

15 October 2021

11:00

Inria Saclay, amphitheatre Sophie-Germain & online

Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as P-finite sequences. A subclass are C-finite sequences satisfying a linear recurrence with constant coefficients.
We'll see in this talk a natural extension of this set of sequences: which satisfy linear recurrence equations with coefficients that are C-finite sequences. We will show that C2-finite sequences form a difference ring and provide methods to compute in this ring.

Antonio Jiménez-Pastor,

LIX, École polytechnique.

Truncated Moment Cone and Connections to the Coalescence Manifold

24 September 2021

11:00

25-26/105 & online

We study the univariate moment problem of piecewise-constant density functions on the interval [0, 1] and its consequences for an inference problem in population genetics. We show that, up to closure, any collection of n moments is achieved by a step function with at most n-1 breakpoints and that this bound is tight. We use this to show that any point in the n-th coalescence manifold in population genetics can be attained by a piecewise constant population history with at most n-2 changes. We give a semi-algebraic description of the n-th coalescence manifold as a projected spectrahedron.

Georgy Scholten,

PolSys, LIP6, Sorbonne Université.