FFT(Fast Fourier Transform)
离散傅里叶变换（DFT）是来计算多项式在
个特殊点的值。而
快速傅里叶变换（FFT）是一种快速有效率的对DFT的实现。FFT可以被用到加速多项式乘法和两个大整数乘法中。快速傅里叶变换加速多项式乘法，其大致过程是将两个多项式的系数表示通过FFT转化为点值表示（时域到频域），然后计算两个多项式点值表示的乘积得到原多项式卷积的点值表示（即乘积多项式系数的FFT变换结果），再将乘积得到的点值表示通过 逆离散傅里叶变换（IDFT）就得到了乘积多项式的系数表示。
多项式的表示
一个多项式一般有有两种表示方法，系数表示法和点值表示法。系数表示法：
点值表示法：
其中
,当
时。这样一个
次多项式就由在
个不同点处的取值唯一确定了。证明如下，在一个点处我们有：
在
个点处：
当点互不相同时，对于未知数
而言，其系数矩阵为范德蒙矩阵，必可逆，故有唯一解，这唯一确定了多项式系数也即唯一确定了多项式。
快速傅里叶变换
在复数域内考虑方程
，由代数学知识我们知道，它有
个根，分别为
，其中由欧拉公式，
。 下面来看一下关于
的性质。基本性质：
我们挑几个来证明一下，如公式(7):
公式(8)由公式(7)平方即可证明。再来看一个重要的性质：
这是因为：
DFT就是要计算
在上述
个根处的取值。如果是朴素的DFT，时间复杂度是
，即Horner's method：
但是现在是一些特殊的点（
的
个单位根），由特殊点的性质我们可以去掉很多冗余计算，将时间复杂度降低到
，这就是FFT。其思想如下，单位根处的点值表示法：
现在考察
，将奇数项与偶数项分开：
令
则可得
于是
可以看到计算
和
各自只需要
规模的一半计算量即可得到。这就厉害了，采用Divide and Conquer思想，如果我们已经知道
和
分别在
处的值，可以在常数时间求得
的值。所以总的时间复杂度为
，其中
是每次分治求对应单位根花费的时间。
逆离散傅里叶变换
对一个普通的范德蒙矩阵求逆，时间复杂度是
，但是现在我们有一个特殊的范德蒙矩阵：
它的逆为：
即原矩阵每个元素的共轭再除以
，推导性证明略，下面给一个计算性证明，设上述两个矩阵的乘积矩阵为
，则
可见两矩阵的乘积确为单位阵。这样我们就通过在特殊点处的点值表达式反求出了多项式的系数。 现在考虑两个多项式的乘积
其中
由卷积表达式给出
利用FFT和IDFT可以以
的时间复杂度得到
的系数。
C++代码实现
参考资料
卜东波 算法分析与设计