Fast computation of minimal interpolation bases in Popov form for arbitrary shifts

Abstract : We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Pad\'e approximation and constrained multivariate interpolation, and has applications in coding theory and security. This problem asks to find univariate polynomial relations between $m$ vectors of size $\sigma$; these relations should have small degree with respect to an input degree shift. For an arbitrary shift, we propose an algorithm for the computation of an interpolation basis in shifted Popov normal form with a cost of $\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ field operations, where $\omega$ is the exponent of matrix multiplication and the notation $\mathcal{O}\tilde{~}(\cdot)$ indicates that logarithmic terms are omitted. Earlier works, in the case of Hermite-Pad\'e approximation and in the general interpolation case, compute non-normalized bases. Since for arbitrary shifts such bases may have size $\Theta(m^2 \sigma)$, the cost bound $\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ was feasible only with restrictive assumptions on the shift that ensure small output sizes. The question of handling arbitrary shifts with the same complexity bound was left open. To obtain the target cost for any shift, we strengthen the properties of the output bases, and of those obtained during the course of the algorithm: all the bases are computed in shifted Popov form, whose size is always $\mathcal{O}(m \sigma)$. Then, we design a divide-and-conquer scheme. We recursively reduce the initial interpolation problem to sub-problems with more convenient shifts by first computing information on the degrees of the intermediate bases.
Type de document :
Communication dans un congrès
41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930928〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01265983
Contributeur : Vincent Neiger <>
Soumis le : vendredi 13 mai 2016 - 09:43:22
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : mercredi 16 novembre 2016 - 03:36:11

Fichier

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

Identifiants

Collections

Citation

Claude-Pierre Jeannerod, Vincent Neiger, Eric Schost, Gilles Villard. Fast computation of minimal interpolation bases in Popov form for arbitrary shifts. 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930928〉. 〈hal-01265983v2〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

110