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]

 

[Romesh]

I think this says it all...

>> tic;C = convn(Vs,Vs);toc;
Elapsed time is 473.103412 seconds.
>> tic;C2 = convnfft(Vs,Vs);toc;
Elapsed time is 1.351315 seconds.
>> max(max(max(abs(C-C2))))
ans =
   5.2208e-15

Thanks so much for this!

[Michael Völker]

Hi Bruno, are you sure your inplaceprod() is (still) useful?

I'm pretty sure, MATLAB does A=A.*B in-place itself. I just compared my memory usage for very large A/B with both methods and there was no difference.
This post is from 2007: http://blogs.mathworks.com/loren/2007/03/22/in-place-operations-on-data/

In a heterogeneous environment, it is useful to avoid mex code for such small tasks. If you are a non-privileged user on a compute server it is really a mess when compiling fails due to compiler version, libraries or whatever.

A minor notice is that (i)fftn is faster than for-loops around 1D (i)fft calls. At least as long as the input and output are of the same size. So I got at least a little speed gain by replacing
    for dim=dims
        A = ifft(A,[],dim);
    end
with
    A = ifftn( A );
for the MATLAB ifft case.

Thank you for the code!

[Bruno Luong]

Hi Michael,
May be the inplace times is no longer necessary for recent Matlab.

I remember implement that from a user request.

Thanks for the useful feedback.

[Edwin]

Moreover, when I checked the result form this code, there are some different between this and convn for two 3d matrix, the 2 input matrix are both positive.
the result from this code has negative values while convn does not.