快速多点求值

Horner 法在一个点上只用 $O(n)$ 次运算，但对 $n$ 个无结构点独立执行会达到 $O(n^2)$。快速多点求值不试图让单个点更便宜，而是先把点分组：一个次数约 $n/2$ 的余式同时保留左半全部点的信息，原多项式中能被该半点集乘积整除的部分对这些点都没有影响。随后每次二分只保留下一层真正需要的余式。

这与数值采样的直觉不同。算法没有近似 $f$，也没有在点之间插值；每次取余都是精确同余变换。共享来自“多个求值同态的核包含一个共同乘积”，而不是点彼此靠近。点集可以完全不规则，因此它补足了 FFT 只擅长单位根或其他特殊结构点集的空缺。

取

左半模数为 $M_L=x(x-1)=x^2-x$。在该商中 $x^2\equiv x$、$x^3\equiv x$，所以

再模 $x$ 与 $x-1$ 得 $5,4$。右半模数 $M_R=(x-2)(x-3)=x^2-5x+6$；由 $x^2\equiv 5x-6$ 可得 $x^3\equiv 19x-30$，因此

在 $2,3$ 处分别为 $9,26$。一次大余式计算由此服务两个点，下一层只处理一次多项式。

点可以重复，算法会正确地重复输出同一个值，但树中相同线性因子使工作没有减少，且不能直接转作普通插值。若 $\mathrm{deg}f$ 远大于点数，应先在根模数下把 $f$ 降次；若点数很少，建树的常数与内存可能超过逐点 Horner。复杂度按环运算计数也不控制整数系数膨胀，模数连乘后的系数可能很大，精确 bit complexity 需要另行估计。

另一个边界是数值稳定性。浮点系数上做快速除法和树状传播可能放大舍入误差；$O(M(n)\log n)$ 是精确代数模型的结论，不等价于任意点集上稳定的数值算法。Chebyshev 点、单位根等特殊点集有专门变换，通常同时拥有更好的常数或稳定性分析。

乘积树建好后，可以对多个多项式重复下降，摊薄点集预处理成本。把线性叶子换成一般首一模数，就得到 simultaneous modular reduction：一次把 $f$ 化到多个商环中。这个接口又是快速 Chinese remainder 重构、快速 rational evaluation 和若干符号线性代数算法的组成部分。

乘积树快速插值公理库乘积树快速多项式插值Product-tree polynomial interpolation · Fast interpolation by product tree以根积导数权重和自底向上线性组合，在一般互异点集上快速恢复插值多项式。使用同一批结点，但方向相反：先借一次多点求值得到根积导数在各点的值，再从叶子权重向上合并。两种算法共享数据结构，却不是把求值代码简单倒序；插值多出除以 $M^{\prime }(u_i)$ 的步骤，因此要求点差可逆，并有重复点与非域系数的额外边界。