Quick Convolution
While the "conv" function of the SP Toolbox is very efficient when one of the two signals being linearly convolved is small in length, the convolution can be computed much faster with the FFT when the signals are large. However, it is often even more efficient to choose a "smart" FFT size (namely, one that has only small primes as its prime factors) to reduce the overhead cost. While the simplest approach is often to take the next power of 2, there can still be considerable gains by allowing the FFT length to be a product of any primes up to "p." Qconv provides this functionality by calling the included cfft.m instead of fft.m.
As an additional note, it seems that p = 5 tends to be a good choice for efficiency.
Here is an example usage from my machine that shows the potential benefit:
>> N1 = 463902; N2 = 123456;
>> X = randn(N1, 1); Y = randn(N2, 1);
>> tic; Xc = qconv(X,Y); toc %-- FFT length is N1 + N2 - 1
Elapsed time is 1.074133 seconds.
>> tic; Xc2 = qconv(X,Y,5); toc %-- choose more optimal FFT size, max prime = 5
Elapsed time is 0.330343 seconds.
Cite As
Chris Turnes (2024). Quick Convolution (https://www.mathworks.com/matlabcentral/fileexchange/42561-quick-convolution), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.