快速多点求值 | Codeboy's Blog

形式陈述

给定 $n\ge1$ ，输入交换含幺环 $R$ 上次数小于 $n$ 的多项式 $f$ 与点 $u_0,\ldots,u_{n-1}\in R$ ，输出

\bigl(f(u_0),\ldots,f(u_{n-1})\bigr).

先为线性模数 $x-u_i$ 建立子乘积树。在根处令余式 $r_{h,0}=f\bmod M_{h,0}$ ；对每个内部结点递推

r_{i-1,2j}=r_{i,j}\bmod M_{i-1,2j},\qquad r_{i-1,2j+1}=r_{i,j}\bmod M_{i-1,2j+1}.

到叶子时 $r_{0,j}$ 是常数。因为 $f-r_{0,j}$ 可被 $x-u_j$ 整除，余数定理给出 $r_{0,j}=f(u_j)$ 。若 $n$ 不是二次幂，可以用不完全树或补单位叶子平衡规模；只返回原来的 $n$ 个求值叶子，补入的单位叶子不产生输出。

设乘法代价为 $M(n)$ ，并可在 $O(M(n))$ 环运算内完成首一多项式的除余。每一层的被除式与模数总次数为 $O(n)$ ，故下降连同输出的成本为 $O(M(n)\log(n+1))$ ；加上建树仍是同一量级。这个计数适用于任意交换环上的首一线性模数，因为长除法只除以 $1$ ；快速成本调用多项式乘法算法及其快速首一除余，并使用该页的 $M$ 假设。基于 Newton 反演时，首一模数的反转常数项正是单位 $1$ ，所以截断逆存在；长度为一时直接返回常数值。

直觉

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

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

例子与边界

取

f=x^3-2x+5,\qquad (u_0,u_1,u_2,u_3)=(0,1,2,3).

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

f\bmod M_L=5-x,

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

f\bmod M_R=17x-25,

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

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

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

推论与应用

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

乘积树快速插值使用同一批结点，但方向相反：先借一次多点求值得到根积导数在各点的值，再从叶子权重向上合并。两种算法共享数据结构，却不是把求值代码简单倒序；插值多出除以 $M'(u_i)$ 的步骤，因此要求点差可逆，并有重复点与非域系数的额外边界。

参考资料

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013, Ch. 10.
Robert T. Moenck and Allan Borodin, “Fast Modular Transforms,” Journal of Computer and System Sciences 8(3), 1974, pp. 366–386.
Alin Bostan and Éric Schost, “Polynomial Evaluation and Interpolation on Special Sets of Points,” Journal of Complexity 21(4), 2005, pp. 420–446.

形式陈述 ​

反向链接

形式陈述