1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{amssymb}
  7\usepackage{enumerate}
  8\usepackage{hyperref}
  9\hypersetup{
 10    colorlinks,
 11    citecolor=black,
 12    filecolor=black,
 13    linkcolor=black,
 14    urlcolor=blue
 15}
 16
 17\theoremstyle{definition}
 18\newtheorem{definition}{Def}[section]
 19\newtheorem{theorem}[definition]{Thm}
 20\newtheorem{innersolution}{}
 21\newenvironment{solution}[1]
 22{\renewcommand\theinnersolution{#1}\innersolution}
 23{\endinnersolution}
 24
 25
 26\title{FFT: Fast Fourier Transform}
 27\author{arnaucube}
 28\date{August 2022}
 29
 30\begin{document}
 31
 32\maketitle
 33
 34\begin{abstract}
 35  Usually while reading papers and books I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 36
 37  The notes are not complete, don't include all the steps neither all the proofs. I use these notes to revisit the concepts after some time of reading the topic.
 38
 39  This document are notes done while reading about the topic from \cite{gstrang}, \cite{tpornin}, \cite{rfateman}.
 40\end{abstract}
 41
 42\tableofcontents
 43
 44\section{Discrete \& Fast Fourier Transform}
 45
 46\subsection{Discrete Fourier Transform (DFT)}
 47
 48Continuous:
 49
 50$$
 51x(f) = \int_{-\infty}^{\infty} x(t) e^{-2 \pi f t} dt
 52$$
 53
 54Discrete:
 55The $k^{th}$ frequency, evaluating at $n$ of $N$ samples.
 56$$
 57\hat{f_k} = \sum_{n=0}^{n-1} f_n e^{\frac{-j \pi kn}{N}}
 58$$
 59
 60where we can group under $b_n = \frac{\pi kn}{N}$. The previous expression can be expanded into:
 61$$
 62x_k = x_0 e^{-b_0 j} + x_1 e^{-b_1 j} + ... + x_n e^{-b_n j}
 63$$
 64
 65By the \emph{Euler's formula} we have $e^{jx} = cos(x) + j\cdot sin(x)$, and using it in the previous $x_k$, we obtain
 66
 67$$
 68x_k = x_0 [cos(-b_0) + j \cdot sin(-b_0)] + \ldots
 69$$
 70
 71Using $\hat{f_k}$ we obtained
 72$$
 73\{f_0, f_1, \ldots, f_N\} \xrightarrow{DFT} \{ \hat{f_0}, \hat{f_1}, \ldots, \hat{f_N} \}
 74$$
 75
 76To reverse the $\hat{f_k}$ back to $f_k$:
 77$$
 78f_k = \left( \sum_{n=0}^{n-1} \hat{f_n} e^{\frac{-j \pi kn}{N}} \right) \cdot \frac{1}{N}
 79$$
 80
 81
 82$$
 83DFT =
 84\begin{pmatrix}
 85\hat{f_0}\\
 86\hat{f_1}\\
 87\hat{f_2}\\
 88\vdots\\
 89\hat{f_n}\\
 90\end{pmatrix}=
 91\begin{pmatrix}
 921 & 1 & 1 & \ldots & 1 \\
 931 & w_n & w_n^2 & \ldots & w_n^{N-1} \\
 941 & w_n^2 & w_n^4 & \ldots & w_n^{2(N-1)} \\
 95\vdots & \vdots & \vdots & & \vdots\\
 961 & w_n^{n-1} & w_n^{2(n-1)} & \ldots & w_n^{(N-1)^2} \\
 97\end{pmatrix}
 98\begin{pmatrix}
 99f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_n
100\end{pmatrix}
101$$
102
103\subsection{Fast Fourier Transform (FFT)}
104While DFT is $O(n)$, FFT is $O(n \space log(n))$
105
106Here you can find a simple implementation of the these concepts in Rust: \href{https://github.com/arnaucube/fft-rs}{arnaucube/fft-rs} \cite{fftrs}
107
108
109\section{FFT over finite fields, roots of unity, and polynomial multiplication}
110
111FFT is very useful when working with polynomials. [TODO poly multiplication]
112
113An implementation of the FFT over finite fields using the Vandermonde matrix approach can be found at \cite{fftsage}.
114
115\subsection{Intro}
116Let $A(x)$ be a polynomial of degree $n-1$,
117
118$$
119A(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \cdots + a_{n-1} \cdot x^{n-1} = \sum_{i=0}^{n-1} a_i \cdot x^i
120$$
121
122We can represent $A(x)$ in its evaluation form,
123
124$$
125(x_0, A(x_0)), (x_1, A(x_1)), \cdots, (x_{n-1}, A(x_{n-1})) = (x_i, A(x_i))
126$$
127
128
129We can evaluate A(x) at n given points $(x_0, x_1, ..., x_{n-1}$):
130
131$$
132\begin{pmatrix}
133A(x_0)\\ A(x_1)\\ A(x_2)\\ \vdots\\ A(x_{n-1})
134\end{pmatrix}=
135\begin{pmatrix}
136x_0^0 & x_0^1 & x_0^2 & \ldots & x_0^{n-1} \\
137x_1^0 & x_1^1 & x_1^2 & \ldots & x_1^{n-1} \\
138x_2^0 & x_2^1 & x_2^2 & \ldots & x_2^{n-1} \\
139\vdots & \vdots & \vdots & & \vdots\\
140x_{n-1}^0 & x_{n-1}^1 & x_{n-1}^2 & \ldots & x_{n-1}^{n-1} \\
141\end{pmatrix}
142\begin{pmatrix}
143a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1}
144\end{pmatrix}
145$$
146
147This is known by the Vandermonde matrix.
148
149But this will not be too efficient. Instead of random $x_i$ values, we use \emph{roots of unity}, where $\omega_n^n = 1$. We denote $\omega$ as a primitive $n^{th}$ root of unity:
150
151$$
152\begin{pmatrix}
153A(1)\\ A(\omega)\\ A(\omega^2)\\ \vdots\\ A(\omega^{n-1})
154\end{pmatrix}=
155\begin{pmatrix}
1561 & 1 & 1 & \ldots & 1 \\
1571 & \omega & \omega^2 & \ldots & \omega^{n-1} \\
1581 & \omega^2 & \omega^4 & \ldots & \omega^{2(n-1)} \\
159\vdots & \vdots & \vdots & & \vdots\\
1601 & \omega^{n-1} & \omega^{2(n-1)} & \ldots & \omega^{(n-1)^2} \\
161\end{pmatrix}
162\begin{pmatrix}
163a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1}
164\end{pmatrix}
165$$
166
167Which we can see as
168
169$$
170\hat{A} = F_n \cdot A
171$$
172
173This matches our system of equations:
174
175\begin{itemize}
176  \item at $x=0$, $a_0 + a_1 + \cdots + a_{n-1} = A_0 = A(1)$
177  \item at $x=1$, $a_0 \cdot 1 + a_1 \cdot \omega + a_2 \cdot \omega^2 + \cdots + a_{n-1} \cdot \omega^{n-1} = A_1 = A(\omega)$
178  \item at $x=2$, $a_0 \cdot 1 + a_1 \cdot \omega^2 + a_2 \cdot \omega^4 + \cdots + a_{n-1} \cdot \omega^{2(n-1)} = A_2 = A(\omega^2)$
179  \item $\cdots$
180  \item at $x=n-1$, $a_0 \cdot 1 + a_1 \cdot \omega^{n-1} + a_2 \cdot \omega^{2(n-1)} + \cdots + a_{n-1} \cdot \omega^{(n-1)(n-1)} = A_2 = A(\omega^{n-1})$
181\end{itemize}
182
183We denote the $F_n$ as the Fourier matrix, with $j$ rows and $k$ columns, where each entry can be expressed as $F_{jk} = \omega^{jk}$.
184
185To find the $a_i$ values, we use the inverted $F_n = F_n^{-1}$
186
187\subsection{Roots of unity}
188todo
189
190\subsection{FFT over finite fields}
191todo
192
193\subsection{Polynomial multiplication with FFT}
194todo
195
196
197\bibliography{fft-notes.bib}
198\bibliographystyle{unsrt}
199
200\end{document}