\documentclass[12pt]{article} \usepackage{german,A4,cd} \newcommand{\cdrl}{\cd\rightleftarrows} \newcommand{\cdlr}{\cd\leftrightarrows} \newcommand{\cdr}{\cd\rightarrow} \newcommand{\cdl}{\cd\leftarrow} \newcommand{\cdu}{\cd\uparrow} \newcommand{\cdd}{\cd\downarrow} \newcommand{\cdud}{\cd\updownarrows} \newcommand{\cddu}{\cd\downuparrows} \begin{document} \Large \section{Classical Fourier Transform} \begin{itemize} \item Fourier transform \[ {\cal F}~:~ f(z) \mapsto f^{\wedge}(s) := \int_{- \infty}^{\infty} f(z) \, e^{-2 \pi i s z} dz \] \item inverse Fourier transform \[ {\cal F}_{inv}~:~ f(z) \mapsto f^{\vee}(s) := \int_{- \infty}^{\infty} f(z) \, e^{2 \pi i s z} dz \] \item inversion formula \[ {\cal F}_{inv} ({\cal F} (f))(z) = \left( f^{\wedge} \right)^{\vee}(z) = f(z) \] \item spectral representation \[ f(z) = \int_{- \infty}^{\infty} f^{\wedge}(s) e^{2 \pi i s z} ds \] \item convolution \[ (f \ast g)(z) := \ \int_{- \infty}^{\infty} f(t) \, g(z-t) dt \] \item convolution formula \[ (f \ast g)^{\wedge}(s) = f^{\wedge}(s) \cdot g^{\wedge}(s) \] \[ (f \ast g)(z) = (f^{\wedge} \cdot g^{\wedge})^{\vee}(z) \] \item transformation scheme \[ \CD f,g \cdr{\cal F}{} f^{\wedge},g^{\wedge} \\ \cdd{\ast}{} \cdd{}{\bullet} \\ f*g \cdl{{\cal F}_{inv}}{} f^{\wedge} \cdot g^{\wedge}\\ \hbox{time domain} \cd. \hbox{frequency domain} \endCD \] \end{itemize} \newpage \section{Shannon's Sampling Theorem} \begin{itemize} \item $W$-bandlimited function \[ f(t) = \sum_{k=-W}^{W} F_k \, e^{2 \pi i k t} ~~~(t \in {\bf R}) \] \item identification \[ f(t) ~~\leftrightarrow [F_{-W},F_{-W+1},\ldots,F_W] \] \item reconstruction problem (sampling problem) \begin{quote} can the function $f(t)$ (i.e., the coefficient vector $[F_{-W},F_{-W+1},\ldots,F_W] \in {\bf C}^{2W+1}$) be reconstructed from the knowlegde of $T$ sampling values \[ f(0), f({1 \over T}), f({2 \over T}), \ldots f(1-{1\over T})~~? \] \end{quote} \item representation of the sampling values $\omega_T = e^{2 \pi i / T}$ \[ f\left({\tau \over T}\right) = \sum_{k=-W}^{W} F_k \, (\omega_T)^{\tau k} = \omega_T^{-W \tau} \sum_{k=0}^{2W} F_{k-W} \, \omega_T^{\tau k} \] \item matrix representation \normalsize \[ \pmatrix{ f(0) \cr f(1/T) \cr \vdots \cr f(1-1/T)} = Diag(1,\omega_T^{-W},\omega_T^{-2W}, \ldots,\omega_T^{-(T-1)W}) \pmatrix{ \ddots & & \cr & \omega_T^{\tau k} & \cr & & \ddots}_{{0 \leq \tau < T \atop 0 \leq k \leq 2W}} \pmatrix{ F_{-W} \cr F_{-W+1} \cr \vdots \cr F_W} \] \Large \item sampling theorem \begin{quote} {\em in order to achieve unique reconstruction of the function $f$ the sampling frequency has to be bigger than twice the limit frequency $W$}. \end{quote} \end{itemize} \newpage \section{Representation of Polynomials} \begin{itemize} \item coefficient representation \[ \underbrace{A(X) = \sum_{j=0}^{n-1} a_j \, X^j}_{\in ~k[X]_n} ~~\mapsto ~~ \underbrace{[a_0,a_1, \ldots,a_{n-1}] =: {\bf A}}_{\in ~k^n} \] \item evaluation \[ {\cal L}_{x_0}~:~k[X] \rightarrow k~:~ A(X) \mapsto A(x_0) \] \item Horner's scheme \begin{eqnarray*} A(x_0) &=& \sum_{j=0}^{n-1} a_j \, x_0^j = (1,x_0, \ldots,x_0^{n-1}) \pmatrix{ a_0 \cr a_1 \cr \vdots \cr a_{n-1}} \\ &=& a_0 + x_0\,(a_1+x_0\, ( \ldots +x_0\,(a_{n-2}+x_0\, a_{n-1}) \ldots)) \end{eqnarray*} \item value representation \begin{quote} a polynomial $A(X) \in k[X]_n$ is uniquely determined by the values it takes at $n$ distinct points \end{quote} \item simultaneaous evaluation \begin{eqnarray*} {\cal L}_{x_0,\ldots,x_{n-1}}&~:~& k[X] \rightarrow k^n ~:~\\ A(X) &\mapsto& [{\cal L}_{x_0}(A), \ldots ,{\cal L}_{x_{n-1}}(A)] = [A(x_0),\ldots,A(x_{n-1})] \end{eqnarray*} \item ``modular'' representation \begin{quote} for pairwise distinct $x_0, x_1 , \ldots ,x_{n-1} \in k$ the simultaneouos evaluation \[ {\cal L}_{x_0,\ldots,x_{n-1}}~:~ k[X]_n \rightarrow k^n~:~ A(X) \mapsto [A(x_0),\ldots,A(x_{n-1})] \] is an isomorphism (of rings) \end{quote} \item matrix representation of ${\cal L}_{x_0,\ldots,x_{n-1}}~:~$ \normalsize \[ \pmatrix{ a_0 \cr a_1 \cr \vdots \cr a_{n-1} } \mapsto \underbrace{\pmatrix{ 1 & x_0 & x_0^2 & \ldots & x_0^{n-1} \cr 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \cr \vdots & \vdots & \vdots & \vdots \cr 1 & x_{n-1} & x_{n-1}^2 & \ldots & x_{n-1}^{n-1}}}_{ V(x_0,x_1,\ldots,x_{n-1})} \pmatrix{ a_0 \cr a_1 \cr \vdots \cr a_{n-1} } = \pmatrix{ A(x_0) \cr A(x_1) \cr \vdots \cr A(x_{n-1}) } \] \item \Large {\sc Vandermonde}'s matrix \[ V(x_0,x_1,\ldots,x_{n-1}) = \pmatrix{ 1 & x_0 & x_0^2 & \ldots & x_0^{n-1} \cr 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \cr \vdots & \vdots & \vdots & \vdots \cr 1 & x_{n-1} & x_{n-1}^2 & \ldots & x_{n-1}^{n-1}} \] \item {\sc Vandermonde}'s determinant \[ \det V(x_0,x_1,\ldots,x_{n-1}) = \prod_{i < j} (x_j - x_i) \] \item interpolation \[ A(X) = \sum_{j=0}^{n-1} y_j \, {\prod_{i \neq j} (X - x_i) \over \prod_{i \neq j} (x_j - x_i)} \] \item indicator functions \[ \delta_j(X) := {\prod_{i \neq j} (X - x_i) \over \prod_{i \neq j} (x_j - x_i)}~~~(0 \leq j < n) \] \[ \delta_j(x_i) = \cases{ 1 & if $i=j$ \cr 0 & if $i \neq j$} \] \end{itemize} \newpage \section{Multiplication of Polynomials} \begin{itemize} \item evaluation --- interpolation \begin{enumerate} \item if $A(X), B(X) \in k[X]_n$ have to be multiplied, evaluate both polynomials at $2n$ distinct points $x_0,x_1, \ldots,x_{2n-1}$ and get \begin{eqnarray*} {\cal L}_{x_0, \ldots,x_{2n-1}}(A) &=& [A(x_0), \ldots A(x_{2n-1})] \in k^{2n} \\ {\cal L}_{x_0, \ldots,x_{2n-1}}(B) &=& [B(x_0), \ldots B(x_{2n-1})] \in k^{2n} \end{eqnarray*} \item now compute the $2n$ products $y_i = A(x_i) \cdot B(x_i)$,\\ $(0 \leq i < 2n)$. \item interpolating at points $x_0,x_1, \ldots,x_{2n-1}$ obtain the uniquely determined polynomial $C(X) \in k[X]_{2n}$ s.th. \[ C(x_i) = y_i = A(x_i) \cdot B(x_i)~~~(0 \leq i < 2n) \] since $A(X) \cdot B(X)$ is a polynomial of degree $< 2n$, it must hold that $C(X) = A(X) \cdot B(X)$ \end{enumerate} \item the ``modular'' scheme \normalsize \[ \CD A(X),B(X) \cdr{{\cal L}_{x_0,\ldots,x_{2n-1}}}{} [A(x_0),\ldots,A(x_{2n-1})] , [B(x_0),\ldots,B(x_{2n-1})] \\ \cdd{}{} \cdd{}{C(x_i) := A(x_i)\cdot B(x_i)} \\ C(X) = A(X)\cdot B(X) \cdl{{\cal I}_{x_0,\ldots,x_{2n-1}}}{} [C(x_0),\ldots,C(x_{2n-1})] \endCD \] \end{itemize} \newpage \section{Polynomials and Their Roots} \begin{itemize} \item {\em division property} : for any $f,g \in k[X]$ s.th. $g(X)\neq 0$ there exist uniquely determined $q,r \in k[X]$ s.th \[ f(X) = g(X)\cdot q(X) + r(X) \] where $r$ is either the zero polynomial (in this case one says that $g$ divides $f$, written $f|g$) or $0 \leq \deg r < \deg g$. \item {\em division and evaluation} : for $f \in k[X]$ and $x_0 \in k$ it holds in particular that \[ f(X) = (X-x_0)\cdot q(X) + f(x_0) \] i.e., the {\em evaluation} of $f(X)$ at $x_0$ is the {\em division remainder} when dividing by $X-x_0$. \item {\em division and roots} : the property of $x_0 \in k$ of being a root of $f(X)$ is expressed as follows: \[ f(x_0) = 0 ~~\Leftrightarrow~~ (X-x_0) | f(X)~~\Leftrightarrow~~ f(X) \equiv 0 ~\hbox{mod}~X-x_0 \] \pagebreak \item {\em multiplicities of roots} : for $f \in k[X]$ and $x_0 \in k$ there is a uniquely determined natural number $n$ such that \[ (X-x_0)^n | f(X)~~,~~(X-x_0)^{n+1} \not | f(X) \] this is the {\em multiplicity} of $x_0$ as a root of $f(X)$, written as $n = \nu(f,x_0)$. \item {\em lemma} : let $f,g,h \in k[X]$ s.th. $f=g\cdot h$ and $x_0 \in k$, then \[ \nu(f,x_0)=\nu(g,x_0)+\nu(h,x_0) \] \item {\em proposition} : let $f \in k[X], f \neq 0$, then \[ \sum_{x \in k} \nu(f,x) \leq \deg f \] \item {\em fundamental theorem of algebra} : each complex polynomial $f(X) \in {\bf C}[X]$ has at least one zero in {\bf C}. \item {\em consequence} : for $f \in {\bf C}[X]$ it holds that \[ \sum_{x \in {\bf C}}\nu(f,x) = \deg f \] \end{itemize} \newpage \section{Roots of Unity} \begin{itemize} \item definition : Let $k$ be a field (or, more generally, a ring) and $n \geq 1$ an integer, then any $\omega \in k$ s.th. $\omega^n = 1$, i.e., any root of the equation $X^n-1=0$ is called a $n$-th {\em root of unity}. \item complex $n$-th roots of unity \[ {\cal R}_n := \{~e^{2 \pi i t / n}\,;\,0 \leq t < n~\} \] \item properties \begin{eqnarray*} {\cal R}_m \cap {\cal R}_n &=& {\cal R}_{\gcd(m,n)} \\ d \, | \, n &\Rightarrow& {\cal R}_d \subseteq {\cal R}_n \end{eqnarray*} \item complex principal $n$-th root of unity \[ \omega_n := e^{2 \pi i / n} \] \item rules for computation \begin{itemize} \item for $n,d > 0, t \in {\bf Z}$~:~ $\omega_{d\,n}^{d\,t} = \omega_n^t$ \item for $n > 0$~:~ $\omega_{2n}^n = -1 (\, = \omega_2\,)$ \item squaring $x \mapsto x^2$ maps ${\cal R}_{2n}$ onto ${\cal R}_n$. Each $\omega_n^t$, $(0 \leq t < n)$ has the two preimages $\omega_{2n}^t$ and $\omega_{2n}^{t+n}$. \item for $n \geq 1$ and $t \in {\bf Z}$ one has \[ \sum_{x \in R_n} x^t = \sum_{j=0}^{n-1} \left(\omega_n^t \right)^j = \cases{ n & if $n|t$ \cr 0 & if $n \not | t$} \] \end{itemize} \end{itemize} \newpage \section{Primitive Roots of Unity} \begin{itemize} \item definition (one possiblity) \[ {\cal P}_n = {\cal R}_n \setminus \bigcup_{d|n \atop d \neq n} {\cal R}_d \] \item consequence \[ {\cal R}_n = \bigcup_{d|n} {\cal P}_d \] \item equivalent assertions \begin{itemize} \item $ \xi \in {\cal P}_n$ \item $\xi = \omega_n^t$ for some $t \in \{ 1,2,\ldots,n-1\}$ s.th. $\gcd(t,n) = 1$ \item ${\cal P}_n = \{\,\xi^t\,;\,1 \leq t < n, \gcd(n,t) = 1 \,\}$ \item ${\cal R}_n = \{\,\xi^t\,;\,1 \leq t < n \,\}$ \end{itemize} \Large \item {\sc Euler}'s phi-function: \begin{itemize} \item definition: \[ \phi(n) := \sharp \{\,t\,;\,1 \leq t < n,\, \gcd(t,n) = 1\,\} = \sharp {\cal P}_n \] \item first values: \[ \begin{array}{ccccccccccccccc} n & : & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \ldots\\ \phi(n)& : & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & \ldots \end{array} \] \item properties: \begin{itemize} \item $p$ prime$\Rightarrow \phi(p^n) = p^n - p^{n-1} = p^n \,\left(1 - {1 \over p}\right)$ \item $\gcd(m,n)=1$ $\Rightarrow\phi(m \cdot n) = \phi(m) \cdot \phi(n)$ \item for $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots$ one consequently has \normalsize \[ \phi(n) ~ = p_1^{\alpha_1} \left(1-{1 \over p_1}\right) p_2^{\alpha_2} \left(1-{1 \over p_2}\right) \cdots = n \cdot \prod_{p|n \atop p ~\hbox{\footnotesize prime}} \left(1 - {1 \over p} \right) \] \Large \item $n = \sum_{d|n} \phi(n)$ \end{itemize} \end{itemize} \end{itemize} \newpage examples: \normalsize \begin{eqnarray*} {\cal P}_1 &=& \left\{\omega_1^{\,} \right\} = \left\{ 1 \right\}\\ {\cal P}_2 &=& \left\{\omega_2^{\,} \right\} = \left\{ -1 \right\}\\ {\cal P}_3 &=& \left\{\omega_3^{\,},\omega_3^2 \right\} = \left\{ -{1 \pm \sqrt{3} \over 2}\right\}\\ {\cal P}_4 &=& \left\{\omega_4^{\,},\omega_4^3 \right\} = \left\{ \pm i \right\}\\ {\cal P}_5 &=& \left\{\omega_5^{\,},\omega_5^2,\omega_5^3,\omega_5^4 \right\} = \left\{ {\sqrt{5}-1 \pm i\sqrt{2}\sqrt{5+\sqrt{5}} \over 4}, {-\sqrt{5}-1 \pm i\sqrt{2}\sqrt{5-\sqrt{5}} \over 4}\right\} \\ {\cal P}_6 &=& \left\{\omega_6^{\,},\omega_6^5 \right\} = \left\{ {1 \pm i \sqrt{3} \over 2} \right\}\\ {\cal P}_7 &=& \left\{\omega_7^{\,},\omega_7^2,\omega_7^3,\omega_7^4,\omega_7^5, \omega_7^6 \right\} = \left\{ \cos\left({k \pi \over 7 }\right) \pm i \sin\left({k \pi \over 7 }\right)\,;\,1 \leq k \leq 3 \right\} \\ {\cal P}_8 &=& \left\{\omega_8^{\,},\omega_8^3,\omega_8^5,\omega_8^7 \right\} = \left\{ \pm {1 \pm i \over \sqrt{2} }\right\}\\ {\cal P}_9 &=& \left\{\omega_9^{\,},\omega_9^2,\omega_9^4,\omega_9^5, \omega_9^7,\omega_9^8 \right\} = \left\{ \cos\left({k \pi \over 9 }\right) \pm i \sin\left({k \pi \over 9 }\right)\,;\,k \in \left\{1,2,4\right\}\right\}\\ {\cal P}_{10} &=& \left\{\omega_{10}^{\,},\omega_{10}^3,\omega_{10}^7, \omega_{10}^9 \right\} = \left\{ \cos\left({k \pi \over 10 }\right) \pm i \sin\left({k \pi \over 10 }\right)\,;\,k \in \left\{1,3\right\}\right\}\\ {\cal P}_{11} &=& \left\{\omega_{11}^{\,},\omega_{11}^2,\omega_{11}^3, \omega_{11}^4,\omega_{11}^5,\omega_{11}^6,\omega_{11}^7,\omega_{11}^8, \omega_{11}^9,\omega_{11}^{10} \right\} = \left\{ \cos\left({k \pi \over 11 }\right) \pm i \sin\left({k \pi \over 11 }\right)\,;\,1 \leq k \leq 5 \right\}\\ {\cal P}_{12} &=& \left\{\omega_{12}^{\,},\omega_{12}^5, \omega_{12}^7, \omega_{12}^{11} \right\} = \left\{ \pm {\sqrt{3} \pm i\over 2} \right\}\\ \end{eqnarray*} %\newpage \Large inclusion for roots of unity \vskip1cm \input{teiler} \newpage \section{Discrete Fourier Transform} \Large \begin{itemize} \item definition Sei ${\bf a} = (a_0,a_1,a_2,\ldots,a_{n-1}) \in {\bf C}^n$ \[ DFT_n({\bf a}) := {\bf y} = \cases{ (y_0,y_1,\ldots,y_{n-1}) &\cr \hbox{with}~y_j = \sum_{t=0}^{n-1} a_t \, \omega_n^{jt}~~~(0 \leq j < n)&} \] \item written as an evaluation of polynomials \newline let $A(X) := \sum_{t=0}^{n-1}a_t \, X^t$, then \[ DFT_n ~:~ {\bf C}^n \rightarrow {\bf C}^n ~:~ {\bf a} ~\mapsto~ (A(\omega_n^0),A(\omega_n^1),\ldots,A(\omega_n^{n-1})) \] is the simultaneous evaluation of $A(X)$ at the $n$-th roots of unity \item matrix representation \[ V_n := V(\omega_n^0,\omega_n^1, \ldots,\omega_n^{n-1}) = \left( \omega_n^{jk} \right)_{0 \leq j,k < n} \] \item inverse transformation \[ V_n^{-1} = \left({1 \over n}\, \omega_n^{-jk} \right)_{0 \leq j,k < n} \] proof %\normalsize \begin{eqnarray*} \left( \omega_n^{jk} \right)_{0 \leq j,k < n} \left({1 \over n}\, \omega_n^{-kl} \right)_{0 \leq k,l < n} & = & \left({1 \over n} \sum_{k=0}^{n-1} \omega_n^{(j-l)k} \right)_{0 \leq j,l < n} \\ & = & (\,\delta_{j,l}\,)_{0 \leq j,l < n} \end{eqnarray*} \end{itemize} \newpage \section{DFT Matrices} Note: all the entries $\omega_n^{jk}, 0 \leq j,k < n$, of the matrix $V_n$ are $n$-th roots of unity --- because of $\omega_n^n=1$ it holds that \[ \omega_n^{jk} = \omega_n^t \] where $t$ with $0 \leq t < n$ is the remainder when dividing $j \cdot k$ by $n$ , i.e., $jk \equiv t ~\hbox{mod}~ n$. \begin{itemize} \item $n=2$ one has $\omega_2 = -1$, hence \[ V_2 = \left [\begin {array}{cc} 1&1\\\noalign{\medskip}1&-1\end {array} \right ] \] the inverse matrix is \[ V_2^{-1} = \left [\begin {array}{cc} 1/2&1/2\\\noalign{\medskip}1/2&-1/2 \end {array}\right ] \] \item $n=3$ one has $\omega_3 ={-1+i \,\sqrt{3} \over 2}$ and \begin{eqnarray*} V_3 &=& \left [\begin {array}{ccc} 1 & 1 & 1 \\ 1 & \omega_3 & \omega_3^2 \\ 1 & \omega_3^2 & \omega \end {array}\right ] \\ &=& \left [\begin {array}{ccc} 1&1&1\\\noalign{\medskip}1&-1/2+{\frac { \sqrt {-1}\sqrt {3}}{2}}&-1/2-{\frac {\sqrt {-1}\sqrt {3}}{2}} \\\noalign{\medskip}1&-1/2-{\frac {\sqrt {-1}\sqrt {3}}{2}}&-1/2+{ \frac {\sqrt {-1}\sqrt {3}}{2}}\end {array}\right ] \end{eqnarray*} the inverse transformation is given by \[ V_3^{-1} = \left [\begin {array}{ccc} 1/3&1/3&1/3\\\noalign{\medskip}1/3&-{\frac {\sqrt {-1}\sqrt {3}}{6}}-1/6&{\frac {\sqrt {-1}\sqrt {3}}{6}}-1/6 \\\noalign{\medskip}1/3&{\frac {\sqrt {-1}\sqrt {3}}{6}}-1/6&-{\frac { \sqrt {-1}\sqrt {3}}{6}}-1/6\end {array}\right ] \] \newpage \item $n=4$ one has $\omega_4 = i = \sqrt{-1}$ and thus \begin{eqnarray*} V_4 &=& \left [\begin {array}{cccc} 1&1&1&1 \\ 1 & i & i^2 & i^3 \\ 1 & i^2 & 1 & i^2 \\ 1 & i^3 & i^2 & i \end {array}\right ] \\ &=& \left [\begin {array}{cccc} 1&1&1&1\\\noalign{\medskip}1&\sqrt {-1}&-1 &-\sqrt {-1}\\\noalign{\medskip}1&-1&1&-1\\\noalign{\medskip}1&-\sqrt {-1}&-1&\sqrt {-1}\end {array}\right ] \\ \end{eqnarray*} the inverse transformation is given by \[ V_4^{-1} = \left [\begin {array}{cccc} 1/4&1/4&1/4&1/4\\\noalign{\medskip}1/4&-{ \frac {\sqrt {-1}}{4}}&-1/4&{\frac {\sqrt {-1}}{4}} \\\noalign{\medskip}1/4&-1/4&1/4&-1/4\\\noalign{\medskip}1/4&{\frac { \sqrt {-1}}{4}}&-1/4&-{\frac {\sqrt {-1}}{4}}\end {array}\right ] \] \newpage \item $n=5$ the entries of the matrix are elements of ${\cal R}_5$, as mentioned above \[ V_5 = \left [\begin {array}{ccccc} 1&1&1&1&1 \\ 1 & \omega_5 & \omega_5^2 & \omega_5^3 & \omega_5^4 \\ 1 & \omega_5^2 & \omega_5^4 & \omega_5^1 & \omega_5^3 \\ 1 & \omega_5^3 & \omega_5^1 & \omega_5^4 & \omega_5^2 \\ 1 & \omega_5^4 & \omega_5^3 & \omega_5^2 & \omega_5^1 \\ \end {array}\right ] \] as to the inverse transformation, note that the elements $\omega_5$ and $\omega_5^4$, and similarly the elements $\omega_5^2$ and $\omega_5^3$, are inverse to each other. \[ V_5^{-1} = {1 \over 5} \, \left [\begin {array}{ccccc} 1&1&1&1&1 \\ 1 & \omega_5^4 & \omega_5^3 & \omega_5^2 & \omega_5^1 \\ 1 & \omega_5^3 & \omega_5^1 & \omega_5^4 & \omega_5^2 \\ 1 & \omega_5^2 & \omega_5^4 & \omega_5^1 & \omega_5^3 \\ 1 & \omega_5^1 & \omega_5^2 & \omega_5^3 & \omega_5^4 \\ \end {array}\right ] \] \newpage \item $n=6$ one has $\omega_6 = {1+ i\,\sqrt{3} \over 2}$. The following facts can be used by writing down $V_6$ : \[ \omega_6 = \omega_2 \cdot \omega_3^2 = - \omega_3^2 ~,~ \omega_6^2 = \omega_3~,~ \omega_6^3 = -1 ~,~ \omega_6^4 = \omega_3^2 ~,~ \omega_6^5 = - \omega_3 \] hence $V_6$ can be expressed using $\omega_3$ \begin{eqnarray*} V_6 &=& \left [\begin {array}{cccccc} 1&1&1&1&1&1 \\ 1& \omega_6 & \omega_6^2 & \omega_6^3 & \omega_6^4 & \omega_6^5 \\ 1& \omega_6^2 & \omega_6^4 & 1 & \omega_6^2 & \omega_6^4 \\ 1& \omega_6^3 & 1 & \omega_6^3 & 1 & \omega_6^3 \\ 1& \omega_6^4 & \omega_6^2 & 1 & \omega_6^4 & \omega_6^2 \\ 1& \omega_6^5 & \omega_6^4 & \omega_6^3 & \omega_6^2 & \omega_6^1 \\ \end {array}\right ] \\ &=& \left [\begin {array}{cccccc} 1&1&1&1&1&1 \\ 1& - \omega_3^2 & \omega_3 & -1 & \omega_3^2 & - \omega_3 \\ 1& \omega_3 & \omega_3^2 & 1 & \omega_3 & \omega_3^2 \\ 1& -1 & 1 & -1 & 1 & -1 \\ 1& \omega_3^2 & \omega_3 & 1 & \omega_3^2 & \omega_3 \\ 1& - \omega_3 & \omega_3^2 & -1 & \omega_3 & - \omega_3^2 \\ \end {array}\right ] \end{eqnarray*} the matrix of the inverse transformation can also be written in terms of third roots of unity \end{itemize} \newpage \section{Fast Fourier Transform (FFT)} \begin{itemize} \item situation: \[ A(X) = \sum_{0 \leq j < 2m} a_j \, X^j \in k[X]_{2m} \] has to be evaluated at $n=2m$ points \[ {\cal R}_{2m} = \{ \omega_{2m}^t\,;\,0 \leq t < 2m \,\} \] \item decomposition \[ A(X) = A^{[0]}(X^2) + X \cdot A^{[1]}(X^2) \] with \begin{eqnarray*} A^{[0]}(X) &=& a_0 + a_2 \,X + a_4\,X^2 + \cdots + a_{2m-2}\,X^{m-1} \\ A^{[1]}(X) &=& a_1 + a_3 \,X + a_5\,X^2 + \cdots + a_{2m-1}\,X^{m-1} \end{eqnarray*} \item one has to compute for $0 \leq t < n = 2m$: \begin{eqnarray*} A(\omega_n^t) &=& A^{[0]}(\omega_{n}^{2t}) + \omega_n^t \cdot A^{[1]}(\omega_{n}^{2t}) \\ &=&A^{[0]}(\omega_{m}^{t}) + \omega_n^t \cdot A^{[1]}(\omega_{m}^{t}) \end{eqnarray*} by evaluation of $A^{[0]}(X)$ and $A^{[1]}(X)$ with degree bound $m$ at $m$ points \[ {\cal R}_m = \{\,\omega_{2m}^{2t}(=\omega_m^t)\,;\,0\leq t < m\,\} \] \item thus there is need to compute \begin{eqnarray*} DFT_m({\bf A}^{[0]}) &=& (y_0^{[0]},y_1^{[0]},\ldots,y_{m-1}^{[0]}) = {\bf y}^{[0]} ~~~\hbox{mit}~~y_t = A^{[0]}(\omega_m^t) \\ DFT_m({\bf A}^{[1]}) &=& (y_0^{[1]},y_1^{[1]},\ldots,y_{m-1}^{[1]}) = {\bf y}^{[1]} ~~~\hbox{mit}~~y_t = A^{[1]}(\omega_m^t) \end{eqnarray*} \newpage \item one obtains \[ DFT_n({\bf A}) = (y_0,y_1,\ldots,y_{n-1}) = {\bf y} \] via \[ y_t = A(\omega_n^t) = A^{[0]}(\omega_m^t) + \omega_n^t \cdot A^{[1]}(\omega_m^t)~~ (0 \leq t < n) \] but for $0 \leq t < m$ one has \[ \omega_n^{m+t} = \omega_{2m}^m \cdot \omega_n^t = (-1) \,\omega_n^t \] so that one can write \begin{eqnarray*} y_t &=& y_t^{[0]} + \omega_n^t \cdot y_t^{[1]} \\ y_{m+t} &=& y_t^{[0]} - \omega_n^t \cdot y_t^{[1]} \end{eqnarray*} \end{itemize} \input{fft} \newpage the fft program \begin{verbatim} FFT := proc (A,k) n := 2^k; if k=0 then RETURN(A) fi; omega_n := exp(2*Pi*I/n); omega := 1; a_0 := [A[0],A[2],...,A[n-2]]; a_1 := [A[1],A[3],...,A[n-1]]; y_0 := FFT(a_0,k-1); y_1 := FFT(a_1,k-1); for t from 0 to (n/2)-1 do y[t] := y_0[t] + omega*y_1[t]; y[t+(n/2)] := y_0[t] - omega*y_1[t]; omega := omega*omega_n od; RETURN(y); end; \end{verbatim} \newpage \begin{itemize} \item analysis \begin{itemize} \item $T(n)$ := cost of copmputing $DFT(A)$ for vectors of length $n=2^k$ via {\tt FFT} \item recurrence relation \[ T(2n) = 2 \cdot T(n) + {\cal O}(n) \] \item conclusion \[ T(n) \in {\cal O}(n \, \log n) \] \end{itemize} \item this holds also for the inverse transform (=interpolation) \item the FFT-algorithms allows for a computation of the discrete Fourier transform and its inverse transform for vectors of length $n$ with a complexity of ${\cal O}(n \,\log n)$ operations in the base field (of complex numbers). \item phrased in the language of polynomial arithmetic: simultaneous evaluation and interpolation of (complex) polynomials with degree bound $n$ are possible with ${\cal O}(n \,\log n)$ operations in the base field if the $n$-th roots of unity are taken as points for evaluation and interpolation. Hence computing the product (convolution) of two polynomials with degree bound $n$ is possible using ${\cal O}(n \,\log n)$ field operations. \end{itemize} \end{document}