Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation

Abstract : If $\mathbb{K}$ is a large enough field and $\mathcal{P} \subset \mathbb{K}^2$ is a fixed, generic set of points, which is available for precomputation, we show how to compute all the evaluations of any dense polynomial $f$ on $\mathcal{P}$ in quasi-linear time. Similarly, in quasi-linear time then given interpolation constraints on $\mathcal{P}$ and a target $y$-degree, we compute an $f$ having those evaluations on $\mathcal{P}$ and at most that $y$-degree. Our genericity assumption is explicit and we prove most point sets over a large enough field satisfy it. If $\mathcal{P}$ violates the assumption our algorithms still work and the performance degrades smoothly according to a distance from being generic. We apply the same technique to modular composition: fix a square-free $G \in \mathbb{K}[x]$ and generic $R \in \mathbb{K}[x]$ both available for precomputation, we then input $f \in \mathbb{K}[x,y]$ and output $f(x, R(x)) ~\mathrm{rem}~ G \in \mathbb{K}[x]$ in quasi-linear time in the size of $f, G, R$.
Liste complète des métadonnées

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

https://hal-unilim.archives-ouvertes.fr/hal-02521821
Contributeur : Vincent Neiger <>
Soumis le : vendredi 27 mars 2020 - 16:10:44
Dernière modification le : mardi 31 mars 2020 - 02:01:17

Fichier

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

Identifiants

  • HAL Id : hal-02521821, version 1

Collections

Citation

Vincent Neiger, Johan Rosenkilde, Grigory Solomatov. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. 2020. ⟨hal-02521821⟩

Partager

Métriques

Consultations de la notice

25

Téléchargements de fichiers

18