Short Length Convolution Speed Up

2 次查看(过去 30 天)
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 个评论

请先登录,再进行评论。

采纳的回答

Matt J
Matt J 2022-1-23
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 个)

Matt J
Matt J 2022-1-23
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