# What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand transforms like it ( and yes I know of the area Fourier analysis, just not if anything about it) I've read a little of the FFT wikipedia article and some on DFT etc. But I'm not even sure I understand them enough. and yes I know it's not for simpletons like me.

• You can understand the discrete Fourier transform (and the FFT algorithm) using only linear algebra. I gave a short explanation of the DFT here: math.stackexchange.com/a/1944778/40119 – littleO Jul 27 '17 at 23:34
• The algorithm itself, at its core, is just a straightforward divide-and-conquer algorithm: if you have a vector $x$ of length $2^n$; divide it into the two vectors of length $2^{n-1}$ consisting of the even-index and the odd-index elements; and calculate the Fourier transforms of these two vectors recursively - then a small amount of mathematics allows you to express the Fourier transform of the original vector in terms of the Fourier transforms of the smaller vectors. – Daniel Schepler Jul 27 '17 at 23:41
• so is karatsuba in theory but I guess I'm just too stupid right now. – user451844 Jul 28 '17 at 11:28

First let me begin with a simple explanation of the fourier transform. It takes a signal from the time-domain to the frequency domain. This means that instead of seeing a sine wave we see a point on a graph. And because any real signal can be described as the sum of sines, we get many points, that if connected form a line graph in the frequency plot.

The Fast fourier transform is a mathematical trick that significantly reduces the time it takes to do a fourier transform significantly. FFT algorithms require that you have samples in powers of 2, because they all divide the problem into tiny parts. The small parts are faster to calculate (here the discrete fourier transform formula is used), and the final result is combined from all the small ones. So instead of doing 1 DFT of size 4096, it can do 256 DFTs of size 16.

The mathematical explanation is pretty advanced, check out the Cooley Tukey algorithm.