The joint MATHEXP-Polsys seminar

Since 2021 the Specfun seminar has merged with the Polsys seminar. In 2022, Specfun becomes MATHEXP. The joint seminar is held in Paris or Palaiseau and broadcasted online.

Upcoming talks

NEXT Differential and difference equations from linear fibrations

speaker
Erik Panzer, Mathematical Institute, University of Oxford (UK)
date
Friday, 24 March 2023 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
abstract
Integrals in many variables can be evaluated more efficiently if the dependence of the integrand on a suitable variable is particularly simple. I will talk about algorithms for hyperlogarithms, an old class of special functions which arise from iterating integrals of rational functions and have many applications. I will also discuss how to predict the singularities of many-variable integrals, which applies more generally, and is useful to pick an integration order. Finally, I will discuss applications to hypergeometric functions, that is, integrands with symbolic exponents, and applications to Feynman integrals.

2023

PAST Toric varieties and Gibbs manifolds in convex optimization

speaker
Simon Telen, CWI, Amsterdam (Netherlands)
date
Friday, 3 March 2023 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

Entropic regularization for linear programming leads to intersecting a toric variety with the feasible polytope. In semidefinite programming, the toric variety is replaced by a new geometric object, called Gibbs manifold, and the feasible polytope becomes a spectrahedron. I will explain these concepts and present the example of (quantum) optimal transport.

This is based on joint work with Dmitrii Pavlov, Bernd Sturmfels, François-Xavier Vialard and Max von Renesse.

PAST The moment problem and convex hulls of semialgebraic sets

speaker
Simone Naldi, XLIM, université de Limoges (France)
date
Friday, 17 February 2023 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract
The duality between moments of measures with support contained in a semialgebraic set $$K$$, and the cone of polynomials nonnegative on $$K$$, is the context of the so-called Moment-SOS (a.k.a. Lasserre) hierarchy, for relaxing polynomial optimization problems to several semidefinite programs. In this talk I will discuss the problem of computing the convex hull of a compact semialgebraic set $$K$$: geometrically, this corresponds to the intersection of all linear hyperspaces containing $$K$$, and algebraically, it consists of representing all linear functions that are positive over $$K$$ with weighted SOS certificates. I will present a recent new primal-dual certificate, based on a joint work with D. Henrion. In the last part of the talk, I will discuss algorithmic and complexity aspects of the so-called truncated moment problem for compact basic semialgebraic sets, based on joint work with D. Henrion and M. Safey El Din.

PAST Faster computation of elementary functions

speaker
Fredrik Johansson, Inria, IMB, université de Bordeaux (France)
date
Friday, 27 January 2023 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
abstract
Over a decade ago, Arnold Schönhage proposed a method to compute elementary functions (exp, log, sin, arctan, etc.) efficiently in “medium precision” (up to about 1000 digits) by reducing the argument using linear combinations of pairs of logarithms of primes or Gaussian primes. We generalize this approach to an arbitrary number of primes (which in practice may be 10-20 or more), using an efficient algorithm to solve the associated Diophantine approximation problem. Although theoretically slower than the arithmetic-geometric mean (AGM) by a logarithmic factor, this is now the fastest algorithm in practice to compute elementary functions from about 1000 digits up to millions of digits, giving roughly a factor-two speedup over previous methods. We also discuss the use of optimized Machin-like formulas for simultaneous computation of several logarithms or arctangents of rational numbers, which is required for precomputations.

PAST Generalized integral bases and applications in creative telescoping

speaker
Lixin Du, Johannes Kepler University, Linz (Austria)
date
Friday, 13 January 2023 at 11:00
location
Inria Saclay, bâtiment Turing, salle Sofia Kovalevkaïa + online
abstract
In this talk, we explore the applications of integral bases in symbolic integration via creative telescoping. Trager’s Hermite reduction solves the integration problem for algebraic functions via integral bases, which was extended to Fuchsian D-finite functions. We remove the Fuchsian restriction and present Hermite reduction for general D-finite functions via integral bases. It reduces the pole orders of integrands at finite places. Combining Hermite reduction at finite places and at infinity, we obtain a new reduction-based telescoping algorithm for D-finite functions in two variables. This is the joint work with Shaoshi Chen and Manuel Kauers.

2022

PAST What do we know about the cogrowth sequence?

Jointly organized with the “Groupe de travail Transcendance et combinatoire”.

speaker
Igor Pak Mathematics Department, University of California, Los Angeles (USA)
date
Friday, 9 December 2022 at 14:30
location
Paris, Institut Henri Poincaré, amphithéâtre Darboux + online
abstract
Take a group and a set of generators. Denote by $$a(n)$$ the number of words in the generators with product 1 of length $$n$$ (these are loops in the corresponding Cayley graph). The cogrowth sequence $$\{a(n)\}$$ is the main object of our study. Turns out, it carries remarkably rich information about the group, as one considers arithmetic and asymptotic properties of $$a(n)$$, as well as algebraic properties of the generating function for $$\{a(n)\}$$. In the first half of the talk I will review what is known about the problem from different points of view: combinatorics, group theory and computational complexity. In the second half, I will present our recent work on the subject (joint with David Soukup), where we obtain the first negative result for the cogrowth sequence of nilpotent groups in the most unexpected way. This talk is aimed at the general audience and no background will be assumed.

PAST Special session on holonomy

Jointly organized with the “Groupe de travail Transcendance et combinatoire”.

Guessing with little data

speaker
Christoph Koutschan, RICAM, Linz (Austria)
date
Friday, 25 November 2022 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

Reconstructing a hypothetical recurrence equation from the first terms of an infinite sequence is a well-known technique in experimental mathematics, also referred to as “guessing”. We combine the classical linear-algebra approach to guessing with lattice reduction, which in many instances allows us to find the desired recurrence using fewer input terms. We have successfully applied our method to sequences from the OEIS and have identified several examples, for which it would have been very difficult to obtain the same result with the traditional approach.

This is joint work with Manuel Kauers.

paper
2202.07966
extra
slides

Gerrymandering

speaker
Manuel Kauers, Johannes Kepler University, Linz (Austria)
date
Friday, 25 November 2022 at 14:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

We report on some efforts to compute the next few terms of the so-called gerrymandering sequence A348456 that counts the number of ways to dissect a square grid into two connected regions of the same size.

This is joint work with Christoph Koutschan and George Spahn.

paper
2209.01787
extra
slides

Vector spaces of generalized Euler integrals

speaker
Claudia Fevola, MPI MiS, Leipzig (Germany)
date
Friday, 25 November 2022 at 15:30
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

We study vector spaces associated to a family of generalized Euler integrals. Their dimension is given by the Euler characteristic of a very affine variety. Motivated by Feynman integrals from particle physics, this has been investigated using tools from homological algebra and the theory of D-modules. In this talk, I will present an overview of the main tools needed to study these vector spaces, namely twisted de Rham cohomology and Mellin transform. Finally, I will discuss relations between these approaches.

This is a joint project with Daniele Agostini, Anna-Laura Sattelberger, and Simon Telen.

paper
2208.08967
extra
slides

PAST Sylvester forms and elimination matrices

speaker
Laurent Busé, Inria, université Côte d'Azur (France)
date
Friday, 18 November 2022 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract
Sylvester forms of $$n$$ homogeneous polynomials in $$n$$ variables have been introduced by Jean-Pierre Jouanolou to make explicit a certain duality that unravel the structure of some graded components of elimination ideals. By definition, they are determinants that generalize the classical Jacobian determinant. In this talk, the construction and properties of Sylvester forms will be reviewed, with a particular focus on the construction of a family of “hybrid elimination matrices”, that can be seen as a generalization of the family of hybrid Bézout matrices for univariate polynomials. These matrices are more compact than the usual Macaulay matrices, but they can still be used to solve zero-dimensional polynomial systems by means of linear algebra methods. If time permits, extension of the theory of Sylvester forms to multi-projective spaces (joint work with Marc Chardin and Navid Nemati) and to toric varieties (joint work with Carles Checa) will be discussed.

PAST Walks avoiding a quadrant and the reflection principle

speaker
Michael Wallner, Institute of Discrete Mathematics and Geometry, TU Wien (Austria)
date
Friday, 14 October 2022 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
abstract

We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by Bousquet-Mélou in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function satisfies an algebraicity pheonomeon: it is the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of degree up to 216. We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. This is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.

This is joint work with Mireille Bousquet-Mélou.

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

speaker
Armin Straub, University of South Alabama (USA)
date
Friday, 1 July 2022 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

Apéry's proof of the irrationality of ζ(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.

This session is jointly organized with the “Groupe de travail Transcendance et combinatoire”.

PAST Sparse polynomial interpolation and exact division over ℤ

speaker
Armelle Perret du Cray, LIRMM, University of Montpellier (France)
date
Friday, 10 June 2022 at 11:00
location
Paris, Jussieu + online
abstract

We present a new Monte Carlo randomized algorithm to recover an integer polynomial $$f(x)$$ given a way to evaluate $$f(a) \mod 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.

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

speaker
Florent Bréhard, CNRS, University of Lille (France)
date
Friday, 13 May 2022 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
abstract

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.

PAST Modeling piecewise polynomial functions with polynomial minimizers

speaker
Didier Henrion, LAAS-CNRS, University of Toulouse (France) and Czech Techncal University in Prague (Czech Republic)
date
Friday, 22 April 2022 at 11:00
location
Paris, Jussieu, salle 25-26/105
abstract
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.

PAST P-adic algorithm to find a basis of pivariate primary components

speaker
Catherine St-Pierre, University of Waterloo (France)
date
Friday, 25 February 2022 at 15:00
location
online only (zoom)
abstract
Inspired by the characterization of a Gröbner cell from Conca and Valla (2007), we will present a quadratically convergent $$p$$-adic algorithm that we developed to find a basis of the primary component of zero dimensional ideal $$I \subset K[x,y]$$, where $$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 coefficients in a basis.

PAST On finite convergence and convergence rates in polynomial optimization

speaker
Lorenzo Baldi, Inria (France)
date
Friday, 18 February 2022 at 11:00
location
online only (zoom)
abstract

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 regulaty 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.

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

speaker
Guillaume Moroz, Inria (France)
date
Friday, 21 January 2022 at 11:00
location
online only (zoom)
extra
slides + paper
abstract
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.

2021

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

speaker
Bastien Pacifico, I2M, Aix-Marseille Université (France)
date
Friday, 10 December 2021 at 10:30
location
Paris, Jussieu, salle 25-26/105
abstract
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.

PAST Fast list decoding of algebraic geometry codes

speaker
Grigory Solomatov, Danmarks Tekniske Universitet
date
Monday, 22 November 2021 at 14:00
location
Paris, Jussieu, salle 24-25/509
abstract

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.

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

speaker
George Labahn, Cheriton School of Computer Science, University of Waterloo (Canada)
date
Friday, 19 November 2021 at 11:00
location
Paris, Jussieu, salle 25-26/105
extra
slides
abstract

The Smith normal form of an $$n \times n$$ matrix $$A$$ of integers or polynomials is a diagonal matrix $$S = 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

PAST C2-finite sequences

speaker
Antonio Jiménez-Pastor, École polytechnique, LIX (France)
date
Friday, 15 October 2021 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain
extra
slides
abstract
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 $$C^2$$-finite sequences form a difference ring and provide methods to compute in this ring.

PAST Truncated Moment Cone and Connections to the Coalescence Manifold

speaker
Georgy Scholten, Sorbonne Université, LIP6 (France)
date
Friday, 24 September 2021 at 11:00
location
Paris, Jussieu, salle 25-26/105
extra
slides
abstract
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.

PAST Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems

speaker
Bruno Salvy, Inria, LIP, ENS Lyon (France)
date
Friday, 18 June 2021 at 11:00
extra
slides + paper
abstract

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.

PAST Accelerating the moment-SOS hierarchy for volume approximation

speaker
Didier Henrion, CNRS, LAAS (Toulouse, France), Czech technical university in Prague
date
Friday, 21 May 2021 at 11:00
extra
slides + paper
abstract

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.

PAST Picard-Fuchs equations for Feynman integrals

speaker
Pierre Vanhove, CEA (France), HSE University (Moscow, Russia)
date
Friday, 7 May 2021 at 11:00
extra
slides
abstract

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.

PAST A refined laser method and faster matrix multiplication

speaker
Virginia Vassilevska Williams, MIT (USA)
date
Friday, 9 April 2021 at 16:00
extra
slides
abstract

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^{\omega+\epsilon})$$ field operations for all $$\epsilon \gt0$$; the best bound until now is $$\omega\lt 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 \lt 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.)

PAST Separating variables in bivariate polynomial ideals

speaker
Manfred Buchacher, Johannes Kepler Universität, Linz (Austria)
date
Friday, 2 April 2021 at 11:00
extra
slides
abstract
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.

PAST Linear PDE with constant coefficients

speaker
Bernd Sturmfels, UC Berkerley (USA), MPI Leipzig (Germany)
date
Friday, 12 March 2021 at 15:00
extra
slides
abstract
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.

PAST Symmetric situations in polynomial optimization,

speaker
Philippe Moustrou, University of Tromsø (Norway)
date
Friday, 26 February 2021 at 11:00
extra
slides
abstract

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.

PAST Simultaneous rational function reconstruction and applications to algebraic coding theory

date
Friday, 19 February 2021 at 11:00
speaker
Ilaria Zappatore, INRIA Saclay (France)
extra
slides
abstract

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 resilients 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.

PAST Gröbner bases in Tate algebras

speaker
Thibaut Verron, Johannes Kepler Universität, (Linz, Austria)
date
Friday, 12 February 2021 at 11:00
extra
slides
abstract

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.

PAST Structured algorithms for algebraic curves

speaker
Simon Abelard, École polytechnique, LIX (Palaiseau, France)
date
Thursday, 4 February 2021 at 14:00
extra
slides
abstract

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 Pierrick Gaudry and Pierre-Jean Spaenlehauer, the second part is joint work with Alain Couvreur and Grégoire Lecerf.

PAST Complex roots clustering

speaker
Rémi Imbach, Courant Institute, New York University (USA)
date
Friday, 22 January 2021
abstract
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.

2020 and before

Until 2020, Specfun, ancestor of MATHEXP, held the seminar “Computations and proofs”.

Organizers

current
Jérémy Berthomieu
Pierre Lairez