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?
  8 Comments

Sign in to comment.

Accepted Answer

Matt J
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.
  1 Comment
Alexander Voznesensky
Alexander Voznesensky on 24 Jan 2022
Yes, that's the problem. In my notation M>log2N.

Sign in to comment.

More Answers (1)

Matt J
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by