python - 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 库，这是“西方最快的”...

感谢任何指导。

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

Answer 1

您仅返回卷积的单个值(第 n 个值)，而不是完整数组。使用 FFT，您始终计算所有值，而在您的转换函数中，您只计算您想要的值。就复杂性而言，FFT 是 O(N*log(N))，而您的 conv 实现是 O(N)。如果您要实现一个返回完整卷积的朴素转换函数，那么它将是 O(N^2)。 因此，如果您想要完整的卷积数组，最好的选择是 FFT 方法。如果您只想要第 n:th 值，那么您的方法在复杂性方面是最好的。