Python的SciPy的卷积VS fftconvolve

我知道一般来说FFT and multiplication通常比直接convolve运行速度更快，当阵列是比较大的。但是，我正在用非常短的响应（比如说1千分）来解释一个很长的信号（比如说1000万分）。在这种情况下，fftconvolve似乎并没有太大的意义，因为它迫使第二阵列的第一阵列的同样大小的FFT。在这种情况下直接进行卷积会更快吗？Python的SciPy的卷积VS fftconvolve

来源

2013-02-22 LWZ

是否有一个原因，你不能只是时间两种方法，例如用'timeit'？ – Dougal 2013-02-22 06:57:19

我不知道这个功能。我会尽力。我也想知道底层理论。 – LWZ 2013-02-22 07:22:57

FFT通过快速卷积重叠相加或重叠保存通过使用比所述脉冲响应较大的FFT，这只是一个小的多（例如2X）算法可以在有限的存储器来完成。它将长的FFT分解成适当重叠的较短但零填充的FFT。

即使有重叠的开销，O（NlogN）将击败M * N的足够大的N和M.

来源

2013-02-22 08:46:40 hotpaw2

感谢您的回答！你的意思是即使使用'fftconvolve'函数，它会自动将长FFT分解为短FFT，我不需要担心它？ – LWZ 2013-02-22 08:56:04

@LWZ：SciPy的的fftconvolve没有做到这一点，没有。 hotpaw，你有这个方法的参考/实现吗？ – endolith 2013-08-13 18:06:52

效率看一看比较我在这里：

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

你的情况可能是使用一个普通的卷积，并使用基于FFT的卷积之间的过渡附近，所以最好的办法（如通过@Dougal在评论所说）是自己的时间了。

（请注意，我没有做重叠相加或在比较重叠保留。）

来源

2013-02-22 17:06:05

该链接似乎并没有指向你的意思（尽管我可以在页面中找到它） – luca 2016-07-12 12:34:33

@luca谢谢。该页面最初是在旧的scipy wiki上，现在已经消失了。我更新了链接。 – 2016-07-12 14:25:55

感谢你的帮助。现在我做了测试我自己，我做了卷积2个阵列，2^20和2^4的大小，这就是结果：

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

所以我们有一个赢家，numpy的卷积是远快于其他。我仍然不知道为什么。

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

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

差异只是变大。

来源

2013-03-05 06:36:10 LWZ

Python的SciPy的卷积VS fftconvolve

回答

相关问题