%% This LaTeX-file was created by <jl> Mon Apr 13 10:53:06 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 24 4/13/98 ``You get me confused. You get me to say something and then I
get nervous.''


\section{Fast Fourier Transforms (FFT)}


\subsection{motivation}

Given a function there are several representations.

\begin{itemize}
\item polynomial: \( f(x)=a_{0}+a_{1}x+...a_{n-1}x^{n-1} \)
\item point set: \( (0,f(0)),(1,f(1)),(2,f(2)),...(n-1),f(n-1)) \)
\end{itemize}
The point set representation (with redundant sets) is used to transmit information
in about a polynomial over a noisy channel. This message is decoded using a
big matrix.

\( \begin{array}{ccccc}
1 & 0 & ... & ... & 0\\
1 & 2 & 2^{2} & ... & 2^{n-1}\\
. & . &  &  & \\
. & . &  &  & \\
1 & cn & (cn)^{2} & ... & (cn)^{n-1}
\end{array} \)\( * \)\( \begin{array}{c}
a_{0}\\
.\\
.\\
.\\
a_{n-1}
\end{array} \)\( =\begin{array}{c}
f(0)\\
f(2)\\
.\\
.\\
f(cn)
\end{array} \)

This is \( O(n^{3}) \) to solve, or perhaps \( O(n^{2.36}) \) if you are clever. 

There is a case (the FFT case) which is quickly solvable.


\subsection{vector convolution}

The convolution of two vectors \( (a_{0},...,a_{n-1})\otimes (h_{0},...,h_{n-1})=(c_{0},...,c_{2n-2}) \) is defined by \( c_{k}=\sum _{i=0}^{k}a_{i}b_{k-i} \)


\subsection{algorithm}

Compute \( f(x) \) at \( f(0),f(1),...,f(2n-2) \) and \( g(x) \) at \( g(0),...,g(2n-2) \). Then, we calculate \( f(0)g(0),...,f(2n-2)g(2n-2) \) to get \( f(x)g(x)=c_{0}+c_{1}x+...c_{2n-2}x^{2n-2} \). This doesn't look
like it works except that by shifting to the complex plane, everything can be
made cheap.


\subsection{definitions}

\( \omega  \) = primitive nth root of unity in the complex plane. In orther words \( \omega =e^{i2\pi \frac{j}{n}} \) where
\( j\neq n \).

Conditions:

\begin{itemize}
\item \( \omega \neq 1 \) 
\item \( \omega ^{p}\neq 1 \) with \( 1\leq p\leq n-1 \)
\item \( \omega ^{n}=1 \)
\item \( \sum _{j=0}^{n-1}\omega ^{jp}=0 \) for \( 1\leq p\leq n-1 \)
\end{itemize}
The discrete fourier transform is defined as:

\( \begin{array}{ccccc}
1 & . & . & . & 1\\
. & \omega  & \omega ^{2} & ... & \\
. & \omega ^{2} & \omega ^{4} & ... & \\
. &  &  &  & \\
1 & . & . & . & \omega 
\end{array}* \)\( \begin{array}{c}
a_{0}\\
.\\
.\\
.\\
a_{n}
\end{array}= \) \( \begin{array}{c}
f(\omega ^{0})\\
.\\
.\\
.\\
f(\omega ^{n-1})
\end{array} \)

We can express the matrix as DFT transform matrix as \( F_{ij}=w^{ij} \)


\subsection{lemma}

\( (F^{-1})_{ij}=\frac{1}{n}\omega ^{-ij} \)

Proof:

multiply \( (F^{-1})_{ij}F_{jk} \) using the property \( w^{n}=1 \) and \( \sum _{j=0}^{n-1}\omega ^{jp}=0 \) for \( 1\leq p\leq n-1 \).


\subsection{FFT}

Let \( D_{\frac{n}{2}}=\begin{array}{ccccc}
1 &  &  &  & \\
 & \omega  &  &  & \\
 &  & \omega ^{2} &  & \\
 &  &  & \ddots  & \\
 &  &  &  & -1
\end{array} \) Then \( F_{n}V=\begin{array}{cc}
F_{\frac{n}{2}} & D_{\frac{n}{2}}F_{\frac{n}{2}}\\
F_{\frac{n}{2}} & -D_{\frac{n}{2}}F_{\frac{n}{2}}
\end{array}*\begin{array}{c}
V_{even}\\
V_{odd}
\end{array} \)

This suggest the divide and conquer algorithm:

compute \( F_{\frac{n}{2}}V_{even} \) and \( D_{\frac{n}{2}}F_{\frac{n}{2}}V_{odd} \), then construct \( F_{n}V \) and return.


\subsubsection{timing}

\( T(n)=2*T(\frac{n}{2})+\frac{3}{2}n \) which means \( T(n)=O(n\log n \))


\subsection{FFT in parallel}

The FFT algorithm is parallelizable. Arrange the nodes of the parallel processor
on a hypercube. Each node has a particular value associated with it. Have the
node look at its first (bitwise ordering) neighbor. These 2 nodes will have
values \( a \) and \( b \). Give one node \( a+b \) and the other \( a-b \). Repeat for each bit.


\section{Shuffle exchange graph}

let \( V=\{(a_{0},...,a_{n})|a_{i}=\{0,1\}\} \)

then the 'shuffle' takes \( (a_{0},...,a_{n})\rightarrow (a_{1},...,a_{n}a_{0}) \)

and the 'exchange' takes \( (a_{0},...,a_{n})=(ba_{1},...,a_{n}) \)

\end{document}