FFT 卷积不比规范卷积计算快

Question

几个月前我发现使用 FFT 算法（甚至更多使用 FFTW 库）以最快的方式计算卷积

使用下面的代码我得到了有争议的结果。

进口

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 库，它是 "the fastest in the west"...

感谢任何指导。

我的结论是 numba JIT 编译速度快得令人难以置信。

Answer 1

使用这种类型的语法，您应该能够创建更少的临时数组，这应该会使速度更快。

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

Answer 2

您只是 return 卷积的单个值（n:th 一个值），而不是整个数组。使用 FFT 你总是计算所有的值，而在你的 conv 函数中你只计算你想要的那个。复杂性方面，FFT 是 O(N*log(N))，而您的 conv 实现是 O(N)。如果你要实现一个 return 完整卷积的简单转换函数，它将是 O(N^2)。所以，如果你想要完整的复杂阵列，你最好的选择是 FFT 方法。如果您只想要 n:th 值，那么您的方法在复杂性方面是最好的。

FFT 卷积不比规范卷积计算快

FFT convolution not being faster than the cannonical convolution computation

python

numba