當N不是2的冪時，Numpy（Python）中的FFT

我的問題是關於在Numpy的FFT函數中使用的算法。當N不是2的冪時，Numpy（Python）中的FFT

Numpy的文檔說它使用Cooley-Tukey算法。但是，正如您所知，只有當點數N是2的冪時，此算法纔有效。

爲了計算其FFT FFT [k]，numpy填充我的輸入向量x [n]嗎？（我不這麼認爲，因爲我在輸出中的點數也是N）。我怎麼能真正「看到」numpy使用的FFT函數的代碼？

乾杯！

來源

2012-12-12 Pedro Rodrigues

http://stackoverflow.com/questions/6855169/convolution-computations-in-numpy-scipy – mmgp

嗯...這是一種[實際看到代碼]的方法（https://github.com/numpy/ numpy的/樹/主/ numpy的/ FFT）。如果這不是你的意思，那麼也許你應該改述。 – senderle

簡單的攻擊是下采樣到下一個最低的2次方。也許甚至會多次選擇隨機排除哪些點，並將結果平均到一起。 – wberry

該文檔說numpy的FFT是基於FFTPACK。

在FFTPACK文檔我發現以下：

子程序rffti（N，wsave）

子程序rffti初始化其在兩個 rfftf使用和陣列wsave rfftb。計算n的素因子分解以及三角函數的列表並將其存儲在wsave中。

標準庫利-的Tukey算法是「基數2與時間抽取」，這降低了遞歸大小2*n的FFT的計算成2點的FFT大小爲n的，加N大小2的FFT的有相同算法的一般分解版本，將大小爲m*n的FFT轉換爲大小爲m的n個FFT和大小爲n的m個FFT。事實上FFTPACK中的準備例程計算輸入大小的主要因式分解，似乎表明這是他們正在做的事情。所以除非你需要大量的元素，否則你的元素數量有很大的主要因素，你仍然應該得到很好的加速。

幾年前我寫了關於Cooley-Tukey算法的radix-2和general factorization版本的博客。閱讀這些可能有助於理解NumPy內部似乎正在發生的事情。下面的圖片，從那裏取，描繪了CT FFT：

enter image description here

來源

2012-12-12 14:57:42 Jaime

和對於素數大小，它只是做蠻力DFT，而不是FFT，對嗎？ – endolith

@endolith這就是它似乎正在發生的事情。有[用於素數大小輸入的FFT算法]（http：// en。wikipedia.org/wiki/Rader's_FFT_algorithm），我認爲FFTW有一些。但是在我的numpy安裝中，做一些時間安排似乎表明素數大小是強制性的，是的。 – Jaime

在我的經驗，算法不做自動填充，或者至少他們中的一些沒有。例如，對長度不等於2的冪的信號運行scipy.signal.hilbert方法大約需要45秒。當我用零填充信號到這樣一個長度時，花了100ms。

YMMV但基本上每次運行信號處理算法時都要仔細檢查。

來源

2013-10-12 02:52:34 choldgraf

當N不是2的冪時，Numpy（Python）中的FFT

回答

相關問題