FFT卷積不是比cannonical卷積計算

幾個月前，我發現，盤旋在最快的方式使用FFT算法（更與FFTW庫）FFT卷積不是比cannonical卷積計算

使用下面的代碼計算速度更快我有爭議的結果。

進口

from scipy import fftpack 
from numba import jit

卷積用FFT：使用下面的公式

def conv_fft(X, R): 
    n = len(X) 
    a = fftpack.fft(X) 
    b = fftpack.fft(R) 
    c = a * b 
    e = fftpack.ifft(c) 
    result = e[n] 
    return result

卷積：

@jit(cache=True) 
def conv(X, R): 
    n = len(X)  
    result = complex_type(0) 
    for i in range(n+1): 
     result += X[n-i] * R[i] 
    return result

這是在一個多複雜的過程關鍵的功能，所不同的產生僅僅由使用一個版本或其他。

 no FFT  with FFT increment 
Test1 0.028761 0.034139 0.0053780 
Test2 0.098565 0.103180 0.0046150

**的test2的每次測試計算更多的迴旋。*

的測試表明，與FFT的代碼是慢，我不明白爲什麼，因爲fftpack顯然致電FFTW庫，是「的最快在西部「 ...

任何指導表示讚賞。

我的一個結論是numba JIT彙編速度令人難以置信。

來源

2016-02-20 Santi Peñate-Vera

您只返回卷積的單個值（第n個），而不是整個數組。使用FFT，您總是可以計算所有值，而在您的conv函數中，您只能計算出您之後的值。複雜性方面，FFT是O（N * log（N）），並且您的conv的實現是O（N）。如果你要實現一個能夠返回完整卷積的樸素轉化函數，它將是O（N^2）。所以，如果你想要完整的複雜數組，你最好的選擇就是使用FFT的方式。如果你只想要第n個值，那麼你的方法是複雜性最好的。

來源

2016-02-20 21:57:38 ilmarinen

有沒有辦法使用FFT算法來獲取我需要的值？它會產生任何增益嗎？ –

If你只需要第n個值，沒有任何意義，你可以按照你的方式去做e it，但使用FFT算法，您必須計算數組中的所有值。 – ilmarinen

你應該能夠通過使用這種類型的語法來創建更少的臨時數組，這應該使其更快。

def conv_fft(X, R): 
    fftpack.fft(X, overwrite_x=True) 
    b = fftpack.fft(R) 
    X *= b 
    fftpack.ifft(X, overwrite_x=True) 
    return X

來源

2016-02-20 21:43:23 Benjamin

謝謝，我會測試這個並回到問題 –

我沒有包括len（X檢查，不知道是否需要這個，你也可以直接使用fftpack的convolve ... – Benjamin

我有測試它並且FFT仍然較慢（雖然比之前快一點），對於記錄我測量的平均執行次數爲100 –

FFT卷積不是比cannonical卷積計算

回答

相關問題