The joint MATHEXP-Polsys seminar

speaker

Arthemy Kiselev

date

< Friday, 26 April 2024 at 11:00 >

location

Inria Saclay, bâtiment Turing, salle Grace Hoppen + online

abstract

Suppose that some natural combinatorial structures – such as directed graphs – encode elements of some natural vector spaces – e.g., of differential polynomials on \(\mathbb{R}^d\), – yet it can be that two topologically non-isomorphic graphs encode the same formula. Will then all bases of linearly independent graphs be equal, or will some graph tuples be more equal than others?

We encounter this effect in the (non)triviality problem for infinitesimal deformations of Poisson brackets on \(\mathbb{R}^d\) by using Kontsevich's graph calculus (and its adaptation to the class of Nambu-determinant Poisson structures; both the standard calculus of graphs and its refined micro-graph version are implemented in software {gcaops} by R.Buring). For a chosen datum about the deformation, the problem under study gives us a sequence of overdetermined inhomogeneous linear algebraic systems (upon the undetermined coefficients of micro-graphs) over the spaces \(\mathbb{R}^d\), \(d\geqslant 2\), equipped with the Nambu–Poisson brackets. We detect that the linear systems are solvable if \(d=2,3,4\) and that the shifts along the respective affine spaces of solutions are purely Hamiltonian, hence not essential, at each \(d=2,3,4\). Yet we explore also whether (and why not always) solutions from lower dimension do or do not extend to solutions in higher dimension, depending on our choice of the micro-graphs, i.e. of the basis to encode the formula of solution in lower dimension.

The problem – whether there is a solution to the linear system that one would obtain over \(\mathbb{R}^d\) for \(d\gg 2\) – is open; we analyse obstructions in the bottom-up approach.

Work in progress, joint with R.Buring (INRIA) and M.S. Jagoe Brown and F.M. Schipper (Groningen).

speaker

Florian Fürnsinn, University of Vienna, Vienna (Austria)

date

< Friday, 17 May 2024 at 11:00 >

location

Inria Saclay, bâtiment Turing

abstract

TBA

speaker

Anna-Laura Sattelberger, KTH Royal Institute of Technology, Stockholm (Sweden)

date

< Friday, 22 March 2024 at 11:00 >

location

Inria Saclay, bâtiment Turing, salle Grace Hopper + online

abstract

I explain how to compute series solutions of regular holonomic D-ideals with Gröbner basis methods via an algorithm due to Saito, Sturmfels, and Takayama, which is a vast generalization of Frobenius’ method. As a point in case, I consider a D-ideal originating from a triangle Feynman diagram. This talk is based on the joint work arXiv:2303.11105 with Johannes Henn, Elizabeth Pratt, and Simone Zoia. Therein, we compare D-module techniques to dedicated methods developed for solving differential equations in the context of Feynman integrals.

speaker

Vincent Neiger, Sorbonne Université, Paris (France)

date

< Friday, 9 February 2024 at 11:00 >

location

Paris, Jussieu, corridor 26-00, room 428 + online

abstract

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 \pmod g\). 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. We will also report on experimental results using the Polynomial Matrix Library. Contains joint work with Seung Gyu Hyun, Bruno Salvy, Éric Schost, Gilles Villard.

• https://dl.acm.org/doi/10.1145/3638349
• https://arxiv.org/abs/2110.08354

speaker

Nikolai Fadeev, Research Institute for Symbolic Computation, Linz (Austria)

date

< Friday, 26 January 2024 at 11:00 >

location

Inria Saclay, bâtiment Turing, room Grace Hopper

abstract

Nested binomial sums form a particular class of sums that appear in particle physics computations, in particular in quantum electrodynamics or quantum chromodynamics, but also in combinatorics in mathematics. While computing a closed form for those is not always possible, one can in particular try to study their asymptotics at infinity, for example to get analytical continuations. We will present our package RICA which implements and extends a method sketched in « Iterated Binomial Sums and their Associated Iterated Integrals » (J. Ablinger, J.Blümlein, J.C.Raab, C. Schneider) [arXiv:1407.1822] for computing Mellin representations and asymptotic expansions of such sums.

speaker

Emily Barnard, DePaul University, Chicago (USA)

date

< Wednesday, 25 October 2023 at 11:00 >

location

amphitheatre Darboux, Institut Henri Poincaré (Paris)

abstract

The pop-stack sorting method takes an ordered list or permutation and reverses each descending run without changing their relative positions. In this talk we will review recent combinatorial results on the pop-stack sorting method, and we will extend the pop-stack sorting method to certain pattern avoiding permutations. This talk will be accessible to all.

Joint event with RTCA

speaker

Camilo Sanabria Malagón, Universidad de los Andes, Colombia

date

< Friday, 6 October 2023 at 11:00 >

location

amphitheatre Darboux, Institut Henri Poincaré (Paris)

abstract

Let G⊆SL2(ℂ) be a finite primitive group. A classical result of Klein states that there exists a hypergeometric equation such that any second order linear ordinary differential equation whose differential Galois group is G is projectively equivalent to the pullback by a rational map of this hypergeometric equation. In this talk I present a generalization of this result. Let G⊆SLn(ℂ) be a finite primitive group. I will show that there is a positive integer d=d(G) and a standard equation such that any linear ordinary differential equation whose differential Galois group is G is gauge equivalent over a field extension of degree d to an equation projectively equivalent to the pullback by a map of this standard equations. For n=3, the standard equations can be chosen so that they are hypergeometric. Implementations of Klein's result exist. If time permits, I will show how the properties of the invariants of the primitive subgroups of SL3(ℂ) can be exploited to aim for an efficient implementation of this generalization for n=3.

Joint event with RTCA

speaker

Yann Bugeaud, IRMA, Université de Strasbourg (France)

date

< Friday, 2 June 2023 at 11:00 >

location

salle Pierre Grisvard, Institut Henri Poincaré (Paris)

abstract

Almost nothing is known on the continued fraction expansion of an algebraic real number of degree at least three. The situation is different over the field of power series \({{\mathbb F}}_p((x^{-1}))\), where \(p\) is a prime number. For instance, there are algebraic power series of degree at least three whose sequence of partial quotients have bounded degree. And there are as well algebraic power series of degree at least three which are very well approximable by rational fractions: the analogue of Liouville's theorem is best possible in \({{\mathbb F}}_p((x^{-1}))\). Recently, in a joint work with Han (built on a previous work by Han and Hu), we proved that, for any distinct nonconstant polynomials \(a, b\) in \({{\mathbb F}}_2 [x]\), the power series

\[ [a; b, b, a, b, a, a, b, \ldots ] = a + \frac{1}{b + \frac{1}{b + \cdots}},\] whose sequence of partial quotients is given by the Thue–Morse sequence, is algebraic of degree \(4\) over \({{\mathbb F}}_2 (x)\). We discuss this and related results. Furthermore, we give a complete description of the continued fraction expansion of the algebraic power series \((1 + x^{-1})^{j/d}\) in \({{\mathbb F}}_p((x^{-1}))\), where \(j, d\) are coprime integers with \(d \ge 3\), \(1 \le j < d/2\), and \(\gcd(p, jd) = 1\) (joint work with Han).

speaker

Florent Koechlin, LORIA, Nancy (France)

date

< Friday, 14 April 2023 at 11:00 >

location

Inria Saclay, bâtiment Turing, room Grace Hopper + online

abstract

I will talk about the connection between inherent ambiguity of formal languages and the properties of their generating series. It is a classical result that regular languages have rational generating series and that the generating series of unambiguous context-free languages are algebraic. In the eighties, Philippe Flajolet developed several tools based on this connection to prove efficiently and easily the inherent ambiguity of many context-free languages, some of which resisted the historical methods based on iterations. In this talk I will present how these ideas relying on generating series can be extended to Parikh automata, and how they provide an algorithmic tool to decide the inclusion problem on unambiguous Parikh automata. This is a joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.

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.

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.

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.

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.

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.

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.