快速傅里叶变换
傅里叶分析是一个很美妙的理论，而且它还很实用。在频域分析波形可以很好的将信号分离开来，相反的过程又能回到时域中。处于物理和数学的缘故，指定实用指数函数，我们感觉最主要的原因就是：如果我们对eikx求导、积分或将x变成x+h，结果依然是eikx的倍数，指数函数非常适用于微分方程，积分方程和差分方程，每个频域分量有自己的运作方式，就像特征值一样，然后阿门重新组合得到问题的解。信号的分析和合成(从y中计算c，从c中计算y)是科学计算的中心问题。
我们想要展示Fc,F−1y计算非常快，关键点就是F4到F2的关系：
F4=⎡⎣⎢⎢⎢⎢11111ii2i31i2i4i81i3i6i9⎤⎦⎥⎥⎥⎥接近F∗2=⎡⎣⎢⎢⎢111−1111−1⎤⎦⎥⎥⎥
F4包含w4=i，1的四次根，F∗2包含w2=−1，1的平方根。注意F∗2有一半的元素都是零，做两次2×2的变换仅需要直接进行4×4变换时间的一半，如果64×64变化可以用两个32×32变换替换，那么运行时间将减少一般。之所有能够如此，原因在于w64 和w32之间存在一个简单的联系：
(w64)2=w32,或者(e2πi/64)2=e2πi/32
从圆上的点看，32次根是64次根的两倍，如果w64=1，那么(w2)32=1，如果m是n的一半，那么m次根是n 次根的平方：
如果m=12n,那么w2n=wm(1)
FFT的速度取决于像210=1024这样的合数。如果没有快速变换，那么F 乘以c就需要(1024)2次乘法，相比之下，快速变换只需要5⋅1024 步，整整快了200倍。一般来讲，当n=2ℓ时，我们用12nℓ代替n2，我们先将Fn和两个Fn/2联系起来，然后在和四个Fn/4 联系起来，如此不断进行下去最后可以得出很小的F，通常来讲n2步会减到12nlogn2。
我们现在看看y=Fnc(一个有n个元素的向量)如何从两个只有一半长度的向量中恢复回来。第一步是将c分成奇数和偶数两部分：
c′=(c0,c2,…,cn−2)c′′=(c1,c3,…,cn−1)
利用这两个向量，我们变换y′=Fmc′,y′′=Fmc′′，这两个乘法的矩阵Fm比原来要小。现在问题变成如何从y′,y′′ 中恢复y，Cooley和Tukey注意到了如何求解这个问题：
33、向量y=Fnc的前m项和后m项是
yj=y′j+wjny′′j,yj+m=y′j−wjny′′j,j=0,…,m−1j=0,…,m−1(2)
因此第三步就是：将c分成c′,c′′，用Fm将他们变成y′,y′′并且利用(13)进行重构。
这种不断分半的想法可以一直重复进行，例如从F1024到F512再到F256，如果我们从n=2ℓ开始到一直到n=1，那么最终的计数是12nℓ。另一种计算方法是：从n=2ℓ到n=1需要ℓ 步，每一步需要n/2次乘法，相当于是Fn的一个分解：
F1024=[I512I512D512−D512][F512F512][奇偶置换矩阵](3)
所需的代价近似是线性的，傅里叶分析完全可以用FFT进行转换，为了证实方程(13)，我们将yi分成奇数项和偶数项：
yi=∑k=0n−1wjknck等价于∑k=0m−1w2jknc2k+∑k=0m−1w(2k+1)jnc(2k+1)
右边的两个和式分别有m=12n项。因为w2n=wm，所以这两个和式子可以表示为：
yj=∑k=0m−1wjkmc′k+wjn∑k=0m−1wjkmc′′k=y′j+wjny′′j(4)
在方程(13)的第二部分，j+m部分有一个符号的变化：
在和式里面，因为wkmm=1k=1，所以wk(j+1)m依然为wkjm；在外面，因为wmn=e2πim/n=eπi=−1，所以wj+mn=−wjn。
FFT的想法用其他的素数n代替后就得到一个新版本，如果n本身是一个素数，那么将会有一个全新的算法。
例1:从n=4到n=2为
⎡⎣⎢⎢⎢c0c1c2c3⎤⎦⎥⎥⎥→⎡⎣⎢⎢⎢c0c2c1c3⎤⎦⎥⎥⎥→[F2c′F2c′′]→[y]
因为每步都是线性的，所以从一个矩阵开始，这些矩阵的乘积也必须是F4：
⎡⎣⎢⎢⎢⎢11111ii2i31i2i4i61i3i6i9⎤⎦⎥⎥⎥⎥=⎡⎣⎢⎢⎢11111−1i−i⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢111−1111−1⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢1111⎤⎦⎥⎥⎥(5)
我们可以看出中间的是两个F2，右边是将c分成c′,c′′的置换矩阵，左边是用乘以wjn的矩阵。如果我们从F8开始，那么中间的矩阵就是两个F4，所以FFT相当于傅里叶矩阵的因式分解！n2个非零向量矩阵F近似为ℓ=logn2个矩阵(他们有nℓ个非零元素)相乘的结果。
FFT
FFT的第一步是将Fn的乘法变成两个Fm的乘法，偶数项(c0,c2)从奇数项(c1,c3)中分离出来，如1给出了n=4时的流图(flow graph)。对于n=8，只要用F2代替F4 即可。新元素w4=i是老元素w=w8=e2πi/8 的平方，流图给出了c进入FFT的顺序。
每一步需要12n次乘法，所以最终需要12nlogn。
图2
|
