https://hal-unilim.archives-ouvertes.fr/hal-02521821v1Neiger, VincentVincentNeigerXLIM-MATHIS - Mathématiques & Sécurité de l'information - XLIM - XLIM - UNILIM - Université de Limoges - CNRS - Centre National de la Recherche ScientifiqueRosenkilde, JohanJohanRosenkildeDTU Compute - Department of Applied Mathematics and Computer Science [Lyngby] - DTU - Danmarks Tekniske Universitet = Technical University of DenmarkSolomatov, GrigoryGrigorySolomatovDTU Compute - Department of Applied Mathematics and Computer Science [Lyngby] - DTU - Danmarks Tekniske Universitet = Technical University of DenmarkGeneric bivariate multi-point evaluation, interpolation and modular composition with precomputationHAL CCSD2020Multi-point evaluationinterpolationmodular compositionbivariate polynomials[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Neiger, Vincent2020-03-27 16:10:442023-03-24 14:53:152020-03-30 10:19:40enPreprints, Working Papers, ...https://hal-unilim.archives-ouvertes.fr/hal-02521821v1application/pdf1If $\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$.