Short Length Convolution Speed Up

9 次查看（过去 30 天）
Alexander Voznesensky
编辑： Alexander Voznesensky 2022-1-24
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 个评论
显示 6更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

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.

类别

在 Help Center 和 File Exchange 中查找有关 Correlation and Convolution 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by