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$ písmeny $A$, $B$, $C$ a $D$, u matice $Y$ písmeny $P$, $Q$, $R$ a $S$. Z definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice $Z$ mù¾eme zapsat pomocí souèinù èá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) = 8T\left({n \over 2}\right) + \O(n^2). $$
  25
  26 Pou¾itím Master Theoremu 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) = 7T\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 $\O(n^{2.808})$, co¾ je sice malé, ale pro velké matice znatelné zlep¹ení oproti algoritmu vycházejícímu pøímo z~definice.
  31
  32 \s{Lemma:} (vzorce pro násobení blokových matic ve~Strassenovì algoritmu)
  33
  34 \def\\{\noalign{\vskip 7pt}}
  35
  36 $$
  37 \pmatrix{A & B \cr\\ C & D \cr}
  38 \cdot
  39 \pmatrix{P & Q \cr\\ R & S \cr}
  40 =
  41 \pmatrix{
  42 T_1 + T_4 - T_5 + T_7 &
  43 T_3 + T_5 \cr\\
  44 T_2 + T_4 &
  45 T_1 - T_2 + T_3 + T_6 \cr
  46 },$$
  47
  48 kde:
  49
  50 $$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
  51 T_1 = (A+D)\cdot(P+S)           & T_5 = (A+B)\cdot S \cr\\
  52 T_2 = (C+D)\cdot P              & T_6 = (C-A)\cdot (P+Q) \cr\\
  53 T_3 = A\cdot(Q-S)               & T_7 = (B-D)\cdot (R+S) \cr\\
  54 T_4 = D\cdot(R-P)                                        \cr
  55 }}$$
  56
  57 \medskip
  58
  59 \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.
  60
  61 \def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}}
  62 \def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi}
  63 \def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
  64 \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}}}}}
  65
  66 $$
  67 T_1 = \qq{+..+}{....}{....}{+..+} \qquad
  68 T_2 = \qq{....}{....}{+...}{+...} \qquad
  69 T_3 = \qq{.+.-}{....}{....}{....} \qquad
  70 T_4 = \qq{....}{....}{....}{-.+.}
  71 $$
  72 $$
  73 T_5 = \qq{...+}{...+}{....}{....} \qquad
  74 T_6 = \qq{--..}{....}{++..}{....} \qquad
  75 T_7 = \qq{....}{..++}{....}{..--}
  76 $$
  77
  78 \medskip
  79
  80 \def\\{\noalign{\vskip 7pt}}
  81 $$
  82 \eqalign{
  83 T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
  84 T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
  85 T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
  86 T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
  87 }
  88 $$
  89
  90 % konec slidu z prednasky
  91
  92 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:
  93
  94 \s{Vìta:}
  95 Strassenùv algoritmus pro násobení matic $n \times n$ má èasovou slo¾itost
  96 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 O tom, jak jsou prvky uspoøádány uvnitø tìchto mno¾in, ale nic nevíme.
 112
 113 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 formálnìji:
 114
 115 {\bo Select($k,X$):} (Hledání $k$-tého nejmen¹ího prvku v mno¾ine $X$)
 116 \algo
 117 \:Jestli¾e $\vert X\vert \le 1$, vyøe¹íme triviálnì.
 118 \:Zvolíme pivota $p \in X$.
 119 \: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\}$.
 120 \:Jestli¾e $k \le \vert M\vert$, vrátím výsledek funkce \<Select>($k$, $M$).
 121 \:Jestli¾e $k \le \vert M\vert + \vert P\vert$, vrátíme pivota $p$.
 122 \:Jinak vrátíme výsledek funkce \<Select>($k - \vert M\vert - \vert P\vert, V$).
 123 \endalgo
 124
 125 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:
 126
 127 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:
 128
 129 $$ T(n) = T\left({n \over 2}\right) + \O(n) = \O\left(n + {n \over 2} + {n \over 4} + \dots\right) = \O(n). $$
 130
 131 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.
 132
 133 \break
 134
 135 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:
 136
 137 $$ 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). $$
 138
 139 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?
 140
 141 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.
 142
 143 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)$.
 144
 145 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.
 146
 147 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:
 148
 149 \s{Volba pivota:}
 150 \algo
 151 \:Rozdìlíme vstup na pìtice \dots $\O(n)$
 152 \:Spoèteme medián ka¾dé pìtice \dots $\O(n)$
 153 \: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.
 154 \endalgo
 155
 156 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:
 157
 158 \s{Lemma:} V ka¾dém kroku vypadne alespoò ${3/10}\cdot n$ prvkù.
 159
 160 \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.
 161
 162 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ù.
 163 \qed
 164
 165 \figure{petice.eps}{Pìtice}{125mm}
 166
 167 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:
 168
 169 $$ T(n) = \O(n) + T\left({n \over 5}\right) + T\left({7 \over 10}n\right). $$
 170
 171 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$:
 172
 173 $$ cn = n + {1 \over 5}cn + {7 \over 10}cn \quad\Longleftrightarrow\quad c = 10. $$
 174
 175 Tímto jsme tedy dokázali, ¾e èasová slo¾itost tohoto algoritmu v nejhor¹ím pøípadì je $\O(n)$.
 176 Jeliko¾ to rychleji urèitì není mo¾né, mù¾eme na závìr této kapitoly zformulovat tuto vìtu:
 177
 178 \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
 179
 180 \bye