Why does FFT accelerate the calculation involved i

Question

I am seeing a lot of literature in which they say that by using the fft one can reach a faster convolution. I know that one needs to get fft and and then ifft from the results, but I really do not understand why using the fft can make the convolution faster?

Answer 1

FFT speeds up convolution for large enough filters, because convolution requires N multiplications (and N-1) additions for each output sample and conversely (2)N^2 operations for a block of N samples.

Taking account, that one has to double the block size for FFT processing by adding zeroes, each block requires (2)*(2N)*log(2N) operations to perform FFT, 2N operations to multiply and again 4N*log(2N) operations to perform inverse FFT, there is a break even point, where 8Nlog2N <= 2N^2.

The fundamental reasons are:

1) a discrete time-domain signal can be represented as a sum of frequencies.
2) convolution in time domain (O(N^2)) equals multiplication of frequencies in frequency domain (O(N)) 3) the transformation is invertible
4) there exists a method to convert a signal from time domain to frequency domain in less than N^2 operations (that's the first F in 'Fast Fourier Transform').

The straight forward FT is O(N^2), where each Frequency domain element F(i) = Sigma f(i) * exp(i*pi/N).

However the FFT is based on an observation that exp(i*pi/N) has certain symmetries, allowing the calculation to be split in odd/even vectors. The even vectors can be calculated at the expense of O(N) while the odd vectors require a full FT of half the size. As this can be repeated until N=2, the overall complexity will be (proportional to) Nlog(N).