Computing minimal interpolation bases

Abstract : We consider the problem of computing univariate polynomial matrices over a field that represent minimal solution bases for a general interpolation problem, some forms of which are the vector M-Pad\'e approximation problem in [Van Barel and Bultheel, Numerical Algorithms 3, 1992] and the rational interpolation problem in [Beckermann and Labahn, SIAM J. Matrix Anal. Appl. 22, 2000]. Particular instances of this problem include the bivariate interpolation steps of Guruswami-Sudan hard-decision and K\"otter-Vardy soft-decision decodings of Reed-Solomon codes, the multivariate interpolation step of list-decoding of folded Reed-Solomon codes, and Hermite-Pad\'e approximation. In the mentioned references, the problem is solved using iterative algorithms based on recurrence relations. Here, we discuss a fast, divide-and-conquer version of this recurrence, taking advantage of fast matrix computations over the scalars and over the polynomials. This new algorithm is deterministic, and for computing shifted minimal bases of relations between $m$ vectors of size $\sigma$ it uses $O~( m^{\omega-1} (\sigma + |s|) )$ field operations, where $\omega$ is the exponent of matrix multiplication, and $|s|$ is the sum of the entries of the input shift $s$, with $\min(s) = 0$. This complexity bound improves in particular on earlier algorithms in the case of bivariate interpolation for soft decoding, while matching fastest existing algorithms for simultaneous Hermite-Pad\'e approximation.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2017, 83, pp.272--314. <10.1016/j.jsc.2016.11.015>
Liste complète des métadonnées


https://hal.inria.fr/hal-01241781
Contributeur : Vincent Neiger <>
Soumis le : lundi 13 juin 2016 - 16:17:35
Dernière modification le : vendredi 30 juin 2017 - 01:14:52

Fichier

MinimalInterpolationBasis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Claude-Pierre Jeannerod, Vincent Neiger, Eric Schost, Gilles Villard. Computing minimal interpolation bases. Journal of Symbolic Computation, Elsevier, 2017, 83, pp.272--314. <10.1016/j.jsc.2016.11.015>. <hal-01241781v2>

Partager

Métriques

Consultations de
la notice

601

Téléchargements du document

88