Short Length Convolution Speed Up

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?

[Matt J]

So the gain is for M>log2N. In my case M>18.

Don't you mean M<log2N and M<18?

[Alexander Voznesensky]

Then fftfilt is slower, than filter. See the plot.

[Matt J]

Is it the filter impulse response kernel that is of length 15, or the number of filter coefficients?

[Alexander Voznesensky]

It is number of filter coefficients.

[Alexander Voznesensky]

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]

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]

Conv is almost the same ...

Answer 1

[Matt J]

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]

Yes, that's the problem. In my notation M>log2N.

Answer 2

[Matt J]

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