## 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.

Related programs:
FFTXlib ·
Related disciplines: