浅谈快速傅里叶变换

本人太菜了,不是很懂这个东西,只是有点懂了快速傅里叶变换的一种方法,本文没有代码,只是证明了这种快速傅里叶变换的方法是正确的。
本文大量使用复数,i表示$\sqrt{-1}$。

多项式乘法

快速傅里叶变换用于快速解决多项式乘法的问题。即
设$A(x)=\displaystyle\sum_{j=0}^{n-1}a_jx^j$
$B(x)=\displaystyle\sum_{j=0}^{m-1}b_jx^j$
令$C(x)=A(x)\times B(x)$
则C(x)可表示为:
$\displaystyle\sum_{j=0}^{n+m-2}c_jx^j$
我们要解决的问题是已知a数组和b数组,求c数组。
举个例子:有多项式$A(x)=6x^3+7x^2-10x+9,B(x)=-2x^3+4x-5$则$C(x)=-12x^6-14x^5+44x^4-20x^3-75x^2+86x-45$
显然,我们可以得出:
$c_j=\displaystyle\sum_{k=0}^{j}a_kb_{j-k}$
但是按这个式子计算,我们需要耗费$\Theta(nm)$的时间,这个时间复杂度在大数据规模下是无法接受的,因此要寻找一种更快的方法。

系数表达与点值表达

为了便于讨论,我们不妨把a和b数组的大小都设为n,且令n为2的幂次。我们称上面那种使用数组记录系数的方式为系数表达。光看这个系数表达,我们无法得出一个更快的方法来计算。但是,一个多项式还有另外一种表达方式:点值表达。我们可以把一个多项式的函数图像上的一些点给记录下来,如果一个n次的多项式只需要记录n个点的坐标就可以唯一表示一个多项式了(唯一性可以用解n元一次方程来证明,具体证明略)。
我们可以通过系数表达和点值表达的相互转换来快速实现多项式乘法。基本有三个步骤:
1.求值。将AB两个多项式的系数表达转换为点值表达。
2.点值乘法。用AB两个多项式的点值表达得到C的点值表达。
3.插值。将C的点值表达转换为系数表达。
乍一看,我们可以选取相同的x值来分别得到AB点值表达的y坐标,第二步可以将y坐标依次乘起来得到C的y坐标,然后求解。这样的话步骤2可以用$\Theta(n)$的时间复杂度实现,但是在一般情况下,步骤1和步骤3还是需要$\Theta(n^2)$的时间代价。但是,这些求值点是可以由我们自己选择的,快速傅里叶变换通过精妙地选取特殊求值点来快速实现步骤1,然后可以使用逆快速傅里叶变换来实现步骤3。

特殊求值点

我们需要使用欧拉公式$e^{iu}=cos(u)+isin(u)$,我们先来证明下这个公式:
设$x=cos(u)+isin(u)$
则$dx=[-sin(u)+icos(u)]du=ixdu$
则$\int x^{-1}dx=\int idu$
所以$x=e^{iu}$
证毕。
设$\omega_n=e^{2\pi i/n}$
我们令求值点依次为$\omega_n^{0},\omega_n^{1},…,\omega_n^{n-1}$
可以发现一个简单的性质:
对于所有$n\ge 0,k\ge 0,d>0$有$\omega_{dn}^{dk}=\omega_{n}^{k}$

使用快速傅里叶变换(FFT)进行求值

我们定义一个问题Q(n,a[])表示系数分别为a数组中的元素,依次求以$\omega_n^{0},\omega_n^{1},…,\omega_n^{n-1}$的求值点y坐标。
我们可以考虑分治算法来完成这一操作。对于每一个问题:
如果n=1,这个问题的结果就是$a_{0}$
否则,我们可以先求解Q(n/2,$a_0,a_2,a_4,…,a_{n-2}$)和Q(n/2,$a_1,a_3,a_5,…,a_{n-1}$)。
接下来考虑如何合并结果:
不妨设要求的结果分别为数组为y,已得到的两个子问题结果分别为$y^{[0]}$和$y^{[1]}$。
由引理1得,$\omega_{n/2}^k=(\omega_{n}^{k})^2$
则对于所有$k<n/2$,有$y_k=y_k^{[0]}+\omega_n^k y_k^{[1]}$
当$k\ge n/2$时,我们可以考虑用上面那种形式进行求值,但是子问题的结果规模没有这么大。但是我们可以发现一些性质:
$\omega_{n}^{k+n/2}=e^{2k\pi i/n+\pi i}=-\omega_{n}^{k}$
$\omega_{n/2}^{k+n/2}=e^{2k\pi i/(n/2)+2\pi i}=\omega_{n/2}^{k}$
则$y_{k+n/2}=y_k^{[0]}-\omega_n^k y_k^{[1]}$
这样我们就可以求解了。
我们思考一下这样分治的时间复杂度:$T(n)=2T(n/2)+\Theta(n)$
则$T(n)=\Theta(nlgn)$

使用逆快速傅里叶变换(逆FFT)实现插值

根据定义,我们可以把问题转换为矩阵运算。
设中间那个$\omega$矩阵为V。
则$V^{-1}V=I_n$
我们发现,当一个矩阵U中(j,k)位置元素为$\omega_n^{-kj}/n$时
$[VU]_{jj’}=\displaystyle\sum_{k=0}^{n-1} \omega_n^{k(j’-j)}/n$
易得,当j’=j时上式值为1,否则上式
$=\omega_n^{j’-j}/n \displaystyle\sum_{k=0}^{n-1}\omega_n^k $
$=\omega_n^{j’-j}/n (\omega_n^n -1)/(\omega_n -1) $
$=0 $
因此$U=V_{-1}$
则$a_j=(1/n)\displaystyle\sum_{k=0}^{n-1} y_k\omega_n^{-kj} $
然后我们发现这个式子和求值时要求的式子非常类似,我们可以再做一遍FFT实现操作。

小结

本人太菜了,不会非递归版的,而且本文可能有错误,请dalao帮忙修改。

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注