我知道一般来说FFT and multiplication通常比直接convolve操作要快，当数组比较大的时候。但是，我将一个非常长的信号（比如 1000 万点）与非常短的响应（比如 1000 点）进行卷积。在这种情况下，这fftconvolve似乎没有多大意义，因为它强制第二个数组的 FFT 与第一个数组的大小相同。在这种情况下直接进行卷积会更快吗？
问问题
10311 次
3 回答
6
看看我在这里做的比较：
http://scipy-cookbook.readthedocs.io/items/ApplyFIRFilter.html
您的情况可能接近使用普通卷积和使用基于 FFT 的卷积之间的过渡，因此您最好的选择（正如@Dougal 在评论中所建议的那样）是自己计时。
（请注意，在该比较中，我没有进行重叠添加或重叠保存。）
于 2013-02-22T17:06:05.850 回答
4
感谢您的帮助。现在我自己做了测试，我用 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
差别只会越来越大。
于 2013-03-05T06:36:10.110 回答
3
通过重叠添加或重叠保存算法的 FFT 快速卷积可以通过使用仅比脉冲响应大一小倍（例如 2X）的 FFT 在有限的内存中完成。它将长 FFT 分解为适当重叠的较短但零填充的 FFT。
即使有重叠开销，对于足够大的 N 和 M，O(NlogN) 的效率也会超过 M*N。
于 2013-02-22T08:46:40.117 回答