3-strassen/3-strassen.tex

   1 \input ../lecnotes.tex
   2 \input epsf.tex
   3
   4 \prednaska{3}{Rozdìl a panuj II}{(zapsali Luká¹ Hermann, Vincent Krí¾, Oto Petøík)}
   5
   6 \h{Násobení matic n$\times$n a Strassenùv algoritmus}
   7
   8 Nejdøíve si pøipomeneme definici násobení dvou ètvercových matic typu $n \times n$. Platí, ¾e prvek v $i$-tém øádku a $j$-tém sloupci výsledné matice $Z$ se rovná standardnímu skalárnímu souèinu $i$-tého øádku první matice $X$ a $j$-tého sloupce druhé matice~$Y$. Formálnì zapsáno:
   9
  10 $$ Z_{ij} = \sum_{k=1}^n X_{ik} \cdot Y_{kj} $$
  11
  12 \figure{nasobeni-matic.eps}{Násobení matic}{\epsfxsize}
  13
  14 Algoritmus, který by násobil matice podle této definice, by mìl èasovou slo¾itost $ \Theta(n^3) $, proto¾e poèet prvkù ve výsledné matici je $n^2$ a jeden skalární souèin vektorù dimenze $n$ vy¾aduje lineární poèet operací.
  15
  16 My se s touto èasovou slo¾itostí ov¹em nespokojíme a budeme postupovat podobnì jako pøi vylep¹ování algoritmu na násobení velkých èísel. Bez újmy na obecnosti pøedpokládejme, ¾e budeme násobit dvì matice typu $n \times n$, kde $n=2^k, k \in \bb N$. Obì tyto matice rozdìlíme na ètvrtiny a tyto èásti postupnì oznaèíme u matice $X$ - $A$, $B$, $C$ a $D$, u matice $Y$ - $P$, $Q$, $R$ a $S$. Z definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice $Z$ mù¾eme zapsat pomocí èástí násobených matic. Levá horní ètvrtina bude odpovídat výsledku operací $AP+BR$, pravá horní ètvrtina bude $AQ+BS$, levá dolní $CP+DR$ a zbylá $CQ+DS$ (viz obrázek).
  17
  18 \figure{nasobeni-matic-2.eps}{Násobení rozètvrcených matic}{\epsfxsize}
  19
  20 \break
  21
  22 Pøevedli jsme tedy problém násobení ètvercových matic øádu $n$ na násobení ètvercových matic øádu ${n/2}$. Tímto rozdìlováním bychom mohli pokraèovat, dokud bychom se nedostali na matice øádu 1, jejich¾ vynásobení je triviální. Dostali jsme tedy klasický algoritmus typu {\it rozdìl a panuj}. Pomohli jsme si ale nìjak ? V ka¾dém kroku provádíme 8 násobení matic polovièního øádu a navíc konstantní poèet operací na $n^2$ prvcích. Dostáváme tedy rekurentní zápis èasové slo¾itosti:
  23
  24 $$ T(n) = 8\ T\left({n \over 2}\right) + \O(n^2). $$
  25
  26 Po aplikaci Master Theoremu pak lehce dojdeme k závìru, ¾e slo¾itost je stále $\Theta(n^3)$, tedy stejná jako pøi násobení matic z definice. Zdánlivì jsme si tedy nepomohli, ale stejnì jako tomu bylo u násobení velkých èísel, i teï mù¾eme zredukovat poèet násobení matic polovièního øádu, které nejvíce ovlivòuje èasovou slo¾itost algoritmu. Není to bohu¾el nic triviálního, a proto si radìji rovnou øekneme správné øe¹ení. Jedná se o Strassenùv algoritmus, který redukuje potøebný poèet násobení na~7, a je¹tì pøed tím, ne¾ si uká¾eme, jak funguje, doká¾eme si, jak nám to s èasovou slo¾itostí vlastnì pomù¾e:
  27
  28 $$ T(n) = 7\ T\left({n \over 2}\right) + \O(n^2) \Longrightarrow \O(n^{log_2 7}) = \O(n^{2.808}). $$
  29
  30 Výsledná slo¾itost Strassenova algoritmu je tedy pøibli¾nì $\O(n^{2.808})$, co¾ je sice malé, ale pro velké matice znatelné zlep¹ení oproti algoritmu vycházejícího pøímo z~definice.
  31
  32 % zacatek slidu z prednasky
  33 \s{Lemma:} Strassenùv algoritmus
  34
  35 \def\\{\noalign{\vskip 7pt}}
  36
  37 $$
  38 \pmatrix{A & B \cr\\ C & D \cr}
  39 \cdot
  40 \pmatrix{P & Q \cr\\ R & S \cr}
  41 =
  42 \pmatrix{
  43 T_1 + T_4 - T_5 + T_7 &
  44 T_3 + T_5 \cr\\
  45 T_2 + T_4 &
  46 T_1 - T_2 + T_3 + T_6 \cr
  47 },$$
  48
  49 kde:
  50
  51 $$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
  52 T_1 = (A+D)\cdot(P+S)           & T_5 = (A+B)\cdot S \cr\\
  53 T_2 = (C+D)\cdot P              & T_6 = (C-A)\cdot (P+Q) \cr\\
  54 T_3 = A\cdot(Q-S)               & T_7 = (B-D)\cdot (R+S) \cr\\
  55 T_4 = D\cdot(R-P)                                        \cr
  56 }}$$
  57
  58 \medskip
  59
  60 \proof Do ètvercù $4 \times 4$ si napí¹eme znaky $+$ nebo $-$ podle toho, jestli se pøi výpoètu dané matice pøièítá nebo odeèítá pøíslu¹ný souèin dvou matic. Øádky znamenají matice $A$, $B$, $C$ a $D$ a sloupce znaèí matice $P$, $Q$, $R$ a $S$. Pokud se tedy v prvním øádku a prvním sloupci vyskytuje znak $+$, znamená to ¾e pøièteme souèin matic $A$~a~$P$. Nejdøíve si spoèítáme pomocné matice $T_1$ a¾ $T_7$ a z nich pak dopoèítáme, co bude na pøíslu¹ných místech ve výsledné matici.
  61
  62 \def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}}
  63 \def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi}
  64 \def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
  65 \def\qq#1#2#3#4{{\offinterlineskip\vcenter{\halign{\vrule ##\vrule \cr\noalign{\hrule}\zz#1\cr\zz#2\cr\zz#3\cr\zz#4\cr\noalign{\hrule}}}}}
  66
  67 $$
  68 T_1 = \qq{+..+}{....}{....}{+..+} \qquad
  69 T_2 = \qq{....}{....}{+...}{+...} \qquad
  70 T_3 = \qq{.+.-}{....}{....}{....} \qquad
  71 T_4 = \qq{....}{....}{....}{-.+.}
  72 $$
  73 $$
  74 T_5 = \qq{...+}{...+}{....}{....} \qquad
  75 T_6 = \qq{--..}{....}{++..}{....} \qquad
  76 T_7 = \qq{....}{..++}{....}{..--}
  77 $$
  78
  79 \medskip
  80
  81 \def\\{\noalign{\vskip 7pt}}
  82 $$
  83 \eqalign{
  84 T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
  85 T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
  86 T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
  87 T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
  88 }
  89 $$
  90
  91 % konec slidu z prednasky
  92
  93 Jak je vidìt, výsledná matice je tvoøena stejnými èástmi jako pøi obyèejném násobení. Touto kapitolou jsme tedy dokázali následující vìtu:
  94
  95 \s{Vìta:}
  96 Násobení matic $n \times n$ má èasovou slo¾itost v nejhor¹ím pøípadì $\O(n^{2.808})$. \qed
  97
  98 \s{Poznámka:}
  99 Zatím nejlep¹í dokázaný algoritmus má èasovou slo¾itost $\O(n^{2.376})$, $ $ ov¹em s velkou multiplikativní konstantou.
 100
 101 \h{Hledání $k$-tého nejmen¹ího prvku (mediánu)}
 102
 103 V tomto oddílu se budeme zabývat tím, jak co nejrychleji najít v jakékoli posloupnosti $n$ èísel $k$-tý nejmen¹í prvek popøípadì medián. Pro ty, kdo medián neznají, tu máme definici:
 104
 105 \s{Definice:}
 106 Medián posloupnosti $a_1, a_2,\ldots , a_n$ je takové $m=a_i$, kde nejvý¹e $n/2$ prvkù je men¹ích ne¾ $m$ a nejvý¹e $n/2$ prvkù je vìt¹ích ne¾ $m$.
 107
 108 Nejjednodu¹¹ím øe¹ením by urèitì bylo celou posloupnost nejdøíve setøídit a pak u¾ jednodu¹e vyhmátnout po¾adovaný prvek. To bychom dokázali v celkem slu¹ném èase $\O(n\log n)$, ale u¾ teï mù¾eme prozradit, ¾e to jde v èase $\O(n)$. Jak?
 109
 110 Pou¾ívat budeme metodu {\it rozdìl a panuj}. Nìjakým zpùsobem si zvolíme jeden prvek posloupnosti, který nazveme {\it pivot}. Poté rozdìlíme zadanou posloupnost na~tøi disjunktní mno¾iny. Do první dáme v¹echny prvky men¹í ne¾ pivot, do druhé stejné jako pivot a do tøetí vìt¹í ne¾ pivot. Tímto máme zaji¹tìno, ¾e prvky z první mno¾iny jsou urèitì men¹í ne¾ prvky z druhé a ty ne¾ prvky z tøetí.
 111
 112 O tom, jak jsou prvky uspoøádány uvnitø tìchto mno¾in, ale nic nevíme. V posledním kroku na¹eho algoritmu se pak rozhodneme, na kterou mno¾inu svùj algoritmus rekurzivnì zavoláme. Pokud je $k$ men¹í ne¾ velikost první mno¾iny, pokraèujeme v první mno¾inì, pokud je $k$ men¹í ne¾ souèet velikostí první a druhé mno¾iny, pak hledaným prvkem je právì vybraný pivot a algoritmus skonèí, a nakonec pokud ani jedna podmínka splnìna nebyla, pustíme se do hledání ve tøetí mno¾inì, ov¹em u¾ nehledáme $k$-tý nejmen¹í prvek, ale $l$-tý, kde $l$ se rovná $k$ minus velikost prvních dvou mno¾in. Pro vìt¹í názornost zapí¹eme tento algoritmus pøedhlednìji:
 113
 114
 115 {\bo Select($k,X$):} (Hledání $k$-tého nejmen¹ího prvku v mno¾ine $X$)
 116 \algo
 117
 118
 119 \:Jestli¾e $\vert X\vert <= 1$, pak triviálnì o¹etøíme.
 120 \:Zvolíme pivota $p \in X$.
 121 \:Rozdìlíme mno¾inu X na tøi podmno¾iny: $M = \{x \in X; x < p\},$ $ P = \{x \in X; x = p\}, V = \{x \in X; x > p\}$.
 122 \:Jestli¾e $k <= \vert M\vert$, pak vra» výsledek funkce \<Select>($k$, $M$).
 123 \:Jestli¾e $k <= \vert M\vert + \vert P\vert$, pak vra» pivota $p$.
 124 \:Jinak vra» výsledek funkce \<Select>($k - \vert M\vert - \vert P\vert, V$).
 125 \endalgo
 126
 127 Na první pohled je vidìt, ¾e se algoritmus zastaví (vstup se v¾dy zmen¹í alespoò o 1) a ¾e vydá v¾dy správný výsledek. Jak je to ov¹em s èasovou slo¾itostí? Rozdìlení do mno¾in a podmínky v druhém a tøetím kroku mají lineární slo¾itost, èemu¾ se nevyhneme. Pøi ne¹»astné volbì pivota se nám mù¾e stát, ¾e poèet rekurencí mù¾e být a¾ $n$, tedy celková slo¾itost v nejhor¹ím pøípadì je $\Theta(n^2)$, èím¾ jsme si oproti prostému setøídìní je¹tì pohor¹ili. Co s tím? Jak je vidìt, velmi dùle¾itá je volba pivota. Tu mù¾eme provést nìkolika zpùsoby:
 128
 129 a) Pivot by se v setøídìné posloupnosti vyskytoval uprostøed, vstup by se tedy stále pùlil. Èasovou slo¾itost vypoèteme z rekurentního zápisu:
 130
 131 $$ T(n) = T\left({n \over 2}\right) + \O(n) = \O\left(n + {n \over 2} + {n \over 4} + \dots\right) = \O(n). $$
 132
 133 To by bylo sice skvìlé, ale nalezení takového pivota je vlastnì vyøe¹ení úlohy hledání mediánu, o co¾ se sna¾íme. Tedy jsme si vùbec nepomohli.
 134
 135 \break
 136
 137 b) Pivot by se v setøídìné posloupnosti náchazel v prostøedních dvou ètvrtinách (nazvìme tento prvek "l¾imedián"). Tím bychom v ka¾dém kroku urèitì odstranili mno¾inu velikosti ètvrtiny vstupu. Èasová slo¾itost tohoto øe¹ení by byla:
 138
 139 $$ T(n) = T\left({3 \over 4}n\right) + \O(n) = \O\left(n + {3 \over 4}n + {9 \over 16}n + \dots\right) = \O(n). $$
 140
 141 Tímto bychom tedy také dosáhli lineární èasové slo¾itosti. Ale jak vybrat pivota tak, aby se nacházel v prostøedních dvou ètvrtinách, aby nám nám to nepokazilo lineární slo¾itost?
 142
 143 c) Pivot bude v¾dy prostøední prvek zadané posloupnosti. V tomto pøípadì je zøejmé, ¾e existují urèité vstupy, pro které bude èasová slo¾itost $\Omega(n^2)$, ale v~prùmìrném pøípadì, bude èasová slo¾itost $\O(n)$, co¾ doká¾eme v pøí¹tí kapitole.
 144
 145 d) Pivot bude náhodnì zvolený prvek zadané posloupnosti. Tímto dosáhneme nìèeho podobného jako v pøedchozím pøípadì, ale u¾ nebude existovat vstup, pro který by èasová slo¾itost byla $\Omega(n^2)$, jen nìkteré prùbìhy tohoto algoritmu na rùzných vstupech budou trvat takto dlouho. Prùmìrná èasová slo¾itost je tedy zase $O(n)$.
 146
 147 My se ale nespokojíme pouze s lineární prùmìrnou èasovou slo¾itostí. Chceme dosáhnout lineární slo¾itosti i v nejhor¹ím pøípadì. Ne¾ si ale prozradíme takové øe¹ení, rozmyslíme si, ¾e u¾ teï známe 3 èasové slo¾itosti, i kdy¾ ne v¹echny je¹tì umíme analyzovat. Je to èasová slo¾itost v nejhor¹ím pøídadì, v prùmìrném pøípadì pøes v¹echny vstupy a v prùmìrném pøípadì pøes v¹echny bìhy programu. V¹imnìte si hlavnì rozdílu posledních dvou.
 148
 149 A nyní u¾ slibované øe¹ení s lineární nejhor¹í èasovou slo¾itostí. Vyjdeme z~mo¾nosti b), tedy pokusíme se najít takového pivota, který by na pøí¹tí krok zaruèenì omezil velikost analyzované mno¾iny. Dosáhneme toho tímto algoritmem:
 150
 151 \s{Volba pivota:}
 152 \algo
 153 \:Rozdìlíme vstup na pìtice \dots $\O(n)$
 154 \:Spoèteme medián ka¾dé pìtice \dots $\O(n)$
 155 \:Spoèteme medián mediánù pìtic tak, ¾e rekurzivnì zavoláme tentý¾ algoritmus \<Select>($n / 10$, {mediány pìtic}) a to je pivot.
 156 \endalgo
 157
 158 Abychom dokázali, ¾e tento algoritmus bude mít opravdu lineární èasovou slo¾itost, musíme si nejdøíve dokázat následující lemma:
 159
 160 \s{Lemma:} V ka¾dém kroku vypadne alespoò ${3/10}\cdot n$ prvkù.
 161
 162 \proof Ten provedeme obrázkem. Pøedstavme si vybrané pìtice seøazené podle velikosti od nejvìt¹ího prvku a zakresleme je do sloupcù. Jejich mediány tedy vyplòují prostøední øadu. Tyto pìtice pak seøaïme podle velikosti jejich mediánù (nejmen¹í vlevo). Hledaný pivot se tedy nachází (pokud pøedpokládáme pro jednoduchost lichý poèet pìtic) pøesnì uprostøed. O prvcích nad pivotem a napravo od nìj mù¾eme urèitì øíct, ¾e jsou vìt¹í nebo rovny pivotu, prvky pod ním a nalevo od nìj jsou zase urèitì men¹í nebo rovny pivotu.
 163
 164 Podle konstrukce algoritmu tedy zaruèenì vypadne jedna nebo druhá skupina prvkù. Obì tyto skupiny pøitom obsahují, jak je vidìt z obrázku, alespoò $3/10 \cdot n$ prvkù.
 165 \qed
 166
 167 \figure{petice.eps}{Pìtice}{125mm}
 168
 169 Nyní u¾ se tedy mù¾eme pustit do výpoètu èasové slo¾itosti. V ka¾dém kroku funkce zavolá sama sebe nejdøíve na vstup velikosti ${n \over 5}$ a poté na vstup velikosti nejvý¹e ${7 \over 10}n$. Ostatní operace zùstávají lineární. Èasovou slo¾itost v nejhor¹ím pøípadì tedy mù¾eme zapsat rekurentním vzorcem:
 170
 171 $$ T(n) = \O(n) + T\left({n \over 5}\right) + T\left({7 \over 10}n\right). $$
 172
 173 Tento rekurentní vzorec ale zatím neumíme obecnì øe¹it. Mohli bychom ho postupnì rozepsat, ale trvalo by dlouho, ne¾ bychom z toho nìco vykoukali. Lep¹í bude rovnou dokázat, ¾e tento rekurentní vzorec odpovídá lineární slo¾itosti, zkusíme tedy dosadit $T(n) = cn$:
 174
 175 $$ cn = n + {1 \over 5}cn + {7 \over 10}cn \quad\Longleftrightarrow\quad c = 10. $$
 176
 177 Tímto jsme tedy dokázali, ¾e èasová slo¾itost tohoto algoritmu v nejhor¹ím pøípadì je $\O(n)$.
 178 Jeliko¾ to rychleji urèitì není mo¾né, mù¾eme na závìr této kapitoly zformulovat tuto vìtu:
 179
 180 \s{Vìta:} Hledání k-tého nejmen¹ího prvku v posloupnosti délky n má èasovou slo¾itost v nejhor¹ím pøípadì $\Theta(n)$. \qed
 181
 182 \bye