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
Vincent Neiger
• Fonction : Auteur
Grigory Solomatov
• Fonction : Auteur
• PersonId : 1027644

#### 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$.

#### Domaines

Informatique [cs] Calcul formel [cs.SC]

### 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⟩

### Exporter

BibTeX TEI Dublin Core DC Terms EndNote Datacite
111 Consultations
166 Téléchargements