May 19 – 20, 2022
XLIM
Europe/Paris timezone

Invited Speakers

Jérémy Berthomieu (Sorbonne Université, Paris)

Title: Guessing linear recurrence relations for polynomial system solving

Abstract: Many problems in computer algebra require to guess linear recurrence relations of a sequence. We can mention sparse linear system solving, modular rational reconstruction or polynomial system solving through Faugère and Mou's Sparse-FGLM algorithm for Gröbner bases change of order. The Berlekamp--Massey algorithm and its faster variants solve this problem in the one-dimensional case. In the multi-dimensional case, several algorithms generalize the Berlekamp--Massey algorithm. The so-called Berlekamp--Massey--Sakata algorithm does so using polynomial additions and shifts by a monomial, the Scalar-FGLM relies on linear algebra operations on a multi-Hankel matrix and the Artinian Gorenstein Border basis algorithm uses a Gram-Schmidt process. In this talk, we present algorithms for guessing recurrences based solely on multivariate polynomial divisions, allowing us to revisit both the Berlekamp--Massey--Sakata and the Scalar-FGLM algorithms. We also present variants that can take advantage of the structure of the sequence to guess the relations more efficiently. Finally, we present a variant of the Sparse-FGLM algorithm for computing the Gröbner basis of a colon ideal. 

This is based on joint works with Christian Eder (Technische Universität Kaiserslautern), Jean-Charles Faugère (CryptoNext Security et INRIA) et Mohab Safey El Din (Sorbonne Université)

 

Paola Boito (Università di Pisa)

Title: Approximation of the reciprocal of a phi-function applied to rank structured matrices

Abstract: In recent years, methods for the numerical computation of matrix functions have been the object of considerable interest. Matrix functions have a wide range of applications, including the solution of certain classes of differential problems. Here we focus on rational approximation of the reciprocal of a phi-function, which is involved for instance in the formulation of exponential integrators. After a quick review of rank structure and of its interplay with matrix functions, we present a recently proposed family of mixed polynomial-rational approximations that is especially well suited for use on rank-structured matrices, such as quasiseparable or Toeplitz-like. The approximate structure retained by the output can be characterized explicitly and is consistent with state-of-the-art decay bounds.  Numerical experiments showcase the favorable behavior of these approximations; in particular, a nonlocal differential problem is selected as a model example.

 

Eleonora Guerrini (Université Montpellier)

Title: Rational reconstruction from faulty evaluations via algebraic decoding

Abstract: Evaluation Interpolation algorithms are a key tool for the algebraic decoding of a large class of codes, including the famous Reed Solomon codes. Recent techniques allow to use this type of decoding in the more general setting of fault tolerant algorithms, where one has to interpolate erroneous data (potentially computed  by an untrusted entity).  In this talk we will present algorithms to reconstruct  a rational function (or vector) from faulty evaluations, focusing on  the number of errors and how one can handle them beyond the classical worst case unique decoding radius.

 

Raf Vandebril (KU Leuven)

Title: Updating and downdating of orthogonal rational functions

Abstract: In this talk we show that the discrete inner product and the corresponding orthogonal rational functions with certain poles can be efficiently and accurately computed by updating and downdating the recurrence relations for these functions by solving corresponding inverse eigenvalue problems.