slides/strassen.tex

   1 \input slidemac.tex
   2
   3 \language=\czech
   4 \chyph
   5
   6 \slide{Strassenùv algoritmus: vzorce}
   7
   8 \def\\{\noalign{\vskip 7pt}}
   9
  10 $$
  11 \pmatrix{A & B \cr\\ C & D \cr}
  12 \cdot
  13 \pmatrix{P & Q \cr\\ R & S \cr}
  14 =
  15 \pmatrix{
  16 T_1 + T_4 - T_5 + T_7 &
  17 T_3 + T_5 \cr\\
  18 T_2 + T_4 &
  19 T_1 - T_2 + T_3 + T_6 \cr
  20 },$$
  21
  22 kde:
  23
  24 $$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
  25 T_1 = (A+D)\cdot(P+S)           & T_5 = (A+B)\cdot S \cr\\
  26 T_2 = (C+D)\cdot P              & T_6 = (C-A)\cdot (P+Q) \cr\\
  27 T_3 = A\cdot(Q-S)               & T_7 = (B-D)\cdot (R+S) \cr\\
  28 T_4 = D\cdot(R-P)                                        \cr
  29 }}$$
  30
  31 \medskip
  32
  33 7 násobení místo 8 $\Rightarrow$ èasová slo¾itost $\O(n^{\log_2 7}) = \O(n^{2.808})$.
  34
  35 \medskip
  36
  37 [Zatím nejlep¹í výsledek: $\O(n^{2.376})$ \uv{s~opravdu velkým~$\O$.}]
  38
  39 \endslide
  40
  41 \slide{Strassenùv algoritmus: dùkaz}
  42
  43 \def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}}
  44 \def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi}
  45 \def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
  46 \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}}}}}
  47
  48 $$
  49 T_1 = \qq{+..+}{....}{....}{+..+} \qquad
  50 T_2 = \qq{....}{....}{+...}{+...} \qquad
  51 T_3 = \qq{.+.-}{....}{....}{....} \qquad
  52 T_4 = \qq{....}{....}{....}{-.+.}
  53 $$
  54 $$
  55 T_5 = \qq{...+}{...+}{....}{....} \qquad
  56 T_6 = \qq{--..}{....}{++..}{....} \qquad
  57 T_7 = \qq{....}{..++}{....}{..--}
  58 $$
  59
  60 \medskip
  61
  62 \def\\{\noalign{\vskip 7pt}}
  63 $$
  64 \eqalign{
  65 T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
  66 T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
  67 T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
  68 T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
  69 }
  70 $$
  71
  72 \endslide
  73
  74 \end