Python SciPy convolve vs fftconvolve

Question

I know generally speaking FFT and multiplication is usually faster than direct convolve operation, when the array is relatively large. However, I'm convolving a very long signal (say 10 million points) with a very short response (say 1 thousand points). In this case the fftconvolve doesn't seem to make much sense, since it forces a FFT of the second array to the same size of the first array. Is it faster to just do direct convolve in this case?

Answer 1

Take a look at the comparison I did here:

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

Your case might be near the transition between using a plain convolution and using the FFT-based convolution, so your best bet (as suggested by @Dougal in a comment) is to time it yourself.

(Note that I didn't do overlap-add or overlap-save in that comparison.)

Answer 2

thank you for your help. Now I did the test myself, I did convolution with 2 arrays, size of 2^20 and 2^4, and this is the result:

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

So we have a winner, numpy convolve is is much faster than the others. I still don't know why though.

---

Now I tried 2 longer arrays, size of 2^22 and 2^10. The result is:

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

The difference just gets bigger.