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

Vincent Neiger
• Fonction : Auteur
• PersonId : 932985
Grigory Solomatov
• Fonction : Auteur
• PersonId : 1027644

#### Résumé

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.

#### 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 2
• DOI :

### Citer

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

### Exporter

BibTeX TEI Dublin Core DC Terms EndNote Datacite

### Collections

117 Consultations
171 Téléchargements