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)$