Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail Année :

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

(1) , (2) , (2)
1
2

Résumé

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$.
Fichier principal
Vignette du fichier
eval.pdf (744.11 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02521821 , version 1 (27-03-2020)
hal-02521821 , version 2 (04-06-2020)

Identifiants

  • HAL Id : hal-02521821 , version 1

Citer

Vincent Neiger, Johan Rosenkilde, Grigory Solomatov. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. 2020. ⟨hal-02521821v1⟩
111 Consultations
166 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More