Python SciPy中的convolve与fftconvolve比较

Question

我知道通常情况下，当数组比较大时，FFT和乘法通常比直接的卷积操作更快。然而，在这种情况下，我需要对一个非常长的信号（比如说1000万个点）进行与非常短的响应（比如说1000个点）的卷积。在这种情况下，fftconvolve似乎并没有太多意义，因为它会强制将第二个数组的FFT大小调整为与第一个数组相同的大小。在这种情况下，直接进行卷积是否更快呢？

- LWZ

---

你为什么不能用 timeit 计时两种方法，有什么原因吗？ - Danica

我不知道这个函数。我会尝试。但我也想了解其中的基本理论。 - LWZ

注意：从v0.19开始，convolve会根据哪种方法更快的估计自动选择fftconvolve或直接方法。 - Dr Xorile

Answer 1

请看我在这里做的比较：

请查看此处：http://scipy-cookbook.readthedocs.io/items/ApplyFIRFilter.html 您的情况可能接近使用普通卷积和使用基于FFT的卷积之间的转换点，因此您最好（如@Dougal在评论中建议的那样）亲自测试时间。

（请注意，我在该比较中没有执行重叠添加或重叠保存。）

- Warren Weckesser

---

链接似乎没有指向你所想要的内容（尽管我仍然可以在页面中找到它）。 - luca

@luca 谢谢。那个页面最初在旧的scipy wiki上，现在已经不存在了。我已经更新了链接。 - Warren Weckesser

Answer 2

感谢您的帮助。现在我已经亲自进行了测试，使用两个大小分别为2^20和2^4的数组进行卷积计算，以下是结果：

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

我们有了胜者，numpy convolve比其他方法快得多。不过我仍然不知道为什么。

---

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

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

差距只会越来越大。

- LWZ

---

感谢您的反馈。也许与此相关：（https://github.com/scipy/scipy/issues/8154）。 - mins

Answer 3

通过使用仅比脉冲响应大几倍（如2X）的FFT，可以通过重叠添加或重叠保存算法进行FFT快速卷积。它将长FFT分成适当重叠的短FFT，但需要进行零填充。

即使考虑到重叠开销，对于足够大的N和M，O(N logN)的效率也会胜过M * N。

- hotpaw2

---

谢谢您的回答！您的意思是即使使用fftconvolve函数，它也会自动将长FFT分解为短FFT，而我无需担心它？ - LWZ

@LWZ: scipy的fftconvolve不会这样做。 hotpaw，你有关于这种方法的参考资料/实现吗？ - endolith