CODEWITHSUNDEEP
pythonscipyfftconvolution
LWZ
LWZ

Reputation: 12338

Python SciPy convolve vs fftconvolve

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?

Upvotes: 12

Views: 16280

Answers (3)

Warren Weckesser
Warren Weckesser

Reputation: 114831

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.)

Upvotes: 6

LWZ
LWZ

Reputation: 12338

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.

Upvotes: 5

hotpaw2
hotpaw2

Reputation: 70693

FFT fast convolution via the overlap-add or overlap save algorithms can be done in limited memory by using an FFT that is only a small multiple (such as 2X) larger than the impulse response. It breaks the long FFT up into properly overlapped shorter but zero-padded FFTs.

Even with the overlap overhead, O(NlogN) will beat M*N in efficiency for large enough N and M.

Upvotes: 4

Related Questions