N不是2的幂时的Numpy中的FFT(Python) [英] FFT in Numpy (Python) when N is not a power of 2
问题描述
我的问题是关于Numpy的FFT函数中使用的算法.
My question is about the algorithm which is used in Numpy's FFT function.
Numpy的文档说它使用Cooley-Tukey算法.但是，您可能知道，该算法仅在点的数量N为2的幂时有效.
The documentation of Numpy says that it uses the Cooley-Tukey algorithm. However, as you may know, this algorithm works only if the number N of points is a power of 2.
numpy是否填充我的输入向量x [n]以计算其FFT X [k]? (我不这样认为，因为我在输出中得到的点数也是N).我实际上如何才能看到" numpy用于其FFT功能的代码?
Does numpy pad my input vector x[n] in order to calculate its FFT X[k]? (I don't think so, since the number of points I have in the output is also N). How could I actually "see" the code which is used by numpy for its FFT function?
干杯！
推荐答案
文档说numpy的FFT基于 FFTPACK .
The docs say numpy's FFT is based on FFTPACK.
在FFTPACK文档中，我发现了以下内容:
In the FFTPACK docs I find the following:
子例程rffti(n，wsave)
subroutine rffti(n,wsave)
子例程rffti初始化数组wsave，这两个数组都使用 rfftf和rfftb. n与a的素因式分解 三角函数的列表计算并存储在 保存.
subroutine rffti initializes the array wsave which is used in both rfftf and rfftb. the prime factorization of n together with a tabulation of the trigonometric functions are computed and stored in wsave.
标准的Cooley-Tukey算法为具有时间抽取的基数2"，它递归地将大小为2*n的FFT的计算减少为大小为n的2个FFT，加上大小为2的n个FFT.该算法的通用分解版本，将大小为c1的FFT转换为大小为m的n个FFT加大小为n的m个FFT. FFTPACK中的准备例程计算输入大小的素因数这一事实似乎表明这是他们正在做的事情.因此，除非您要使用素数的元素，或者您的素数的素数非常大，否则您仍然应该获得相当不错的提速.
The standard Cooley-Tukey algorithm is "radix-2 with decimation in time", which recursively reduces the computation of an FFT of size 2*n into 2 FFTs of size n, plus n FFTs of size 2. There is a general factorization version of the same algorithm that turns an FFT of size m*ninto n FFTs of size m plus m FFTs of size n. The fact that the preparation routines in FFTPACK compute the prime factorization of the input size, seems to indicate this is what they are doing. So unless you go for a prime number of elements, or your number of elements has a very large prime factor, you should still get a pretty good speed-up.
A few years back I blogged about both the radix-2 and general factorization versions of Cooley-Tukey's algorithmn. Reading those may help understand what seems to be going on inside NumPy. The following picture, taken from there, depicts a CT FFT:
这篇关于N不是2的幂时的Numpy中的FFT(Python)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
