Faster Algorithms for Multivariate Interpolation with Multiplicities and Simultaneous Polynomial Approximations

Muhammad Foizul Islam Chowdhury 1, 2 Claude-Pierre Jeannerod 3, 4, * Vincent Neiger 1, 2, 3, 4, * Eric Schost 5 Gilles Villard 3, 4, *
* Auteur correspondant
4 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
5 Computer Science Department, University of Western Ontario
ORCCA - Ontario Research Center for Computer Algebra, Computer Science Department
Abstract : The interpolation step in the Guruswami-Sudan algorithm is a bivariate interpolation problem with multiplicities commonly solved in the literature using either structured linear algebra or basis reduction of polynomial lattices. This problem has been extended to three or more variables; for this generalization, all fast algorithms proposed so far rely on the lattice approach. In this paper, we reduce this multivariate interpolation problem to a problem of simultaneous polynomial approximations, which we solve using fast structured linear algebra. This improves the best known complexity bounds for the interpolation step of the list-decoding of Reed-Solomon codes, Parvaresh-Vardy codes, and folded Reed-Solomon codes. In particular, for Reed-Solomon list-decoding with re-encoding, our approach has complexity $\mathcal{O}\tilde{~}(\ell^{\omega-1}m^2(n-k))$, where $\ell,m,n,k$ are the list size, the multiplicity, the number of sample points and the dimension of the code, and $\omega$ is the exponent of linear algebra; this accelerates the previously fastest known algorithm by a factor of $\ell / m$.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, pp.2370-2387. 〈10.1109/TIT.2015.2416068〉
Liste complète des métadonnées

Littérature citée [53 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00941435
Contributeur : Vincent Neiger <>
Soumis le : vendredi 13 février 2015 - 17:33:50
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : dimanche 16 avril 2017 - 08:46:51

Fichier

MultivariateInterpolation-Poly...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Muhammad Foizul Islam Chowdhury, Claude-Pierre Jeannerod, Vincent Neiger, Eric Schost, Gilles Villard. Faster Algorithms for Multivariate Interpolation with Multiplicities and Simultaneous Polynomial Approximations. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, pp.2370-2387. 〈10.1109/TIT.2015.2416068〉. 〈hal-00941435v2〉

Partager

Métriques

Consultations de la notice

372

Téléchargements de fichiers

228