The Fast Fourier Transform

在各种有关数值计算的算法中，往往会需要使用快速傅里叶变换以加速计算，快速傅里叶变换（FFT）之所以广泛地应用于数值计算的各个领域，是因为这种算法只需步就可以得到个格点上的离散傅里叶变换。本文将从有限群上的分析和线性代数两方面分别简要介绍该算法的原理。

模N剩余类上的Fourier变换

这一部分我们处理的对象是定义在模剩余类上的函数，目标是尽可能高效地得到的Fourier系数。首先需要对问题进行一些分析。

模N剩余类与N阶单位群

注意到与之间存在显然的同构:

由此可见上的全体函数空间与上的全体函数空间同构，因此考虑定义在上的函数相当于研究在单位圆上的上定义的函数空间，即：

从这个角度来看，寻找的傅里叶变换本质上等价于寻找上述：在通常的内做Fourier变换时可以表示成积分或级数的形式，但在时则退化为有限和，此时Fourier变换就是Fourier展开，这种情况下无需考虑收敛问题，因此相对更加容易处理。

Fourier定理与Plancherel公式

在内对函数做Fourier展开可以视作是在对关于正交基进行正交分解:

因此当考虑时同样希望找到内的某族类似的正交基，使得可以像上面那样展开。借助上一节的同构不难看出在内，是一个合适的选择。我们现在定义内的一个内积为：

则可以验证这些函数确实关于该内积互相正交：

上述内积诱导出了一个范数，稍后将看到，即Plancherel公式在这种情况下同样成立。
注意到具有一组有限基为，因此的维数为，而互相正交于是线性无关，进而也是的一组基，所以中的可以使用这组正交基线性表出：

这实际上是在上的Fourier逆变换。类似地可以关于对标准化之后得到的标准正交基

进行展开，最终的结果都可以表示为如下形式，其中是的Fourier系数：

综上，内的Fourier变换可以定义为

这里的就是第个Fourier系数。直接计算可以得到内的Plancherel公式