离散傅里叶变换（DFT）是信号处理中的重要方法，快速傅里叶变换（FFT）是它的一种快速实现方式。

从矩阵-向量乘法说起

对于大小为N的矩阵AN×N，该矩阵作用在N个元素的向量x上，这个矩阵-向量乘法Ax的复杂度是显而易见的，就是O(N2)。

离散傅里叶变换DFT

对长度为N的向量x做离散傅里叶变换，本质上就是用一个特殊的矩阵（离散傅里叶变换矩阵）DN×N对x作一个矩阵-向量乘法X=Dx，其中离散傅里叶变换矩阵的元素非常规律：Dij=ωij,0≤i,j≤N−1（ω=e−2πi/N是复数方程zN=1的单位根，这里的i是虚数单位，注意不要和行列下标的ij混淆了）

DFT矩阵

快速傅里叶变换算法FFT

由于离散傅里叶变换矩阵非常有规律，因此人们很自然地想到，涉及DFT矩阵的乘法一定有某种巧妙的计算方法可以加速运算。快速傅里叶变换算法（FFT）就是这样一种加速DFT矩阵-向量乘法的算法。

FFT算法的核心：奇偶分离（以八个数为例）

FFT算法的原理非常简单，只需要把矩阵乘法的列进行重新安排，就能看出规律了。以八元离散傅里叶变换为例，其原始形式是这样的：

八元离散傅里叶变换

在矩阵乘法中，把右边向量的行进行变换，对应的列也进行变换，结果不变。因此，我们可以把偶数列（0,2,4,6列，程序员的下标从0开始……）往左边挪，对应的偶数下标的x（0,2,4,6行）往上挪，得到变换后的结果：

奇偶分离的八元离散傅里叶变换

观察上述变换之后的分块矩阵，我们发现，每一列的上下矩阵之间都差一个固定的倍数。这不是偶然，这正是FFT算法的核心。

奇偶分离的形式化描述

一般来说（对于偶数的N），上述分块的结果可以表示为下图，其中xN2表示偶数行，xN2+1表示奇数行。

因为w是方程zN=1的单位根，因此wN=1。为了方便讨论，我们这里考虑N为偶数的情况，于是wN2=−1。那么，我们可以得到四个分块矩阵的关系：

是我们只需要计算对偶数下标的元素作用D1、对奇数下标的元素作用D3得到的结果D1xN2和D3xN2+1，就可以得到Dx的完整结果了。

离散傅里叶变换的递归结构

注意到D1=ωi⋅(2j)=(ω2)ij就是N2个元素的DFT矩阵，于是D1xN2就是对下标为偶数的N2个元素进行离散傅里叶变换的结果。

注意到D3=ωi(2j−N+1)=(ω2)ij∗ωi，D3与D1之间只差了一个行变换，因此D3xN2+1就是对下标为奇数的N2个元素进行离散傅里叶变换、再对第i个元素乘以ωi的结果。

由此我们得到了离散傅里叶变换的递归结构：

N个元素的离散傅里叶变换结果可以从奇数下标、偶数下标的N2个元素分别进行离散傅里叶变换的结果中得到。

快速傅里叶变换的复杂度

记N个元素的快速傅里叶变换复杂度为T(N)，根据递归结构，可得到以下递归公式：T(N)=2T(N2)+O(N)。于是，根据复杂度计算的主定理，立刻就能得到快速傅里叶变换的时间复杂度为O(Nlog⁡N)。

离散傅里叶变换的一些应用

离散傅里叶变换矩阵经常出现在一些特殊矩阵的分解中。

循环矩阵（circulant matrix）

循环矩阵是由第一行反复移动得到的：

可以证明，C=D−1diag{Dc}D，其中c是C的第一列。于是Cx=D−1diag{Dc}Dx，即Dc与Dx的逐元素乘法结果再做离散傅里叶变换的逆变换D−1。于是涉及循环矩阵的矩阵-向量乘法也可以通过O(Nlog⁡N)时间得到结果。

Teoplitz矩阵

Teoplitz矩阵由第一行和第一列共同决定，其他元素沿着对角线方向进行复制：

神奇的事情：大小为n×n的Teoplitz矩阵可以被放在大小为2n×2n的循环矩阵中。下图的分块矩阵，左上角和右下角是两个一样的Teoplitz矩阵。

于是包含Teoplitz矩阵的矩阵-向量乘法可以表示成循环矩阵的乘法，也可以在O(Nlog⁡N)时间内得到结果。