当N不是2的幂时,Numpy(Python)中的FFT

Question

我的问题是关于在Numpy的FFT函数中使用的算法.

Numpy的文档说它使用Cooley-Tukey算法.但是,如您所知,此算法仅在点数N为2的幂时才有效.

numpy填充我的输入向量x [n]以计算其FFT X [k]？(我不这么认为,因为我在输出中的点数也是N).我怎么能真正"看到"numpy为其FFT函数使用的代码？

干杯!

Answer 1

文档称numpy的FFT基于FFTPACK.

在FFTPACK文档中,我发现以下内容:

子程序rffti(n,wsave)

子程序rffti初始化在rfftf和rfftb中使用的数组wsave.计算n的素因子化和三角函数的列表,并将其存储在wsave中.

标准的Cooley-Tukey算法是"带有时间抽取的基数-2",它递归地将大小2*n为FFT 的计算减少为2个大小为n的FFT,加上大小为2的n个FFT.有一个通用的因子分解版本将大小m*n为FFT的算法转换为大小为m的n个FFT加上大小为n的m个FFT.事实上,FFTPACK中的准备程序计算输入大小的素数因子化,似乎表明这就是他们正在做的事情.因此,除非你选择了素数元素,或者你的元素数量具有非常大的素数因素,你仍然可以获得相当好的加速.

几年前,我在博客上写了关于Cooley-Tukey算法的radix-2和一般分解版本.阅读这些内容可能有助于了解NumPy内部的情况.从那里拍摄的下图描绘了CT FFT: