Fast Fourier Transformation

A Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). The algorithm can be applied to both real (\(\mathbb{R}\)) and complex (\(\mathbb{C}\)) input, and can result in both a real or a complex output. This is because it is possible to express an even-length real-input DFT as a complex DFT of half its length. From a mathematical perspective a Discrete Fourier Transform (DFT) transforms a sequence of \(N\) complex numbers from one space to another sequence of complex numbers in the reciprocal space.

It is commonly used in many different practical applications. In signal processing the complex input sequence represent discrete equally spaced samples of a continous signal on the time domain. The DFT transforms these samples into a frequency domain in this case. DFTs are also applied to images where the sequence of samples in this case are values of pixels along a row or column of an image. They can also be used to solve Partial Differential Equations because some PDEs have a simpler form in the reciprocal space.

FFTs can be performed in a multiple dimensions array, usually using the “row-column” algorithm, in which one performs a sequence of one-dimensional FFTs (by any of the algorithms): first you transform along the n1 dimension, then along the n2 dimension, and so on for each dimension. For example, in a two dimension array, this algorithm corresponds to first performing the FFT of all the rows, grouping the resulting transformed rows together as another matrix, and then performing the FFT on each of the columns of this second matrix, and similarly grouping the results into the final result matrix.