Python SciPy卷积与fftconvolve

Question

我知道一般来说,当阵列比较大时,FFT and multiplication通常比直接convolve操作更快.然而,我正在卷入一个非常长的信号(比如1000万点),响应非常短(比如1000点).在这种情况下,fftconvolve似乎没有多大意义,因为它迫使第二阵列的FFT与第一阵列的大小相同.在这种情况下直接卷积是否更快？

Answer 1

看看我在这里做的比较:

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

您的情况可能接近使用简单卷积和使用基于FFT的卷积之间的过渡,因此您最好的选择(正如@Dougal在评论中所建议的)是自己计时.

(请注意,我没有在该比较中进行重叠添加或重叠保存.)

Answer 2

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

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

所以我们有一个胜利者，numpy convolve 比其他的快得多。但我还是不知道为什么。

现在我尝试了 2 个更长的数组，大小分别为 2^22 和 2^10。结果是：

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

差别只会越来越大。

Answer 3

通过重叠相加或重叠保存算法的 FFT 快速卷积可以通过使用仅比脉冲响应大一小倍（例如 2 倍）的 FFT 在有限的内存中完成。它将长 FFT 分解为适当重叠的较短但零填充的 FFT。

即使存在重叠开销，对于足够大的 N 和 M，O(NlogN) 的效率也将击败 M*N。