# Short Length Convolution Speed Up

3 views (last 30 days)
Hi! I need to perform a short-length convolution. The signal length is N=2^18=262144, and the filter length is M=1...64. The most interesting filter length is M=15. The basic solution is to use the filter function. To increase the speed, I use fftfilt, but it is more efficient for long sequences. I need to get a gain in speed compared to the filter function with N=262144 and M=15. What is possible to do in this case?
Сonvolution complexity is M*N, FFT - Nlog2N. So the gain is for M>log2N. In my case M>18. But I have M between 256 and 512. Why? Alexander Voznesensky on 23 Jan 2022
Conv is almost the same ...

Matt J on 23 Jan 2022
From the documentation, it appears that the faster performance of fftfilt is indeed expected:
When the input signal is relatively large, fftfilt is faster than filter.
filter performs N multiplications for each sample in x, where N is the filter length. fftfilt performs 2 FFT operations — the FFT of the signal block of length L plus the inverse FT of the product of the FFTs — at the cost of 12Llog2L where L is the block length. It then performs L point-wise multiplications for a total cost of L+Llog2L=L(1+log2L) multiplications. The cost ratio is therefore L(1+log2L)/(NL)=(1+log2L)/N which is approximately log2L / N.
Therefore, fftfilt is faster when log2L is less than N.
Alexander Voznesensky on 24 Jan 2022
Yes, that's the problem. In my notation M>log2N.

Matt J on 23 Jan 2022
Do you have the Parallel Computing Toolbox and a decently powerful GPU? If so, filter() is enabled for gpuArrays.