MATH 414 Lecture 25

« previous | Friday, March 21, 2014 | next »

Fast Fourier Transform

Developed by Cooley (CS) and Tukey (STAT/MATH) ca. 1965 at Bell Labs.

Discrete Fourier Transform involves multiplication of an $n\times n$ matrix, around $4n^2$ real multiplications.

DFT for powers of $2$: $n=2^L$ for $L\in {\mathbb{\mathbb{Z}}}^{+}$. (In practice, we have $n=2N$, where $N=2^{L-1}$).

$\begin{array}{rl}{{ℱ}}_{2N}[y_0,\dots ,y_{2N-1}]& =\sum _{j=0}^{2N-1}{y}_j\stackrel{jk}{\bar{\omega }}\\ & =\sum _{\text{even}j}{y}_j\stackrel{jk}{\bar{\omega }}+\sum _{\text{odd}j}{y}_j\stackrel{jk}{\bar{\omega }}\\ & =\sum _{\ell =0}^{N_1}{y}_{2\ell }\stackrel{2\ell k}{\bar{\omega }}+\sum _{\ell =0}^{N-1}{y}_{2\ell +1}\stackrel{(2\ell +1)k}{\bar{\omega }}\end{array}$

In the even case,

$\begin{array}{rl}\stackrel{2\ell k}{\bar{\omega }}& ={\mathrm{e}}^{-\frac{2\pi i}{n}\cdot 2\ell k}\\ & ={\mathrm{e}}^{-\frac{2\pi i}{2N}\cdot 2\ell k}\\ & ={\mathrm{e}}^{-\frac{2\pi i}{N}\ell k}\end{array}$

Let $W={\mathrm{e}}^{\frac{2\pi i}{N}}$. Then

$\begin{array}{rl}{\mathrm{e}}^{-\frac{2\pi i}{2N}\cdot 2\ell k}& =\stackrel{\ell k}{\bar{W}}\end{array}$

In the odd case,

$\begin{array}{rl}\stackrel{(2\ell +1)k}{\bar{\omega }}& =\stackrel{k}{\stackrel{‾}{\omega }}\stackrel{2\ell k}{\bar{\omega }}\\ & =\stackrel{k}{\stackrel{‾}{\omega }}\stackrel{\ell k}{\bar{W}}\end{array}$

Hence

${{ℱ}}_{2N}{[y_0,\dots ,y_{2N-1}]}_k={{ℱ}}_N[y_0,y_2,y_4,\dots ,y_{2N-2}]+\stackrel{k}{\stackrel{‾}{\omega }}{{ℱ}}_N[y_1,y_3,y_5,\dots ,y_{2N-1}]$

Complexity Analysis

Suppose that it takes $K_L$ recursive levels to compute $F_{2^L}$, where $L=\log [2]n$

We get a recurrence relation

$K_L=2K_{L-1}+2^{L-1}$

Where $K\sim L{2}^L\in O(n\log n)$