FFT

FFT可以在$O(n\log n)$的时间内在多项式的点值表示法和系数表示法之间相互转换, 从而可以加速多项式乘法.

原理

多项式可以用系数来表示, 也可以用点值表示法表示.

一个$n$次多项式可以由其$n+1$个不同点处的值来确定.

证明: 设这些点为$x_0,x_1,...,x_n$, 对应地设多项式在这些点处的值为$y_0,y_1,...,y_n$. 由这些已知条件, 尝试解出多项式的$i$次项系数$a_i(i=0,1,...,n)$, 即解方程

$$\left(\begin{matrix} 1 & x_0 & x_0^2 & ... & x_0^n \\ 1 & x_1 & x_1^2 & ... & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & ... & x_n^n\\ \end{matrix}\right) \left(\begin{matrix} a_0 \\ a_1 \\ \vdots \\ a \\ \end{matrix}\right) = \left(\begin{matrix} y_0 \\ y_1 \\ \vdots \\ y_n \\ \end{matrix}\right) $$

由于左侧的系数矩阵为范德蒙德矩阵, 其行列式为$\prod_{i<j}(x_j-x_i)$, 又由$x_i\neq x_j(i\neq j)$, 其行列式不为0, 从而方程有唯一解.

之所以要转换, 是因为在点值表达式下有些东西更好算, 如多项式乘积. 暴力转换需要算出左边的矩阵, 并进行$(n\times n)$矩阵与$(n\times 1)$矩阵的乘积, 是$O(n^2)$的.

$$\omega_n=e^{i\theta}=\cos{k\theta}+i\sin{k\theta},\theta=\dfrac{2\pi}{n}$$

$\omega_n$$0,1,...,(n-1)$次幂称为单位根, 是方程$x^n=1$在复数域的全部解. 它们将单位圆$n$等分, 并且其中有一个点$(\omega_n^0)$是1.

由于$2^k$次单位根的性质较好, 先将$n$补全为$2^{\lceil \log n\rceil}$, 再用多项式在$n$次单位根 (及其幂次) 处的值来表示$(n-1)$次多项式, 以求快速的转换.

现在要求

$$\begin{align*} y_0&=a_0\omega_n^{0\cdot0}+a_1\omega_n^{0\cdot1}+a_2\omega_n^{0\cdot2}+...+a_{n-1}\omega_n^{0\cdot(n-1)}\\ y_1&=a_0\omega_n^{1\cdot0}+a_1\omega_n^{1\cdot1}+a_2\omega_n^{1\cdot2}+...+a_{n-1}\omega_n^{1\cdot(n-1)}\\ y_2&=a_0\omega_n^{2\cdot0}+a_1\omega_n^{2\cdot1}+a_2\omega_n^{2\cdot2}+...+a_{n-1}\omega_n^{2\cdot(n-1)}\\ &...\\ y_{n-1}&=a_0\omega_n^{(n-1)\cdot0}+a_1\omega_n^{(n-1)\cdot1}+a_2\omega_n^{(n-1)\cdot2}+...+a_{n-1}\omega_n^{(n-1)\cdot(n-1)}\\ \end{align*} $$

分离奇数项和偶数项, 以$y_1$为例:

$$\begin{align*} y_1&=(a_0+a_2\omega_n^2+a_4\omega_n^4+...+a_{n-2}\omega_n^{n-2})+(a_1\omega_n^1+a_3\omega_n^3+...+a_{n-1}\omega_n^{n-1})\\ &=(a_0+a_2\omega_n^2+a_4\omega_n^4+...+a_{n-2}\omega_n^{n-2})+\omega_n^1(a_1\omega_n^0+a_3\omega_n^2+...+a_{n-1}\omega_n^{n-2})\\ \end{align*} $$

问题变成递归的了: 求$a_0,a_2,...,a_{n-2}/a_1,a_3,...,a_{n-1}$为系数的多项式, 在$n/2$次单位根处的点值表示.

此外, 还有:

$$\begin{align*} y_{n/2+1}&=(a_0\omega_n^{(n/2+1)\cdot 0}+a_2\omega_n^{(n/2+1)\cdot2}+...+a_{n-2}\omega_n^{(n/2+1)\cdot(n-2)})\\&+\omega_n^{n/2+1}(a_1\omega_n^{(n/2+1)\cdot 0}+a_3\omega_n^{(n/2+1)\cdot2}+...+a_{n-1}\omega_n^{(n/2+1)\cdot(n-2)})\\ &=(a_0+a_2\omega_n^2+a_4\omega_n^4+...+a_{n-2}\omega_n^{n-2})-\omega_n^1(a_1+a_3\omega_n^2+...+a_{n-1}\omega_n^{n-1})\\ &=\overline{y_1} \end{align*} $$

同理, $y_{n/2+k}=\overline{y_k}$. 从而, 为了计算$n-1$次多项式在$n$个点处的值$y_0,y_1,...,y_{n-1}$, 只需要计算2个$n/2-1$次多项式在$n/2$个点处的值. 也就是$T(n)=2T(n/2)+n,T(1)=1$, 解得$T(n)=n(\log n+1)$.