Python SciPy 卷积与 fftconvolve

Question

我知道一般来说，当数组比较大时，FFT和乘法通常比直接的卷积操作要快。不过，我现在要处理的是一个非常长的信号（比如说有1000万个点），还有一个非常短的响应（比如说有1000个点）。在这种情况下，fftconvolve似乎就没什么意义了，因为它会把第二个数组强制调整到和第一个数组一样大。这样的话，直接进行卷积操作会不会更快呢？

Answer 1

通过重叠相加或重叠保存算法，快速傅里叶变换（FFT）可以在有限的内存中进行卷积。这里的关键是使用一个比脉冲响应稍微大一点的FFT（比如大两倍）。这样可以把长的FFT分成几个适当重叠的短FFT，并在它们的末尾加上零。

即使考虑到重叠带来的额外开销，当N和M足够大的时候，O(NlogN)的效率会比M*N要高。

Answer 2

谢谢你的帮助。现在我自己做了测试，我用两个数组进行了卷积，大小分别是2的20次方和2的4次方，结果是：

numpy.convolve: 110 ms
scipy.signal.convolve: 1.0 s
scipy.signal.fftconvolve: 2.5 s

所以我们有了一个赢家，numpy的卷积速度远快于其他方法。不过我还是不知道为什么。

---

接下来我尝试了两个更长的数组，大小分别是2的22次方和2的10次方。结果是：

numpy.convolve: 6.7 s
scipy.signal.convolve: 221 s
scipy.signal.fftconvolve: MemoryError

差距只会越来越大。

Answer 3

看看我在这里做的比较：

http://scipy-cookbook.readthedocs.io/items/ApplyFIRFilter.html

你的情况可能正好在使用普通卷积和基于FFT的卷积之间的过渡期，所以最好的办法（正如@Dougal在评论中提到的）就是自己来测一下时间。

（注意，我在那个比较中没有使用重叠相加或重叠保存的方法。）