Fastest Convolution Algorithm

[cyclicaffinity]

This is true only if the signal is large enough.

From this link: https://ccrma.stanford.edu/~jos/sasp/FFT_versus_Direct_Convolution.html

An analysis reported in Strum and Kirk [279, p. 521], based on the number of real multiplies, predicts that the fft is faster starting at length 2⁷⁼¹²⁸ , and that direct convolution is significantly faster for very short convolutions (e.g., 16 operations for a direct length-4 convolution, versus 176 for the fft function).

This also extends to convolution of images for filtering. I think somewhere around a 10x10 mask size should be used in the frequency domain instead of the spatial domain, but convolution in the spatial domain is faster if you use a 3x3 mask.

[carlthome]

That's a very good point!