Short Length Convolution Speed Up

2022 1 23
2 个回答
回答已采纳
更新时间：2022 1 24
18 次查看（30 天）

0 个投票

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更早的评论 隐藏 6更早的评论

Matt J
Matt J 2022-1-23
So the gain is for M>log2N. In my case M>18.
Don't you mean M<log2N and M<18?
Then fftfilt is slower, than filter. See the plot.
Matt J
Matt J 2022-1-23
编辑：Matt J 2022-1-23
Is it the filter impulse response kernel that is of length 15, or the number of filter coefficients?
It is number of filter coefficients.
For short lengths, algorithms that require the minimum number of multiplications possible have been developed by Winograd. Is there something similar in matlab?
Matt J
Matt J 2022-1-23
It is not necessarily the number of multiplications that matters. If fftfilt is highly parallelized (it probably is), it can be faster than a non-parallelized routine that has lower computational complexity.
Alexander Voznesensky
编辑：Alexander Voznesensky 2022-1-23
Conv is almost the same ...

请先登录，再进行评论。

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

 采纳的回答

Matt J
Matt J 2022-1-23

0 个投票

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

0 个投票

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

类别

在 帮助中心 和 File Exchange 中查找有关 Signal Modeling 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by