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:To receive further anouncements, register for the mailing list here:
Faster computation of elementary functions
Fredrik
Johansson
LFANT, Institut de Mathématiques de Bordeaux,
Centre Inria de l'Université de Bordeaux
The moment problem and convex hulls of semialgebraic sets
Simone
Naldi
Computer Algebra team, XLIM, Université de Limoges
27th Jan. 2023
11:00
Inria Saclay, amphithéâtre Sophie-Germain & online
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.
LFANT, Institut de Mathématiques de Bordeaux, Centre Inria de Bordeaux
17th Feb. 2023
11:00
LIP6 25-26/105 & online
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 (aka 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.
Computer Algebra team, XLIM, Université de Limoges
13th Jan. 2023
11:00
Inria Saclay, salle Sofia Kovalevkaïa & online
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.
9th Dec. 2022
14:30
IHP Amphithéâtre Darboux
Co-organized with Groupe de travail « Transcendance et combinatoire »
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.
Mathematics Department, University of California, Los Angeles
25th Nov. 2022
11:00
LIP6 25-26/105 & online
Co-organized with Groupe de travail « Transcendance et combinatoire »
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.
Johann Radon Institute for Computational and Applied Mathematics
25th Nov. 2022
14:00
LIP6 25-26/105 & online
Co-organized with Groupe de travail « Transcendance et combinatoire »
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, arXiv:2209.01787.
Institut für Algebra, Johannes Kepler Universität Linz
25th Nov. 2022
15:30
LIP6 25-26/105 & online
Co-organized with Groupe de travail « Transcendance et combinatoire »
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. F inally, I will discuss relations between these approaches. This is a joint project with Daniele Agostini, Anna-Laura Sattelberger, and Simon Telen.
Max-Planck-Institut für Mathematik in den Naturwissenschaften
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.
Team Aromath, Centre Inria d'Université Côte d'Azur
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.
Institute of Discrete Mathematics and Geometry, TU Wien
1st July 2022
11:00
LIP6 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.
Department of Mathematics and Statistics, University of South Alabama
10 June 2022
11:00
LIP6 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.
Team ECO, LIRMM
Université de Montpellier
13 May 2022
11:00
Inria Saclay, amphithéâtre 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.
Centre de Recherche en Informatique, Signal et Automatique de Lille
22 April 2022
11:00
LIP6 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.
LAAS-CNRS Univ. Toulouse and Czech Tech. Univ. Prague
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.
University of Waterloo.
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.
Team AROMATH, Inria Sophia Antipolis-Méditerranée.
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.
Team Gamble, Inria Nancy – Grand Est.
10 December 2021
10:30
LIP6 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.
I2M, Aix Marseille Université.
22 November 2021
14:00
LIP6 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.
Department of Applied Mathematics and Computer Science Mathematics, Danmarks Tekniske Universitet.
19 November 2021
11:00
LIP6 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
Cheriton School of Computer Science, University of Waterloo.
15 October 2021
11:00
Inria Saclay, amphithéâtre 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.
LIX, École polytechnique.
24 September 2021
11:00
LIP6 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.
PolSys, LIP6, Sorbonne Université.