定义和速度

用FFT计算DFT会得到与直接用DFT定义计算相同的结果；最重要的区别是FFT更快。（由于舍入误差的存在，许多FFT算法还会比直接运用定义求值精确很多，后面会讨论到这一点。）

令 x0, ...., xN-1 为复数。DFT由下式定义

直接按这个定义求值需要 O(N) 次运算：Xk 共有 N 个输出，每个输出需要 N 项求和。直接使用DFT运算需使用N个复数乘法(4N 个实数乘法)与N-1个复数加法(4N-2个实数加法)，因此，计算使用DFT所有N点的值需要N复数乘法与N-N 个复数加法。FFT则是能够在 O(N log N) 次操作计算出相同结果的任何方法。更准确的说，所有已知的FFT算法都需要O(N log N) 次运算（技术上O只标记上界），虽然还没有已知的证据证明更低的复杂度是不可能的。（Johnson and Frigo, 2007）

要说明FFT节省时间的方式，就得考虑复数相乘和相加的次数。直接计算DFT的值涉及到 N 次复数相乘和 N(N−1) 次复数相加（可以通过削去琐碎运算（如乘以1）来节省 O(N) 次运算）。众所周知的基2库利-图基算法，N 为2的幂，可以只用 (N/2)log2(N) 次复数乘法（再次忽略乘以1的简化）和 Nlog2(N) 次加法就可以得到相同结果。在实际中，现代计算机通常的实际性能通常不受算术运算的速度和对复杂主体的分析主导（参见Frigo & Johnson, 2005），但是从 O(N) 到 O(N log N) 的总体改进仍然能够体现出来。

一般的简化理论

假设一个M*N型矩阵S可分解成列向量以及行向量相乘：

S = [ a 1 a 2 ⋮ ⋮ --> a m ] [ b 1 b 2 ⋯ ⋯ --> b n ] {\displaystyle \mathbf {S} ={\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{m}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}}

若 [ a 1 a 2 ⋯ ⋯ --> a m ] T {\displaystyle {\begin{bmatrix}a_{1}&a_{2}&\cdots &a_{m}\end{bmatrix}}^{T}} 有 M 0 {\displaystyle M_{0}} 个相异的非平凡值（ a m ≠ ≠ --> ± ± --> 2 k , a m ≠ ≠ --> ± ± --> 2 k a n {\displaystyle a_{m}\neq \pm 2^{k},a_{m}\neq \pm 2^{k}a_{n}} where m ≠ ≠ --> n {\displaystyle m\neq n} ）　

[ b 1 b 2 ⋯ ⋯ --> b n ] {\displaystyle {\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}} 有 N 0 {\displaystyle N_{0}} 个相异的非平凡值

则S共需要 M 0 ∗ ∗ --> N 0 {\displaystyle M_{0}*N_{0}} 个乘法。

[ Z [ 1 ] Z [ 2 ] ⋮ ⋮ --> Z [ N ] ] = S [ X [ 1 ] X [ 2 ] ⋮ ⋮ --> X [ N ] ] = [ a 1 a 2 ⋮ ⋮ --> a m ] [ b 1 b 2 ⋯ ⋯ --> b n ] [ X [ 1 ] X [ 2 ] ⋮ ⋮ --> X [ N ] ] {\displaystyle {\begin{bmatrix}Z[1]\\Z[2]\\\vdots \\Z[N]\end{bmatrix}}=\mathbf {S} {\begin{bmatrix}X[1]\\X[2]\\\vdots \\X[N]\end{bmatrix}}={\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{m}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}{\begin{bmatrix}X[1]\\X[2]\\\vdots \\X[N]\end{bmatrix}}}

Step 1： Z a = b 1 X [ 1 ] + b 2 X [ 2 ] + ⋯ ⋯ --> + b n X [ N ] {\displaystyle Z_{a}=b_{1}X[1]+b_{2}X[2]+\cdots +b_{n}X[N]}

Step 2： Z [ 1 ] = a 1 Z a , Z [ 2 ] = a 2 Z a , ⋯ ⋯ --> , Z [ N ] = a m Z a {\displaystyle Z[1]=a_{1}Z_{a},Z[2]=a_{2}Z_{a},\cdots ,Z[N]=a_{m}Z_{a}}

简化理论的变型：

S = [ a 1 a 2 ⋮ ⋮ --> a m ] [ b 1 b 2 ⋯ ⋯ --> b n ] + S 1 {\displaystyle \mathbf {S} ={\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{m}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}+\mathbf {S} _{1}}

S 1 {\displaystyle S_{1}} 也是一个M*N的矩阵。

若 S 1 {\displaystyle S_{1}} 有 P 1 {\displaystyle P_{1}} 个值不等于0，则 S {\displaystyle \mathbf {S} } 的乘法量上限为 M 0 + N 0 + P 1 {\displaystyle M_{0}+N_{0}+P_{1}} 。

快速傅里叶变换乘法量的计算

假设 N = P 1 × × --> P 2 × × --> ⋯ ⋯ --> × × --> P k {\displaystyle N=P_{1}\times P_{2}\times \cdots \times P_{k}} ，其中 P 1 , P 2 , ⋯ ⋯ --> , P k {\displaystyle P_{1},P_{2},\cdots ,P_{k}} 彼此互素

P k {\displaystyle \mathbf {P_{k}} } 点DFT的乘法量为 B k {\displaystyle \mathbf {B_{k}} } ，则 N {\displaystyle \mathbf {N} } 点DFT的乘法量为：

假设 N = P c {\displaystyle \mathbf {N=P^{c}} } ，P是一个素数。

若 N 1 = P a {\displaystyle \mathbf {N_{1}=P^{a}} } 点的DFT需要的乘法量为 B 1 {\displaystyle \mathbf {B_{1}} }

且 n 1 × × --> n 2 {\displaystyle n_{1}\times n_{2}} 当中（ n 1 = 0 , 1 , ⋯ ⋯ --> , N 1 − − --> 1 , n 2 = 0 , 1 , ⋯ ⋯ --> , N 2 − − --> 1 {\displaystyle n_{1}=0,1,\cdots ,N_{1}-1,\quad n_{2}=0,1,\cdots ,N_{2}-1} ）

有 D 1 {\displaystyle D_{1}} 个值不为 N 12 {\displaystyle {\frac {N}{12}}} 及 N 8 {\displaystyle {\frac {N}{8}}} 的倍数，

有 D 2 {\displaystyle D_{2}} 个值为 N 12 {\displaystyle {\frac {N}{12}}} 及 N 8 {\displaystyle {\frac {N}{8}}} 的倍数，但不为 N 4 {\displaystyle {\frac {N}{4}}} 的倍数，

则N点DFT的乘法量为：

库利-图基算法

库利-图基算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为 N = N 1 N 2 {\displaystyle N=N_{1}N_{2}} 的离散傅里叶变换分解为长度为 N 1 {\displaystyle N_{1}} 的 N 2 {\displaystyle N_{2}} 个较短序列的离散傅里叶变换，以及与 O ( N ) {\displaystyle \mathrm {O} (N)} 个旋转因子的复数乘法。

这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法（此算法在历史上数次以各种形式被再次提出）。

库利-图基算法最有名的应用，是将序列长为N 的DFT分区为两个长为N/2 的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey都指出的那样，Cooley-Tukey算法也可以用于序列长度N 为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显式的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。

目前最常用的快速傅里叶变换是库利-图基（Cooley-Tukey）算法。该算法利用分治法，将一个常数n的离散傅里叶变换递归地分解为两个常数分别为 n 1 {\displaystyle n_{1}} 和 n 2 {\displaystyle n_{2}} 的变换，保证 n = n 1 n 2 {\displaystyle n=n_{1}n_{2}} ，从而简化了原来的离散傅里叶变换。

设计思想

下面，我们用N次单位根 W N {\displaystyle W_{N}} 来表示 e − − --> j 2 π π --> N {\displaystyle e^{-j{\frac {2\pi }{N}}}} 。

W N {\displaystyle W_{N}} 的性质：

周期性， W N {\displaystyle W_{N}} 具有周期 N {\displaystyle N} ，即 W N k + N = W N k {\displaystyle W_{N}^{k+N}=W_{N}^{k}}

对称性： W N k + N 2 = − − --> W N k {\displaystyle W_{N}^{k+{\frac {N}{2}}}=-W_{N}^{k}} 。

若 m {\displaystyle m} 是 N {\displaystyle N} 的约数， W N m k n = W N m k n {\displaystyle W_{N}^{mkn}=W_{\frac {N}{m}}^{kn}}

为了简单起见，我们下面设待变换序列长度 n = 2 r {\displaystyle n=2^{r}} 。根据上面单位根的对称性，求级数 y k = ∑ ∑ --> n = 0 N − − --> 1 W N k n x n {\displaystyle y_{k}=\sum _{n=0}^{N-1}W_{N}^{kn}x_{n}} 时，可以将求和区间分为两部分：

y k = ∑ ∑ --> n = 2 t W N k n x n + ∑ ∑ --> n = 2 t + 1 W N k n x n = ∑ ∑ --> t W N 2 k t x 2 t + W N k ∑ ∑ --> t W N 2 k t x 2 t + 1 = F e v e n ( k ) + W N k F o d d ( k ) ( i ∈ ∈ --> Z ) {\displaystyle {\begin{matrix}y_{k}=\sum _{n=2t}W_{N}^{kn}x_{n}+\sum _{n=2t+1}W_{N}^{kn}x_{n}\\=\sum _{t}W_{\frac {N}{2}}^{kt}x_{2t}+W_{N}^{k}\sum _{t}W_{\frac {N}{2}}^{kt}x_{2t+1}\\=F_{even}(k)+W_{N}^{k}F_{odd}(k)&&&&&&(i\in \mathbb {Z} )\end{matrix}}}

F o d d ( k ) {\displaystyle F_{odd}(k)} 和 F e v e n ( k ) {\displaystyle F_{even}(k)} 是两个分别关于序列 { x n } 0 N − − --> 1 {\displaystyle \left\{x_{n}\right\}_{0}^{N-1}} 奇数号和偶数号序列N/2点变换。由此式只能计算出 y k {\displaystyle y_{k}} 的前N/2个点，对于后N/2个点，注意 F o d d ( k ) {\displaystyle F_{odd}(k)} 和 F e v e n ( k ) {\displaystyle F_{even}(k)} 都是周期为N/2的函数，由单位根的对称性，于是有以下变换公式：

y k + N 2 = F e v e n ( k ) − − --> W N k F o d d ( k ) {\displaystyle y_{k+{\frac {N}{2}}}=F_{even}(k)-W_{N}^{k}F_{odd}(k)}

y k = F e v e n ( k ) + W N k F o d d ( k ) {\displaystyle y_{k}=F_{even}(k)+W_{N}^{k}F_{odd}(k)} 。

这样，一个N点变换就分解成了两个N/2点变换。照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。根据主定理不难分析出此时算法的时间复杂度为 O ( N log ⁡ ⁡ --> N ) {\displaystyle \mathrm {O} (N\log N)}

算法实现

蝶形结网络和位反转（Bit Reversal）：

001 倒置以后变成 100

010 --〉 010

011 --〉 110

100 --〉 001

101 --〉 101

110 --〉 011

111 --〉 111

倒置后的编号为{0,4,2,6,1,5,3,7}。

算法复杂度

由于按蝶形结网络计算n点变换要进行log n层计算，每层计算n个点的变换，故算法的时间复杂度为 O ( n log ⁡ ⁡ --> n ) {\displaystyle \mathrm {O} (n\log n)} 。

其他算法

在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度 N = N 1 N 2 {\displaystyle N=N_{1}N_{2}} 且 N 1 {\displaystyle N_{1}} 与 N 2 {\displaystyle N_{2}} 互质的序列，可以采用基于中国剩余定理的互质因子算法将N长序列的DFT分解为两个子序列的DFT。与Cooley-Tukey算法不同的是，互质因子算法不需要旋转因子。

Rader-Brenner算法是类似于Cooley-Tukey算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radix variant of Cooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性。

Bruun以及QFT算法是不断的把DFT分成许多较小的DFT运算。（Rader-Brenner以及QFT算法是为了2的指数所设计的算法，但依然可以适用在可分解的整数上。Bruun算法则可以运用在可被分成偶数个运算的数字）。尤其是Bruun算法，把FFT看成是 z N − − --> 1 {\displaystyle z^{N}-1} ，并把它分解成 z M − − --> 1 {\displaystyle z^{M-1}} 与 z 2 M + a z M + 1 {\displaystyle z^{2M}+az^{M}+1} 的形式。

另一个从多项式观点的快速傅立叶变换法是Winograd算法。此算法把 z N − − --> 1 {\displaystyle z^{N}-1} 分解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。这样只需要很少的乘法量（如果有需要的话），所以winograd是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd算法让DFT可以用 2 k {\displaystyle 2^{k}} 点的DFT来简化，但减少乘法量的同时，也增加了非常多的加法量。Winograd也可以利用剩余值定理来简化DFT。

Rader算法提出了利用点数为N（N为素数）的DFT进行长度为N-1的回旋折积来表示原本的DFT，如此就可利用折积用一对基本的FFT来计算DFT。另一个prime-size的FFT算法为chirp-Z算法。此法也是将DFT用折积来表示，此法与Rader算法相比，能运用在更一般的转换上，其转换的基础为Z转换（Rabiner et al., 1969）。

实数或对称资料专用的算法

在许多的运用当中，要进行DFT的资料是纯实数，如此一来经过DFT的结果会满足对称性：

而有一些算法是专门为这种情形设计的（e.g. Sorensen, 1987）。另一些则是利用旧有的算法（e.g. Cooley-Tukey），删去一些不必要的演算步骤，如此省下了记忆体的使用，也省下了时间。另一方面，也可以把一个偶数长度且纯实数的DFT，用长度为原本一半的复数型态DFT来表示（实数项为原本纯实数资料的偶数项，虚数项则为奇数项）。

一度人们认为，用离散哈特利转换（Discrete Hartley Transform）来处理纯实数的DFT会更有效率，但接着人们发现，对于同样点数的纯实数DFT，经过设计的FFT，可以比DHT省下更多的运算。Bruun算法是第一个试着从减少实数输入的DFT运算量的算法，但此法并没有成为人们普遍使用的方法。

对于实数输入，且输入为偶对称或奇对称的情形，可以更进一步的省下时间以及记忆体，此时DFT可以用离散余弦转换或离散正弦转换来代替（Discrete cosine/sine transforms）。由于DCT/DST也可以设计出FFT的算法，故在此种情形下，此方法取代了对DFT设计的FFT算法。

DFT可以应用在频谱分析以及做折积的运算，而在此处，不同应用可以用不同的算法来取代，列表如下：

用来做频谱分析的情况下，DFT可用下列的算法代替：

DCT

DST

DHT

正交基底的扩展（orthogonal basis expantion）包括正交多项式（orthogonal polynomials）以及CDMA.

Walsh（Hadamard）转换

Haar转换

小波（wavelet）转换

时频分布（time-frequency distribution）

用来做折积的情况下，DFT可用下列的算法代替：

DCT

DST

DHT

直接做折积（direct computing）

分段式DFT折积（sectioned DFT convolution）

威诺格拉德快速傅里叶变换算法

Walsh（Hadamard）转换

数论转换

复杂度以及运算量的极限

长久以来，人们对于求出快速傅里叶变换的复杂度下限以及需要多少的运算量感到很有兴趣，而实际上也还有许多问题需要解决。即使是用较简单的情形，即 2 k {\displaystyle 2^{k}} 点的DFT，也还没能够严谨的证明出FFT至少需要 Ω Ω --> ( N l o g N ) {\displaystyle \Omega (NlogN)} （比NlogN大）的运算量，目前也没有发现复杂度更低的算法。通常数算量的多寡会是运算效率好坏最主要的因素，但在现实中，有许多因素也会有很大的影响，如高速缓存以及CPU均有很大的影响。

在1978年，Winograd率先导出一个较严谨的FFT所需乘法量的下限： Θ Θ --> ( N ) {\displaystyle \Theta (N)} 。当 N = 2 k {\displaystyle N=2^{k}} 时，DFT只需要 4 N − − --> 2 log 2 2 ⁡ ⁡ --> N − − --> 2 log 2 ⁡ ⁡ --> N − − --> 4 {\displaystyle 4N-2\log _{2}^{2}N-2\log _{2}N-4} 次无理实数的乘法即可以计算出来。更详尽，且也能趋近此下限的算法也一一被提出（Heideman & Burrus, 1986; Duhamel, 1990）。很可惜的是，这些算法，都需要很大量的加法计算，目前的硬件无法克服这个问题。

对于所需加法量的数目，虽然我们可以在某些受限制的假设下，推得其下限，但目前并没有一个精确的下限被推导出来。1973年，Morgenstern在乘法常数趋近巨大的情形下（对大部分的FFT算法为真，但不是全部）推导出加法量的下限： Ω Ω --> ( N log ⁡ ⁡ --> N ) {\displaystyle \Omega \left(N\log N\right)} 。Pan（1986）在假设FFT算法的不同步的情形有其极限下证明出加法量的下限 Ω Ω --> ( N l o g N ) {\displaystyle \Omega (NlogN)} ，但一般来说，此假设相当的不明确。长度为 N = 2 k {\displaystyle N=2^{k}} 的情形下，在某些假设下，Papadimitriou（1979）提出使用Cooley-Tukey算法所需的复数加法量 N log 2 ⁡ ⁡ --> N {\displaystyle N\log _{2}N} 是最少的。到目前为止，在长度为 N = 2 k {\displaystyle N=2^{k}} 情况，还没有任何FFT的算法可以让复数的加法量比 N log 2 ⁡ ⁡ --> N {\displaystyle N\log _{2}N} 还少。

还有一个问题是如何把乘法量与加法量的总和最小化，有时候称作"演算复杂度"（在这里考虑的是实际的运算量，而不是渐近复杂度）。同样的，没有一个严谨下限被证明出来。从1968年开始， N = 2 k {\displaystyle N=2^{k}} 点DFT而言，split-radix FFT算法需要最少的运算量，在 N > 1 {\displaystyle N>1} 的情形下，其需要 4 N log 2 ⁡ ⁡ --> N − − --> 6 N + 8 {\displaystyle 4N\log _{2}N-6N+8} 个乘法运算以及加法运算。最近有人导出更低的运算量： 34 9 N log 2 ⁡ ⁡ --> N {\displaystyle {\frac {34}{9}}N\log _{2}N} 。（Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007）

大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数数据输入的情况，因其为最简单的情形。但是，复数数据输入的FFT算法，与实数数据输入的FFT算法，离散余弦变换（DCT），离散哈特列变换（DHT），以及其他的算法，均有很大的关连性。故任何一个算法，在复杂度上有任何的改善的话，其他的算法复杂度也会马上获得改善（Duhamel & Vetterli, 1990）。

参阅

离散傅里叶变换

并行快速傅里叶变换

延伸阅读

Brenner, N.; Rader, C. A New Principle for Fast Fourier Transformation. IEEE Acoustics, Speech & Signal Processing. 1976, 24 (3): 264–266. doi:10.1109/TASSP.1976.1162805. 

Brigham, E. O. The Fast Fourier Transform. New York: Prentice-Hall. 2002. 

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 30. (Polynomials and the FFT). Introduction to Algorithms 2. MIT Press and McGraw-Hill. 2001. ISBN 0-262-03293-7. 

Duhamel, Pierre. Algorithms meeting the lower bounds on the multiplicative complexity of length-2 DFTs and their connection with practical algorithms. IEEE Trans. Acoust. Speech. Sig. Proc. 1990, 38 (9): 1504–151. doi:10.1109/29.60070. 

Duhamel, P.; Vetterli, M. Fast Fourier transforms: a tutorial review and a state of the art. Signal Processing. 1990, 19: 259–299. doi:10.1016/0165-1684(90)90158-U. 

Edelman, A.; McCorquodale, P.; Toledo, S. The Future Fast Fourier Transform?. SIAM J. Sci. Computing. 1999, 20: 1094–1114. doi:10.1137/S1064827597316266. 

D. F. Elliott, & K. R. Rao, 1982, Fast transforms: Algorithms, analyses, applications. New York: Academic Press.

Funda Ergün, 1995,Testing multivariate linear functions: Overcoming the generator bottleneck, Proc. 27th ACM Symposium on the Theory of Computing: 407–416.

Frigo, M.; Johnson, S. G.The Design and Implementation of FFTW3(PDF). Proceedings of the IEEE. 2005, 93: 216–231. doi:10.1109/jproc.2004.840301. 

H. Guo and C. S. Burrus, 1996,Fast approximate Fourier transform via wavelets transform, Proc. SPIE Intl. Soc. Opt. Eng.2825: 250–259.

H. Guo, G. A. Sitton, C. S. Burrus, 1994,The Quick Discrete Fourier Transform, Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP)3: 445–448.

Steve Haynal and Heidi Haynal, "Generating and Searching Families of FFT Algorithms", Journal on Satisfiability, Boolean Modeling and Computation vol. 7, pp. 145–187 (2011).

Heideman, Michael T.; Burrus, C. Sidney. On the number of multiplications necessary to compute a length-2 DFT. IEEE Trans. Acoust. Speech. Sig. Proc. 1986, 34 (1): 91–95. doi:10.1109/TASSP.1986.1164785. 

Johnson, S. G.; Frigo, M.A modified split-radix FFT with fewer arithmetic operations(PDF). IEEE Trans. Signal Processing. 2007, 55 (1): 111–119. doi:10.1109/tsp.2006.882087. 

T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2," Computing80 (1): 23–45.

Kent, Ray D. and Read, Charles (2002). Acoustic Analysis of Speech. ISBN 978-0-7693-0112-9. Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250–255.

Morgenstern, Jacques. Note on a lower bound of the linear complexity of the fast Fourier transform. J. ACM. 1973, 20 (2): 305–306. doi:10.1145/321752.321761. 

Mohlenkamp, M. J.A fast transform for spherical harmonics(PDF). J. Fourier Anal. Appl. 1999, 5 (2–3): 159–184. doi:10.1007/BF01261607. 

Nussbaumer, H. J. Digital filtering using polynomial transforms. Electronics Lett. 1977, 13 (13): 386–387. doi:10.1049/el:19770280. 

V. Pan, 1986,The trade-off between the additive complexity and the asyncronicity of linear and bilinear algorithms, Information Proc. Lett.22: 11–14.

Christos H. Papadimitriou, 1979,Optimality of the fast Fourier transform, J. ACM26: 95–102.

D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial", in: J.J. Benedetto and P. Ferreira (Eds.), Modern Sampling Theory: Mathematics and Applications (Birkhauser).

Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P.,Chapter 12. Fast Fourier Transform, Numerical Recipes: The Art of Scientific Computing 3, New York: Cambridge University Press, 2007, ISBN 978-0-521-88068-8 

Rokhlin, Vladimir; Tygert, Mark. Fast algorithms for spherical harmonic expansions. SIAM J. Sci. Computing. 2006, 27 (6): 1903–1928. doi:10.1137/050623073. 

Schatzman, James C.Accuracy of the discrete Fourier transform and the fast Fourier transform. SIAM J. Sci. Comput. 1996, 17: 1150–1166. doi:10.1137/s1064827593247023. 

Shentov, O. V.; Mitra, S. K.; Heute, U.; Hossen, A. N. Subband DFT. I. Definition, interpretations and extensions. Signal Processing. 1995, 41 (3): 261–277. doi:10.1016/0165-1684(94)00103-7. 

Sorensen, H. V.; Jones, D. L.; Heideman, M. T.; Burrus, C. S. Real-valued fast Fourier transform algorithms. IEEE Trans. Acoust. Speech Sig. Processing. 1987, 35 (35): 849–863. doi:10.1109/TASSP.1987.1165220.  See also Sorensen, H.; Jones, D.; Heideman, M.; Burrus, C. Corrections to "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 1987, 35 (9): 1353–1353. doi:10.1109/TASSP.1987.1165284. 

Welch, Peter D. A fixed-point fast Fourier transform error analysis. IEEE Trans. Audio Electroacoustics. 1969, 17 (2): 151–157. doi:10.1109/TAU.1969.1162035. 

Winograd, S. On computing the discrete Fourier transform. Math. Computation. 1978, 32 (141): 175–199. JSTOR 2006266. doi:10.1090/S0025-5718-1978-0468306-4. 

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。