Simultaneous Rational Function Reconstruction with errors: Handling multiplicities and poles. (May 2023)

• Record Type: Journal Article
• Authors: Guerrini, Eleonora; Lairedj, Kamel; Lebreton, Romain; Zappatore, Ilaria
• Is Part Of: Journal of symbolic computation. Volume 116(2023)
• Page Start: 345
• Page End: 364
• Publication Date: 2023-05
• Subjects: Simultaneous rational function reconstruction -- Interleaved Reed-Solomon codes -- Cauchy interpolation with poles -- Hermite interpolation -- Multiplicity codes; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.10.007
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper, we focus on extensions of methods for interpolating rational functions from their evaluations, in the context of erroneous evaluations. This problem can be seen both from a computer algebra and a coding theory point of view. In computer algebra, this is a generalization of Simultaneous Rational Function Reconstruction with errors and multiprecision evaluations. From an error correcting codes point of view, this problem is related to the decoding of some algebraic codes such as Reed-Solomon, Derivatives or Multiplicity codes. We give conditions on the inputs of the problem which guarantee the uniqueness of the interpolant. Since we deal with rational functions, some evaluation points may be poles: a first contribution of this work is to correct any error in a scenario with poles and multiplicities that extends (Kaltofen et al., 2020 ). Our second contribution is to adapt rational function reconstruction for random errors, and provide better conditions for uniqueness using interleaving techniques as in (Guerrini et al., 2021 ).