论文标题
通用双变量多点评估，插值和模块化成分
Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
论文作者
论文摘要
假设$ \ mathbb {k} $是一个足够大的字段，$ \ mathcal {p} \ subset \ mathbb {k}^2 $是一个固定的，通用的点集，可用于预先计算。我们介绍了一种称为\ emph {重塑}的技术，该技术使我们能够为这两者都设计准线性算法：计算输入多项式$ f \ in \ mathbb {k} [k} [x，y] $在$ \ nathcal {p} $的所有点上的评估；并计算\ Mathbb {k} [x，y] $中的interpolant $ f \ in，该$在$ \ mathcal {p} $上采用规定的值并满足输入$ y $ -Degegrey bund。我们的通用假设是明确的，我们证明它在足够大的字段上的大多数点设置都具有。如果$ \ MATHCAL {P} $违反了假设，那么我们的算法仍然可以正常工作，并且根据通用距离的距离，性能会顺利降解。为了证明该重塑技术可能会对其他相关问题产生影响，我们将其应用于模块化组成：假设通用多项式$ m \ in \ Mathbb {k} [x] $和$ a \ in \ mathbb {k} [k} [x] $ f（x，a（x））\ operatatorName {rem} m（x）$ in quasi-linear时间。
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.
