+\def\scharfs{\char"19}
\input lecnotes.tex
\def\imply{\Rightarrow}
-\prednaska{8}{Fourierova transformace}{ \vbox{\hbox{(K.Jakubec, M.Polák
+\prednaska{9}{Fourierova transformace}{\vbox{\hbox{(K.Jakubec, M.Polák
a~G.Ocsovszky,}\hbox{\ V.Tùma, M.Kozák)}}}
Násobení polynomù mù¾e mnohým pøipadat jako pomìrnì (algoritmicky) snadný
Fourier Transform}.
-\ss{Trochu algebry na~zaèátek:}
-\>Libovolný polynom $P$ stupnì $n$ lze reprezentovat dvìma rùznými zpùsoby:
+\ss{Trochu algebry na~zaèátek}
+Celé polynomy oznaèujeme velkými písmeny, jednotlivé èleny polynomù pøíslu¹nými
+malými písmeny (pø.: polynom $W$ stupnì $d$ má koeficienty $w_{0}, w_{1},
+w_{2},\ldots, w_{d}$).
-\itemize\ibull
-\:svými koeficienty, èili èísly $p_{0}, p_{1}, \ldots ,p_{n}$, nebo
-\:svými hodnotami v~$n$ rùzných bodech $x_{0}, x_{1}, \ldots , x_{n}$, èili
-èísly $P(x_{0}),$ $P(x_{1}),$ $\ldots , P(x_{n})$.
-\endlist
+Libovolný polynom $P$ stupnì (nejvý¹e) $d$ lze reprezentovat
+jednak jeho koeficienty, tedy èísly $p_{0}, p_{1}, \ldots ,p_{d}$, druhak
+i~pomocí hodnot:
+
+\>{\bf Lemma:} Polynom stupnì nejvý¹e $d$ je jednoznaènì urèeò svými
+hodnotami v~$d+1$ rùzných bodech.
-\>Dostateènost $n+1$ hodnot pro urèení druhým zpùsobem lze dokázat
-následnovnì: polynom stupnì $n$ má maximálnì $n$ koøenù (indukcí, je-li
+\>{\it Dùkaz:}
+Polynom stupnì $d$ má maximálnì $d$ koøenù (indukcí -- je-li
$k$ koøenem $P$, pak lze $P$ napsat jako $(x-k)Q$ kde $Q$ je polynom stupnì
o~jedna men¹í, pøitom polynom stupnì 1 má jediný koøen); uvá¾íme-li
-dva rùzné polynomy $P$ a~$Q$ stupnì $n$ nabývající v~daných bodech stejných
-hodnot, tak $P-Q$ je polynom stupnì maximálnì $n$, ka¾dé
-z $x_{0}\ldots x_{n}$ je koøenem tohoto polynomu $\imply$ spor, polynom stupnì
-$n$ má $n+1$ koøenù $\imply$ $P-Q$ musí být nulový polynom $\imply$ $P=Q$.
+dva rùzné polynomy $P$ a~$Q$ stupnì $d$ nabývající v~daných bodech stejných
+hodnot, tak $P-Q$ je polynom stupnì maximálnì $d$, ka¾dé
+z $x_{0}\ldots x_{d}$ je koøenem tohoto polynomu $\imply$ spor, polynom stupnì
+$d$ má $d+1$ koøenù $\imply$ $P-Q$ musí být nulový polynom $\imply$ $P=Q$.
+\qed
\medskip
-\ss{Konvence:}
-Celé polynomy oznaèujeme velkými písmeny, jednotlivé èleny polynomù pøíslu¹nými
-malými písmeny (pø.: polynom $W$ stupnì $n$ má koeficienty $w_{0}, w_{1},
-w_{2},\ldots, w_{n}$).
-
-Pov¹imnìme si jedné skuteènosti -- máme-li dva polynomy $A$ a~$B$ stupnì $n$
-a~body $x_{0}, \ldots, x_{k}$, dále polynom $C=A \cdot B$ (stupnì $2n$), pak
-platí $C(x_{k}) = A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots, n.$ Toto èiní
-tento druhý zpùsob reprezentace polynomu velice atraktivním pro násobení.
-Problémem je, ¾e typicky máme polynom zadaný koeficienty a~ne hodnotami
+Pov¹imnìme si jedné skuteènosti -- máme-li dva polynomy $A$ a~$B$ stupnì $d$
+a~body $x_{0}, \ldots, x_{n}$, dále polynom $C=A \cdot B$ (stupnì $2d$), pak
+platí $C(x_{j}) = A(x_{j}) \cdot B(x_{j})$ pro $j = 0,1,2, \ldots, n$. Toto
+èiní tento druhý zpùsob reprezentace polynomu velice atraktivním pro násobení
+-- máme-li $A$ i $B$ reprezentované hodnotami v $n \geq 2d+1$ bodech, pak
+snadno (v $\Theta(n)$) spoèteme takovou reprezentaci $C$.
+Problémem je, ¾e typicky máme polynom zadaný koeficienty, a~ne hodnotami
v~bodech. Tím pádem potøebujeme nìjaký hodnì rychlý algorimtus (tj.
rychlej¹í ne¾ kvadratický, jinak bychom si nepomohli oproti hloupému
algoritmu) na~pøevod polynomu z jedné reprezentace do druhé a~zase zpìt.
-Dále bychom si mìli uvìdomit, ¾e stupeò na¹eho výsledného polynomu $C$ bude
-$\leq 2n$ (kde $n$ je stupeò výchozích polynomù). Pokud chceme polynom $C$
-reprezentovat pomocí jeho hodnot v~bodech, musíme tedy vzít alespoò $2n$
-bodù. Tímto konèí malá algebraická vsuvka.
-
\s{Idea, jak by mìl algoritmus pracovat:}
\algo
-\:Vybereme $2n$ bodù $x_{0}, x_{1}, \ldots , x_{2n-1}$.
+\:Vybereme $n\geq 2d+1$ bodù $x_{0}, x_{1}, \ldots , x_{n-1}$.
\:V tìchto bodech vyhodnotíme polynomy $A$ a~$B$.
-\:Nyní ji¾ v~lineárním èase získáme hodnoty polynomu $C$ v~tìchto bodech
- (viz vý¹e).
+\:Nyní ji¾ v~lineárním èase získáme hodnoty polynomu $C$ v~tìchto bodech:
+ $C(x_i) = A(x_i)\cdot B(x_i)$
\:Pøevedeme hodnoty polynomu $C$ na~jeho koeficienty.
\endalgo
-\>Je vidìt, ¾e klíèové jsou kroky 2 a~4. Vybrání bodù jistì stihneme pohodlnì
-v~lineárním èase a~vynásobení samotných hodnot té¾ (máme $2n$ bodù a~$C(x_{k})
-= A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots , 2n-1$, tak¾e na~to nepotøebujeme
-více ne¾ $2n$ násobení).
-
+\>Je vidìt, ¾e klíèové jsou kroky 2 a~4.
Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy
-vyhodnocovat. Je na~to potøeba vìdìt pár zajímavostí o~komplexních èíslech,
-na~webové stránce pøedná¹ky jsou k dispozici slajdy, zde to bude zapsáno
-o~trochu struènìji.
+vyhodnocovat -- zvolí-li se obecná $x_j$, tak se to rychle neumí, pro speciální
+$x_j$ ale uká¾eme, ¾e to rychle jde.
-\ss{ Vyhodnocení polynomu metodou Rozdìl a~panuj (algoritmus FFT):}
-Mìjme polynom $P$ øádu $n$ a~chtìjme jej vyhodnotit v~$n$ bodech. Vybereme si
-body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1}, \ldots , \pm
-x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé mocniny $x_{j}$
-shodují s~druhými mocninami $-x_{j}$.
+\ss{Vyhodnocení polynomu metodou Rozdìl a~panuj (algoritmus FFT):}
+Mìjme polynom $P$ stupnì $\leq d$ a~chtìjme jej vyhodnotit v~$n$ bodech.
+Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1},
+\ldots , \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé
+mocniny $x_{j}$ shodují s~druhými mocninami $-x_{j}$.
Polynom $P$ rozlo¾íme na~dvì èásti, první obsahuje èleny se sudými exponenty,
druhá s~lichými:
-$$P(x) = (p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n-2}x^{n-2}) + (p_{1}x^{1} +
- p_{3}x^{3} + \ldots + p_{n-1}x^{n-1})$$
+$$P(x) = (p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{d-2}x^{d-2}) + (p_{1}x^{1} +
+ p_{3}x^{3} + \ldots + p_{d-1}x^{d-1})$$
\>se zavedením znaèení:
-$$P_s(x^{2}) = p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n - 2}x^{n - 2}$$
-$$P_l(x^{2}) = p_{1}x^{1} + p_{3}x^{3} + \ldots + p_{n - 1}x^{n - 1}$$
+$$P_s(t) = p_0t^0 + p_{2}t^{1} + \ldots + p_{d - 2}t^{d - 2\over 2}$$
+$$P_l(t) = p_1t^0 + p_3t^1 + \ldots + p_{d - 1}t^{d - 2\over 2}$$
-\>Dohromady $P(x) = P_s(x^{2}) + xP_l(x^{2})$ a~$P(-x) = P_s(x^{2}) -
-xP_l(x^{2})$. Jinak øeèeno, vyhodnocování $P$ v~$n$ bodech se nám smrskne
-na~vyhodnocení $P_s(x)$ a~$P_l(x)$ (oba jsou polynomy stupnì $n/2$
-a~vyhodnocujeme je nyní v~$x^{2}$) v~$n/2$ bodech (proto¾e $(x_{i})^{2} =
-(-x_{i})^{2}$).
+\>bude $P(x) = P_s(x^{2}) + xP_l(x^{2})$ a~$P(-x) = P_s(x^{2}) -
+xP_l(x^{2})$. Jinak øeèeno, vyhodnocování polynomu $P$ v~$n$ bodech se nám
+smrskne na~vyhodnocení $P_s$ a~$P_l$ v~$n/2$ bodech -- oba jsou polynomy
+stupnì nejvý¹e $d/2$ a~vyhodnocujeme je v~$x^{2}$ (vyu¾íváme
+rovnosti $(x_{i})^{2} = (-x_{i})^{2}$).
\s{Pøíklad:}
$3 + 4x + 6x^{2} + 2x^{3} + x^{4} + 10x^{5} = (3 + 6x^{2} + x^{4}) + x(4 +
Teï nám ov¹em vyvstane problém s~oním párováním -- druhá mocina pøece nemù¾e
být záporná a~tím pádem u¾ v~druhé úrovni rekurze body spárované nebudou.
Z~tohoto dùvodu musíme pou¾ít komplexní èísla -- tam druhé mocniny záporné býti
-mohou. Jako $x_{0}, \ldots , x_{n-1} $ si zvolíme mocniny
-$n$-té primitvní odmocniny z jedné (oznaèíme si ji jako $\omega$). Pøipomeòme:
-$\omega$ je $n$-tá odmocnina z $1$ je {\it primitivní} $\equiv$ $(\forall k)
-(k<n)\ \omega^k \neq 1$ a~$\omega^n = 1$. Máme $n$ navzájem rùzných odmocnin
-z~jednièky, rovnomìrnì rozesetých po jednotkové kru¾nici, BÚNO $n=2^{k}, k \in
-N$ (jinak viz slajdy Martina Mare¹e). Jednotlivé $x$ vypadají takto: $1,
-\omega, \omega^{2}, \ldots , \omega^{n - 1} $, kde $\omega = e^{2 \pi i/ n}$.
-
-\s{Pìt poznámek:}
+mohou.
+
+% komplex
+\h{Komplexní intermezzo}
+\def\i{{\rm i}}
+\def\\{\hfil\break}
+
+\s{Základní operace}
+
+\itemize\ibull
+\:Definice: ${\bb C} = \{a + b\i \mid a,b \in {\bb R}\}$
+
+\:Sèítání: $(a+b\i)\pm(p+q\i) = (a\pm p) + (b\pm q)\i$. \\
+Pro $\alpha\in{\bb R}$ je $\alpha(a+b\i) = \alpha a + \alpha b\i$.
+
+\:Komplexní sdru¾ení: $\overline{a+b\i} = a-b\i$. \\
+$\overline{\overline x} = x$, $\overline{x\pm y} = \overline{x} \pm
+\overline{y}$, $\overline{x\cdot y} = \overline x \cdot \overline y$, $x
+\cdot \overline x \in {\bb R}$.
+
+\:Absolutní hodnota: $\vert x \vert = \sqrt{x\cdot\overline{x}}$, tak¾e $\vert
+a+b\i \vert = \sqrt{a^2+b^2}$. \\
+Také $\vert \alpha x \vert = \vert \alpha\vert \cdot \vert x \vert$.
+
+\:Dìlení: $x/y = (x\cdot \overline{y}) / (y \cdot \overline{y})$.
+\endlist
+
+\s{Gau{\scharfs}ova rovina a goniometrický tvar}
+
\itemize\ibull
-\:Pro $k\neq j,\ 0\leq k<j<n$ je $\omega^k \neq \omega^j$, nebo» $\omega^j /
-\omega^k = \omega^{j-k}\neq 1$, proto¾e $j-k < n$ a~$\omega$ je $n$-tá
-primitivní (a~tedy $\omega^0, \ldots, \omega^{n-1}$ jsou rùzné).
-\:$\overline{\omega} = \omega^{-1}$, nebo» $\omega^{-1} = \omega^{-2\pi i/n}$
-a~tedy èísla $\omega,\omega^{-1}$ svírají vùèi reálné ose opaèný úhel a~jsou
- komplexnì sdru¾ená.
-\:mocniny $\omega$ jsou spárované, èili $\omega^{j} = -\omega^{n/2 + j}$
- (staèí si uvìdomit, ¾e $\omega^{n/2} = -1$ pro $n$ sudé)
-\:umocníme-li v¹echny $\omega^{0},\ldots, \omega^{n-1}$ na~druhou, vzniknou nám
- odmnocniny z~$1$ které budou i~nadále spárované: $\omega^n$ je toti¾
- $1$ a~exponenty lze tedy poèítat$\mod n$, $n$ je sudé $\imply$
- dostaneme pùvodní posloupnost ze které zmizí liché mocniny $\omega$, ale $n$
- je mocnina dvojky a~tedy i~$n/2$ je sudé (pro $n=2$ ne, ale tam je to
- triviální), tak¾e sudé mocniny jsou spárované navzájem..
-\:$\omega^2$ je $n/2$-tá primitivní odmocnina z 1 -- je toti¾ $(\omega^{-2\pi
- i/n})^2 = \omega^{-2\pi i/(n/2)}$ a~$n$ je mocnina dvojky.
+\:Komplexním èíslùm pøiøadíme body v~${\bb R}^2$: $a+b\i \leftrightarrow (a,b)$.
+
+\:$\vert x\vert$ je vzdálenost od~bodu $(0,0)$.
+
+\:$\vert x\vert = 1$ pro èísla le¾ící na~jednotkové kru¾nici ({\I komplexní jednotky}). \\
+Pak platí $x=\cos\varphi + \i\sin\varphi$ pro nìjaké $\varphi\in\left[
+0,2\pi \right)$.
+
+\:Pro libovolné $x\in{\bb C}$: $x=\vert x \vert \cdot (\cos\varphi(x) +
+\i\sin\varphi(x))$. \\
+Èíslu $\varphi(x)\in\left[ 0,2\pi \right)$ øíkáme {\I argument}
+èísla~$x$, nìkdy znaèíme $\mathop{\rm arg} x$.
+
+\:Navíc $\varphi({\overline{x}}) = -\varphi(x)$.
\endlist
+\s{Exponenciální tvar}
+
+\itemize\ibull
+\:Eulerova formule: $e^{i\varphi} = \cos\varphi + \i\sin\varphi$.
+
+\:Ka¾dé $x\in{\bb C}$ lze tedy zapsat jako $\vert x\vert \cdot e^{\i\cdot
+\varphi(x)}$.
+
+\:Násobení: $xy = \left(\vert x\vert\cdot e^{\i\cdot\varphi(x)}\right) \cdot
+ \left(\vert y\vert\cdot e^{\i\cdot\varphi(y)}\right) = \vert x\vert
+ \cdot \vert y\vert \cdot e^{\i\cdot(\varphi(x) + \varphi(y))}$. \\
+(absolutní hodnoty se násobí, argumenty sèítají)
+
+\:Umocòování: $x^\alpha = \left(\vert x\vert\cdot e^{\i\cdot\varphi(x)}\right)^
+ \alpha = {\vert x\vert}^\alpha\cdot e^{\i \alpha \varphi(x)}$.
+
+\:Odmocòování: $\root n\of x = {\vert x\vert}^{1/n} \cdot e^{\i\cdot
+\varphi(x)/n}$. \\
+Pozor -- odmocnina není jednoznaèná: $1^4=(-1)^4=\i^4=(-\i)^4=1$.
+\endlist
+
+\s{Odmocniny z~jednièky}
+
+\itemize\ibull
+\:Je-li nìjaké $x\in{\bb C}$ $n$-tou odmocninou z~jednièky, musí platit:
+$\vert x \vert = 1$, tak¾e $x=e^{\i\varphi}$ pro nìjaké~$\varphi$.
+Proto $x^n = e^{\i\varphi n} = \cos{\varphi n} + \i\sin\varphi n = 1$.
+Platí tedy $\varphi n = 2k\pi$ pro nìjaké $k\in{\bb Z}$.
+
+\:Z~toho plyne: $\varphi = 2k\pi/n$ \\
+(pro $k=0,\ldots,n-1$ dostáváme rùzné $n$-té odmocniny).
+
+\:Obecné odmocòování: $\root n \of x = {\vert x\vert}^{1/n} \cdot e^{\i\varphi
+ (x)/n} \cdot u$, kde $u=\root n\of 1$.
+
+\:Je-li $x$ odmocninou z 1, pak $\overline{x} = x^{-1}$ -- je toti¾ $1 = \vert
+x\cdot \overline{x}\vert = x\cdot \overline{x}$.
+\endlist
+
+\s{Primitivní odmocniny}
+
+\s{Definice:} $x$ je {\I primitivní} $k$-tá odmocnina z 1 $\equiv x^k=1 \land \forall j: 0<j<k \Rightarrow x^j \neq 1$.
+
+\>Tuto definici splòují napøíklad èísla $\omega = e^{2\pi \i / k}$ a $\overline\omega = e^{-2\pi\i/k}$.
+Platí toti¾, ¾e $\omega^j = e^{2\pi\i j/k}$, co¾ je rovno~1 právì tehdy,
+je-li $j$ násobkem~$k$ (jednotlivé mocniny èísla~$\omega$ postupnì obíhají
+jednotkovou kru¾nici). Analogicky pro~$\overline\omega$.
+
+\>Uka¾me si nìkolik pozorování fungujících pro libovolné èíslo~$\omega$,
+které je primitivní $k$-tou odmocninou z~jednièky (nìkdy budeme potøebovat,
+aby navíc $k$ bylo sudé):
+
+\itemize\ibull
+\:Pro $0\leq j<l<k$ je $\omega^j \neq \omega^l$, nebo» $\omega^l /
+\omega^j = \omega^{l-j} \neq 1$, proto¾e $l-j < k$ a $\omega$ je primitivní.
+\:$\omega^{k/2} = -1$, proto¾e $(\omega^{k/2})^2 = 1$, a tedy
+$\omega^{k/2}$ je druhá odmocnina z~1. Takové odmocniny jsou dvì:
+1 a $-1$, ov¹em 1 to být nemù¾e, proto¾e $\omega$ je primitivní.
+\:$\omega^j = - \omega^{k/2 + j}$ -- pøímý dùsledek pøedchozího bodu, pro
+nás ale velice zajímavý: $\omega^0,\omega^1,\ldots,\omega^{k-1}$ jsou po dvou
+spárované.
+\:$\omega^2$ je $k/2$-tá primitivní odmocnina z 1 -- dosazením.
+\endlist
+
+\h{Konec intermezza}
+% end komplex
+
+\bigskip
+
+Vra»me se nyní k algoritmu. Z poslední èásti komplexního intermezza se zdá,
+¾e by nemusel být ¹patný nápad zkusit vyhodnocovat polynom v mocninách
+$n$-té primitivní odmocniny z~jedné (tedy za $x_0,x_1,\ldots,x_{n-1}$
+z~pùvodního algoritmu zvolíme $\omega^0,\omega^1,\ldots,\omega^{n-1}$).
+Aby nám v¹e vycházelo pìknì, zvolíme $n$ jako mocninu dvojky.
+
\ss{Celý algoritmus bude vypadat takto:}
\>FFT($P$, $ \omega$)
-\>{\sl Vstup:} $p_{0}, \ldots , p_{n-1}$, koeficienty polynomu $P$, a~$\omega$,
+\>{\sl Vstup:} $p_{0}, \ldots , p_{n-1}$, koeficienty polynomu $P$ stupnì
+nejvý¹e $n-1$, a~$\omega$,
$n$-tá primitivní odmocina z jedné.
\>{\sl Výstup:} Hodnoty polynomu v~bodech $1, \omega, \omega^{2}, \ldots ,
\algo
\:Pokud $n = 1$, vrátíme $p_{0}$ a~skonèíme.
-\:Jinak rozdìlíme $P$ na~sudé a~liché koeficienty a~rekurzivnì zavoláme
- FFT($P_s$, $\omega^{2}$) a~FFT($P_l$, $\omega^{2}$) -- $P_l$ i~$P_s$
- jsou stupnì max. $n/2-1$ a~$\omega^2$ je $n/2$-tá primitivní odmocnina.
+\:Jinak rozdìlíme $P$ èleny se sudými a lichými exponenty (jako v pùvodní
+my¹lence) a~rekurzivnì zavoláme FFT($P_s$, $\omega^{2}$) a~FFT($P_l$,
+$\omega^{2}$) -- $P_l$ i~$P_s$ jsou stupnì max. $n/2-1$, $\omega^2$ je
+$n/2$-tá primitivní odmocnina, a mocniny $\omega^2$ jsou stále po dvou
+spárované ($n$ je mocnina dvojky, a tedy i $n/2$ je sudé; popø. $n=2$ a je to
+zøejmé).
\:Pro $j = 0, \ldots , n/2 - 1$ spoèítáme:
\:\qquad $P(\omega^{j}) = P_s(\omega^{2j}) + \omega^{j}\cdot P_l(\omega^{2j})$.
\>{\I Diskretní Fourierova transformace} $(DFT)$
je zobrazení $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $$y=f(x) \equiv
\forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} \cdot \omega ^{jk}$$
-(pøestavme si ji jako funkci vyhodnocující polynom s~koeficienty $x$ v~bodech
-$\omega^j$). Takovéto zobrazení je lineární a~tedy popsatelné maticí $\Omega$
-s~prvky $\Omega_{jk} = \omega^{jk}$
+(DFT si lze mimo jiné pøedstavit jako funkci vyhodnocující polynom
+s~koeficienty $x_k$ v~bodech $\omega^j$). Takovéto zobrazení je lineární
+a~tedy popsatelné maticí $\Omega$ s~prvky $\Omega_{jk} = \omega^{jk}$.
+Chceme-li umìt pøevádìt z~hodnot polynomu na koeficienty, zajímá nás inverze
+této matice.
-\s{Jak najít inverzní matici?} Znaème $\overline{\Omega}$ matici, její¾ prvky
-jsou komplexnì sdru¾ené odpovídajícím prvkùm $\Omega$, a vyu¾ijeme následující
+\ss{Jak najít inverzní matici?}
+Znaème $\overline{\Omega}$ matici, její¾ prvky
+jsou komplexnì sdru¾ené odpovídajícím prvkùm $\Omega$, a vyu¾ijme následující
lemma:
-\ss{Lemma:}$\quad \Omega\cdot \overline{\Omega} = n\cdot E$
+\ss{Lemma:}$\quad \Omega\cdot \overline{\Omega} = n\cdot E$.
\proof $$ (\Omega\cdot \overline{\Omega})_{jk} = \sum_{l=0}^{n-1} \omega^{jl}
\cdot \overline{\omega^{lk}} = \sum \omega^{jl} \cdot \overline{\omega}^{lk} =
-\sum \omega^{jl} \cdot \omega^{-lk} = \sum \omega^{l(j-k)}$$
+\sum \omega^{jl} \cdot \omega^{-lk} = \sum \omega^{l(j-k)}\hbox{.}$$
\itemize\ibull
\:Pokud $j=k$, pak $ \sum \limits ^{n-1}_{l=0} (\omega ^{0}) ^{l} = n$.
-\:Pokud $j\neq k$, pou¾ijeme vzoreèek pro souèet geometrické posloupnosti, kde
-$a_{1}=1$ a~$q=\omega ^{(j-k) }$ a~dostaneme ${{\omega^{(j-k)n} -1} \over
-{\omega^{(j-k)} -1}} ={1-1 \over r- 1} = {0 \over \neq 0} = 0$, kde $r$
-je èíslo rùzné od jednièky (nebo» $\omega$ je $n$-tá primitivní odmoncina).
+\:Pokud $j\neq k$, pou¾ijeme vzoreèek pro souèet geometrické øady
+s kvocientem $\omega ^{(j-k) }$ a~dostaneme ${{\omega^{(j-k)n} -1} \over
+{\omega^{(j-k)} -1}} ={1-1 \over \neq 0} = 0$ (
+$\omega^{j-k} - 1$ je jistì $\neq 0$, nebo» $\omega$ je $n$-tá primitivní
+odmoncina a $j-k<n$).
\endlist
\qed
$\Omega({1 \over n} \overline{\Omega}) = {1 \over n}\Omega \cdot
\overline{\Omega} = E$, \quad $\Omega^{-1}_{jk} = {1 \over n}\overline{\omega^
{jk}} = {1 \over n}\omega^{-jk} = {1 \over n} {(\omega^{-1})}^{jk}$, \quad
-(pøipomínáme, $\omega^{-1}$ je $\overline{\omega}$, $\omega$ je $n$-tá
-primitivní odmocnina z jednièky).
-
-Ná¹ algoritmus poèítá tedy i~inverzní transformaci, pouze místo $\omega_n$
-pou¾ijeme komplexnì zdru¾ené $\overline{\omega_n}$ a~matici vynásobíme $(1/n)$.
-Co¾ je skvìlé -- staèí znát pouze jeden algoritmus u~kterého staèí v~jednom
-pøípadì pou¾ít transformovanou matici a~vydìlit $n$.
+(pøipomínáme, $\omega^{-1}$ je $\overline{\omega}$).
+
+Vyhodnocení polynomu lze provést vynásobením $\Omega$, pøevod do pùvodní
+reprezentace vynásobením $\Omega^{-1}$. My jsme si ale v¹imli chytrého
+spárování, a vyhodnocujeme polynom rychleji ne¾ kvadraticky (proto FFT,
+jako¾e {\it fast}, ne jako {\it fuj}). Uvìdomíme-li si, ¾e $\overline \omega =
+\omega^{-1}$ je také $n$-tá primitivní odmocnina z 1 (má akorát
+úhel s opaèným znaménkem), tak mù¾eme stejným trikem vyhodnotit i~zpìtný
+pøevod -- nejprve vyhodnotíme $A$ a $B$ v $\omega^j$, poté pronásobíme
+hodnoty a~dostaneme tak hodnoty polynomu $C=A\cdot B$, a pustíme na nì
+stejný algoritmus s~$\omega^{-1}$ (hodnoty $C$
+vlastnì budou v~algoritmu \uv{koeficienty polynomu}). Nakonec jen získané
+hodnoty vydìlíme $n$ a~máme chtìné koeficienty.
\s{Výsledek:} Pro $n= 2^k$ lze DFT na~${\bb C}^n$ spoèítat v~èase $\Theta(n
\log n)$ a~DFT$^{-1}$ takté¾.
$\Theta(n \log n)$ pro vyhodnocení, $\Theta(n)$ pro vynásobení a~$\Theta(n
\log n)$ pro pøevedení zpìt.
-\s{Pou¾ití:}
+\s{Pou¾ití FFT:}
\itemize\ibull
\:Násobení dlouhých èísel v~èase $\Theta(n \log n)$.
\endlist
-\s{Hardwarová implementace FFT}
+\s{Paralelní implementace FFT}
\figure{img.eps}{Pøíklad prùbìhu algoritmu na~vstupu velikosti 8}{3in}
+Zkusme si prùbìh algoritmu FFT znázornit graficky (podobnì, jako jsme kreslili
+hradlové sítì). Na~levé stranì obrázku se nachází vstupní vektor $x_0,\ldots,x_{n-1}$
+(v~nìjakém poøadí), na~pravé stranì pak výstupní vektor $y_0,\ldots,y_{n-1}$.
+Sledujme chod algoritmu pozpátku: Výstup spoèítáme z~výsledkù \uv{polovièních}
+transformací vektorù $x_0,x_2,\ldots,x_{n-2}$ a $x_1,x_3,\ldots,x_{n-1}$.
+Èerné krou¾ky pøitom odpovídají výpoètu lineární kombinace $a+\omega^kb$,
+kde $a,b$ jsou vstupy krou¾ku a $k$~nìjaké pøirozené èíslo závislé na poloze
+krou¾ku. Ka¾dá z~polovièních transformací se poèítá analogicky z~výsledkù
+transformace velikosti $n/4$ atd. Celkovì výpoèet probíhá v~$\log_2 n$ vrstvách
+po~$\Theta(n)$ operacích.
-\>Obrázek ukazuje zapojení kombinaèního obvodu pro DFT pro vstup velikosti~8.
-Hladin bude v¾dy $\log_2 n$, tj. v~na¹em pøípadì $\log_2 8 = 3$ hladiny.
+Jeliko¾ operace na~ka¾dé vrstvì probíhají na sobì nezávisle, mù¾eme je poèítat
+paralelnì. Ná¹ diagram tedy popisuje hradlovou sí» pro paralelní výpoèet FFT
+v~èase $\Theta(\log n\cdot T)$ a prostoru $\O(n\cdot S)$, kde $T$ a~$S$ znaèí
+èasovou a prostorovou slo¾itost výpoètu lineární kombinace dvou komplexních èísel.
-\>Podívejme se na~pravou èást obrázku, tedy výstup celého obvodu. Èerná koleèka
-pøedstavují podobvody, rovnice vedle nich operaci, kterou provádìjí. Hodnoty
-$y_j$ znaèí hodnotu polynomu $P$ v~bodì $\omega^j$ kde $\omega^j$ je $j-tá$
-mocnina primitivní $n$-té odmocniny z jednièky. K jejímu spoètení ale
-potøebujeme znát hodnoty $s_k$ a~$l_k$ kde $k$ je z intervalu $[0, {n/2} -1]$
-a~$s_k$ a~$l_k$ jsou hodnoty polynomu stupnì ${n/2}$ v~bodì $\omega^{2k}$.
-V polynomu $s$ jsou sudé koeficienty a~v polynomu $l$ liché koeficienty
-polynomu $P$. Vidíme, ¾e se jedná pøesnì o~ná¹ rekurzivní algoritmus pro
-poèítání FFT a~tímto zpùsobem postavíme celou sí».
-\>Tímto obvodem jsme tedy získali nerekurzivní algoritmus pro poèítání FFT.
-V¹imìme si poøadí vstupních hodnot (koeficientù). Èísla jsou v~binárním tvaru
-0--7 pøeètená pozpátku. Pro pøedstavu jaké koeficienty polynomu $P$ se objevují
-v~rùzných hladinách, na~obrázku jsou naznaèena jejich èísla spolu s~pøíslu¹nými
-mocninami primitivní $n$-té odmocniny z jednièky.
+\s{Cvièení:} Doka¾te, ¾e permutace vektoru $x_0,\ldots,x_{n-1}$ odpovídá bitovému
+zrcadlení, tedy ¾e na pozici~$b$ shora se vyskytuje prvek $x_d$, kde~$d$ je
+èíslo~$b$ zapsané ve~dvojkové soustavì pozpátku.
-\s{Z~toho:}
+\s{Nerekurzivní FFT}
-\itemize\ibull
-\:Kombinaèní obvod pro DFT
-s~$\Theta(\log n)$ hladinami
-a $\Theta(n)$ hradly na~hladinì.
-\:Nerekurzivní algoritmus (postupujeme zleva) v~èase $\Theta(n \log n)$.
+Obvod z~pøedchozího obrázku také mù¾eme vyhodnocovat po~hladinách zleva doprava,
+èím¾ získáme elegantní nerekurzivní algoritmus pro výpoèet FFT v~èase $\Theta(n\log n)$
+a prostoru $\Theta(n)$:
-\endlist
-\bigskip
+\algo
+\algin $x_0,\ldots,x_{n-1}$
+\:Pro $j=0,\ldots,n-1$ polo¾íme $y_k\= x_{r(k)}$, kde $r$ je funkce bitového zrcadlení.
+\:Pøedpoèítáme tabulku $\omega^0,\omega^1,\ldots,\omega^{n-1}$.
+\:$b\= 1$ \cmt{velikost bloku}
+\:Dokud $b<n$, opakujeme:
+\::Pro $j=0,\ldots,n-1$ s~krokem~$2b$ opakujeme: \cmt{zaèátek bloku}
+\:::Pro $k=0,\ldots,b-1$ opakujeme: \cmt{pozice v~bloku}
+\::::$\alpha\=\omega^{nk/2b}$
+\::::$(y_{j+k},y_{j+k+b}) \= (y_{j+k}+\alpha\cdot y_{j+k+b}, y_{j+k}-\alpha\cdot y_{j+k+b})$.
+\::$b\= 2b$
+\algout $y_0,\ldots,y_{n-1}$
+\endalgo
-\>Nakonec dodejme, ¾e poèítat lze nejen nad tìlesem komplexních èísel, ale
-v podstatì nad ka¾dým komutativním tìlesem s~$n$-tou primitivní odmocninou
-(pøíkladem jsou tìlesa øádu $p = 2^k + 1$, $p$ prvoèíslo) èi dokonce
-komutativním okruhem s~multiplikativními inversemi pro øád vektoru
-a~primitivní odmocninu.
+\s{FFT v~koneèných tìlesech}
+
+Nakonec dodejme, ¾e Fourierovu transformaci lze zavést nejen nad tìlesem
+komplexních èísel, ale i v~nìkterých koneèných tìlesech, pokud zaruèíme
+existenci primitivní $n$-té odmocniny z~jednièky. Napøíklad v~tìlese ${\bb
+Z}_p$ pro prvoèíslo $p=2^k+1$ platí $2^k=-1$, tak¾e $2^{2k}=1$
+a $2^0,2^1,\ldots,2^{2k-1}$ jsou navzájem rùzná, tak¾e èíslo~2 je~primitivní
+$2k$-tá odmocnina z~jedné. To se nám ov¹em nehodí pro algoritmus FFT, jeliko¾
+$2k$ bude málokdy mocnina dvojky.
+
+Zachrání nás ov¹em algebraická vìta, která øíká, ¾e multiplikativní grupa\foot{To je
+mno¾ina v¹ech nenulových prvkù tìlesa s~operací násobení.}
+libovolného koneèného tìlesa je cyklická, tedy ¾e v¹echny nenulové prvky tìlesa lze
+zapsat jako mocniny nìjakého èísla~$g$ (generátoru). Napøíklad pro $p=2^{16}+1=65\,537$
+je jedním takovým generátorem èíslo~$3$. Jeliko¾ mezi èísly $g^1,g^2,\ldots,g^{p-1}$
+se musí ka¾dý nenulový prvek tìlesa vyskytnout právì jednou, je~$g$ primitivní
+$2^k$-tou odmocninou z~jednièky, tak¾e mù¾eme poèítat FFT pro libovolný vektor,
+jeho¾ velikost je mocnina dvojky men¹í nebo rovná $2^k$.\foot{Bli¾¹í prùzkum
+na¹ich úvah o~FFT dokonce odhalí, ¾e není ani potøeba tìleso. Postaèí libovolný
+komutativní okruh, ve~kterém existuje pøíslu¹ná primitivní odmocnina
+z~jednièky, její multiplikativní inverze (ta ov¹em existuje v¾dy, proto¾e
+$\omega^{-1} = \omega^{n-1}$) a multiplikativní inverze èísla~$n$. To nám
+poskytuje je¹tì daleko více volnosti ne¾ tìlesa, ale není snadné takové okruhy
+hledat.}
\bye
projects / ads2.git / blobdiff