ARTICLES

# FFT

By **
adam
**

## polynomials

\[ f(x) = A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1} \]

## roots

\begin{eqnarray}
x^{n} &=& 1 \\\

x &=& e^{i \frac{2\pi}{n}}
\end{eqnarray}

Call \(e^{i \frac{2\pi}{n}} = w_n\) the fundamental, then there are \(n\) such roots, \(w_n^k\) for \(k = 0,\cdots,n-1\).

The fourier transform is a vector of the polynomial evaluated at each of the \(k\) roots.

\[ F(k) = f(w_n^k) \]

The FFT is a divide and conquer algorithm where instead of doing \(O(n)\) computations for each fourier coefficient \(F(k)\), we break up the problem into 2 subproblems of size \(n/2\) and do a merge which is of order \(n\). Thus \(T(n) = 2T(n/2) + O(n)\)

Consider taking the FT of the even powers f(x):

\[ f_e(x) = A_0 + A_2 x + \cdots \]

It’s FT will look like

\[ F_e(k) = f_e(w_{n/2}^k) = f_e(w_n^{2k}) \]

for \(k = 0, \cdots, n/2-1\).

Combining both the odd and even contributions we get

\begin{eqnarray}
F(k) &=& f(x=w_n^k) \\\

&=& f_e(x^2) + x f_o(x^2) \\\

&=& f_e(w_n^{2k}) + w_n^k f_o(w_n^{2k})
\end{eqnarray}

Note for \(k = 0, \cdots, n/2 -1\), this is well defined by \(F_e(k)\) and \(F_o(k)\):

\begin{eqnarray*}
F(k) = F_e(k) + w_n^k F_o(k)\\\

\text{ for } k \in [0,n/2-1]
\end{eqnarray*}

We need to take care of \(k = n/2, \cdots, n-1\).

Rewriting \(k = n/2, \cdots, n-1\) as \(k = n/2 + (0, \cdots, n/2-1)\). \(k = n/2 + k’\). We can rewrite:

\[ w_n^{n+2k’} = w_n^{2k’} \]

and

\[ w_n^k = w_n^{n/2+k’} = -w_n^{k’} \]

Thus we can write

\begin{eqnarray}
F(n/2+k’) &=& f_e(w_n^{2k’} - w_n^{k’} f_o(w_n^{2k’}) \\\

&=& F_e(k’) - w_n^{k’} F_o(k’)
\end{eqnarray}