Convolution with FFT, how does this work?

Question

I know that in time domain convolution is a pretty expensive operation between two matrices and you can perform it in frequency domain by transforming them in the complex plane and use multiplication (and then back in the time domain)

Anyway I don't understand how this is performed in the CUDA SDK where the data and the kernel are padded and put into two buffers (m_PaddedKernel and m_PaddedData), this should be to accelerate Cooley-Tuckey method, then the function cufftExecC2C is called to transform first the Kernel (and why C2C? complex-to-complex, why not real-to-complex?) into the complex plane and then the entire data into the same plane

The defined kernel spProcess2D_kernel then kicks in and seems like normalize and executes the multiplication between data and kernel in the frequency domain (how to do the multiplication of two functions? I think they mean composing the two functions) and back with the C2C transformation (still wondering why C2C and not C2R)

Answer 1

As to why this can be done with the FFT, you need to read about the convolution theorem.

In general, your input data may be complex. So that is why C2C is used.