多项式乘法与快速傅里叶变换

两个 $n$ 项多项式按定义相乘需要 $O(n^2)$ 次系数乘加。FFT 的核心不是“神奇地加速卷积”，而是把多项式换到一个乘法特别容易的表示里。

1. 系数表示与卷积

设

A(x)=\sum_{i=0}^{n-1}a_ix^i, \qquad B(x)=\sum_{j=0}^{n-1}b_jx^j.

乘积 $C(x)=A(x)B(x)$ 的系数为

c_k=\sum_{i+j=k}a_ib_j.

这就是离散卷积。直接计算每个 $(i,j)$ 组合需要 $\Theta(n^2)$ 。

2. 点值表示

次数小于 $d$ 的多项式由任意 $d$ 个互异点上的函数值唯一确定。因此可以：

在足够多的点上求 $A$ 和 $B$ 的值；
逐点相乘 $C(x_k)=A(x_k)B(x_k)$ ；
由点值插值恢复 $C$ 的系数。

逐点相乘只需 $O(n)$ 。真正的难点是如何快速完成“系数 $\leftrightarrow$ 点值”的转换。

3. 为什么选单位根

取 $n$ 次复单位根

\omega_n=e^{2\pi i/n}.

它们具有：

\omega_n^n=1, \qquad \omega_n^{k+n}=\omega_n^k, \qquad \omega_n^{2k}=\omega_{n/2}^k.

最后一个性质让偶数次幂和奇数次幂都能变成规模减半的问题。

4. DFT

离散傅里叶变换把系数向量 $a_0,\ldots,a_{n-1}$ 变为单位根上的点值：

y_k=A(\omega_n^k) =\sum_{j=0}^{n-1}a_j\omega_n^{jk}, \qquad k=0,\ldots,n-1.

直接计算仍是 $O(n^2)$ 。FFT 是计算 DFT 的分治算法。

5. 偶奇拆分

把多项式写成

A(x)=A_{even}(x^2)+xA_{odd}(x^2),

其中

A_{even}(x)=a_0+a_2x+a_4x^2+\cdots,

A_{odd}(x)=a_1+a_3x+a_5x^2+\cdots.

在 $x=\omega_n^k$ 处：

A(\omega_n^k) =A_{even}(\omega_{n/2}^k) +\omega_n^kA_{odd}(\omega_{n/2}^k).

而对另一半点 $k+n/2$ ：

A(\omega_n^{k+n/2}) =A_{even}(\omega_{n/2}^k) -\omega_n^kA_{odd}(\omega_{n/2}^k).

一次得到一对输出，递推式为

T(n)=2T(n/2)+O(n)=O(n\log n).

6. 逆变换

逆 DFT 与 DFT 形式几乎相同，只需把单位根换成共轭并除以 $n$ ：

a_j=\frac1n\sum_{k=0}^{n-1}y_k\omega_n^{-jk}.

因此插值也能用一次 FFT 在 $O(n\log n)$ 内完成。

7. 多项式乘法流程

若两个多项式次数都小于 $n$ ，乘积次数小于 $2n-1$ ：

把系数补零到不小于 $2n$ 的 2 的幂 $N$ ；
计算 $\operatorname{FFT}(A)$ 和 $\operatorname{FFT}(B)$ ；
对每个频点做 $Y_k=Y^A_kY^B_k$ ；
对 $Y$ 做逆 FFT；
按需要对浮点误差四舍五入。

总复杂度为

O(N\log N).

8. 一个四项例子

对

A(x)=a_0+a_1x+a_2x^2+a_3x^3,

拆成

A_{even}(x)=a_0+a_2x, \qquad A_{odd}(x)=a_1+a_3x.

先在 $\omega_2^0=1$ 和 $\omega_2^1=-1$ 上分别计算两个一次多项式，再通过加减组合得到 $A$ 在 $1,i,-1,-i$ 四个点上的值。

9. 数值误差与 NTT

复数 FFT 使用浮点运算，长卷积或大整数乘法会有舍入误差。若系数在模素数意义下运算，可使用数论变换 NTT：把复单位根换成有限域中的原根，获得精确整数结果。

FFT/NTT 的应用包括多项式乘法、大整数乘法、信号卷积、相关计算和快速匹配。

10. 易错点

补零长度不足会发生循环卷积混叠；
逆变换忘记除以 $n$ ；
单位根正负号约定前后不一致；
误以为逐点乘法的点数等于原多项式次数，而不是乘积所需的系数数；
浮点结果直接转整数而不四舍五入。