Accéder directement au contenu Accéder directement à la navigation

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

Abstract : Suppose $\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 introduce a technique called \emph{reshaping} which allows us to design quasi-linear algorithms for both: computing the evaluations of an input polynomial $f \in \mathbb{K}[x,y]$ at all points of $\mathcal{P}$; and computing an interpolant $f \in \mathbb{K}[x,y]$ which takes prescribed values on $\mathcal{P}$ and satisfies an input $y$-degree bound. Our genericity assumption is explicit and we prove that it holds for most point sets over a large enough field. If $\mathcal{P}$ violates the assumption, our algorithms still work and the performance degrades smoothly according to a distance from being generic. To show that the reshaping technique may have an impact on other related problems, we apply it to modular composition: suppose generic polynomials $M \in \mathbb{K}[x]$ and $A \in \mathbb{K}[x]$ are available for precomputation, then given an input $f \in \mathbb{K}[x,y]$ we show how to compute $f(x, A(x)) \operatorname{rem} M(x)$ in quasi-linear time.
Keywords :
Type de document :
Pré-publication, Document de travail
Domaine :

Littérature citée [36 références]

https://hal-unilim.archives-ouvertes.fr/hal-02521821
Contributeur : Vincent Neiger <>
Soumis le : jeudi 4 juin 2020 - 12:13:21
Dernière modification le : vendredi 10 septembre 2021 - 11:09:08

### Fichier

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

### Citation

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

### Métriques

Consultations de la notice

## 127

Téléchargements de fichiers