Showing changes from revision #8 to #9:
Added | Removed | Changed
The Fast Fourier transform (FFT) denotes a family of algorithms that can be used to calculate the Fourier transform of a time series. The discrete Fourier transform of a finite time series, written as a vector of real numbers $x$, is naiveley a matrix multiplication $M*x$. In principle, the complexity of such an operation would be $O(n^2)$, where $n$ is the number of elements of the time series. FFT algorithms use the very special structure of the Fourier matrix $M$ to achieve a much lower computational cost, namely a complexity of $O(n log n)$.
An FFT algorithm was known to Gauss, but was rediscovered in the mid 20th century and became relevant when computers allowed the calculation of the FFT for large datasets.
Let $(x)_{l=0, ..., N-1}$ be a given finite time series of real numbers.
The FFT is about the calculation of
for $r = 0,..., N-1$ and $\omega := \exp{(\frac{2 i \pi}{N} )}$ being the $N$th root of unity.
For convenience, we note that $\omega_N^{\frac{N}{2}} = -1$ and $\omega_{\frac{N}{2}} = \omega_N^2$.
The FFT algorithms are examples of divide and conquer algorithms.
We assume that the length $N$ of the given time series is a power of 2.
Note that we can rewrite the defining equation of the discrete Fourier transform in the following way:
Using $\omega_{\frac{N}{2}} = \omega_N^2$ we can rewrite this sum as:
This equation represents the FFT as the sum of two FFT of the length $\frac{N}{2}$, the first one involving all the even indexed elements of the time series $x_0, x_2, ...$ and the other one all elements with an odd index, $x_1, x_3$ etc.
Two free online books:
C. Sidney Burrus: Fast Fourier Transforms (online version)
Douglas L. Jones: The DFT, FFT, and Practical Spectral Analysis (online version)
One of the most well known implementations is the FFTW (fastest Fourier Transform of in the West):
The authors explain that an important part of performance optimizing is the use of the multi level caching architecture of modern CPUs, via a combination of automated self-testing (empirically determining which code performs best on the current machine, including implicitly cache effects) and cache-oblivious algorithms. A free online explanation of this concept can be found here:
For an installation on Windows and linking to it from a Visual C++ 2010 Express Installation (VC) as of January 2012, note the following:
download the precompiled DLL from here
open a cmd shell, run vcvars32.bat from the VC\bin folder to set up the necessary environment variables,
execute “lib /def:libfftw3-3.def” using the lib.exe from the VC\bin folder to generate “libfftw3-3.lib”,
in VC, add “libfftw3-3.lib” in VC to your project via project -> properties -> linker -> input -> additional dependencies.