On the uniqueness of Simultaneous Rational Function Reconstruction: handling poles and multiplicities


Séminaire AMAC: CASC

27/01/2022 - 11:00 Ilaria Zappatore (Inria) À distance : https://meet-ljk.imag.fr/b/pie-a8o-t2f-ckl

In this talk I focus on an evaluation-interpolation technique for reconstructing a vector of rational functions (with the same denominator), in presence of erroneous evaluations. This problem is also called Simultaneous Rational Function Reconstruction with errors (SRFRwE) and it has significant applications in computer algebra (e.g.for the parallel resolution of polynomial linear systems) and in algebraic coding theory (e.g. for the decoding of the interleaved version of the Reed-Solomon codes). Indeed, an accurate analysis of this problem leads to interesting results in both these scientific domains.
Starting from the SRFRwE, we then introduce its multi-precision generalization, in which we include evaluations with certain precisions.
Our goal is to reconstruct a vector of rational functions, given, among other information, a certain number of evaluation points. Thus, these evaluation points may be poles of the vector that we want to recover. Our multi-precision generalization also allows us to handle poles with their respective orders.
The main goal of this work is to determine a condition on the instance of this SRFRwE problem (and its generalized version) which guarantee the uniqueness of the interpolating vector. This condition is crucial for the applications: in computer algebra it affects the complexity of the corresponding SRFRwE resolution algorithm, while in coding theory, it affects the number of errors that can be corrected.
We determine a condition which allows us to correct any errors.  Then we exploit and revisit results related to the decoding of interleaved Reed-Solomon codes in order to introduce a better condition for correcting random errors.
This talk includes joint works with E. Guerrini, K. Lairedj and R. Lebreton.