# Contents

## Idea

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.

## Details

### Definition

Let $(x)_{l=0, ..., N-1}$ be a given finite time series of real numbers.

The FFT is about the calculation of

$X_r := \sum_{l = 0}^{N -1} x_l \; \omega^{r l}$

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

### Divide and Conquer

The FFT algorithms are examples of divide and conquer algorithms.

### Decimation in Time, Radix 2

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:

$X_r = \sum_{l = 0}^{\frac{N}{2} -1} x_{2l} \; \omega^{2 r l} + \omega_N^r \sum_{l = 0}^{\frac{N}{2} -1} x_{2l+1} \; \omega^{2 r l}$

Using $\omega_{\frac{N}{2}} = \omega_N^2$ we can rewrite this sum as:

$X_r = \sum_{l = 0}^{\frac{N}{2} -1} x_{2l} \; \omega_{\frac{N}{2}}^{r l} + \omega_N^r \sum_{l = 0}^{\frac{N}{2} -1} x_{2l+1} \; \omega_\frac{N}{2}^{r l}$

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.

## References

### General

Two free online books:

• C. Sidney Burrus: Fast Fourier Transforms (online version)

• Douglas L. Jones: The DFT, FFT, and Practical Spectral Analysis (online version)

### Implementations

#### Fastest Fourier Transform of the West

One of the most well known implementations is the FFTW (fastest Fourier Transform 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:

• Steven G. Johnson, Matteo Frigo: Implementing FFTs in Practice (online)

For an installation on Windows and linking to it from a Visual C++ 2010 Express Installation (VC) as of January 2012, note the following: