FFT-based convolution

Discrete convolution using FFT method

Description

As opposed to Matlab CONV, CONV2, and CONVN implemented as straight forward sliding sums, CONVNFFT uses Fourier transform (FT) convolution theorem, i.e. FT of the convolution is equal to the product of the FTs of the input functions.

In 1-D, the complexity is O((na+nb)*log(na+nb)), where na/nb are respectively the lengths of A and B.

Optional arguments to control the dimension(s) along which convolution is carried out.

Slightly less accurate than sliding sum convolution.

Good usage recommendation:
        In 1D, this function is faster than CONV for nA, nB > 1000.
        In 2D, this function is faster than CONV2 for nA, nB > 20.
        In 3D, this function is faster than CONVN for nA, nB > 5.

• Acknowledgements: This submission has inspired the following:; conv2fft_reuse
• MATLAB release: MATLAB 7.8 (R2009a)

[Eric]

 

[Alexander]

Awesome function! My code runs 60x faster now (thanks to your GPU support).

[Felipe G. Nievinski]

Well written (IMHO).

[Arun Shamanna]