6 \slide{Strassenùv algoritmus: vzorce}
8 \def\\{\noalign{\vskip 7pt}}
11 \pmatrix{A & B \cr\\ C & D \cr}
13 \pmatrix{P & Q \cr\\ R & S \cr}
16 T_1 + T_4 - T_5 + T_7 &
19 T_1 - T_2 + T_3 + T_6 \cr
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\\
33 7 násobení místo 8 $\Rightarrow$ èasová slo¾itost $\O(n^{\log_2 7}) = \O(n^{2.808})$.
37 [Zatím nejlep¹í výsledek: $\O(n^{2.376})$ \uv{s~opravdu velkým~$\O$.}]
41 \slide{Strassenùv algoritmus: dùkaz}
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}}}}}
49 T_1 = \qq{+..+}{....}{....}{+..+} \qquad
50 T_2 = \qq{....}{....}{+...}{+...} \qquad
51 T_3 = \qq{.+.-}{....}{....}{....} \qquad
52 T_4 = \qq{....}{....}{....}{-.+.}
55 T_5 = \qq{...+}{...+}{....}{....} \qquad
56 T_6 = \qq{--..}{....}{++..}{....} \qquad
57 T_7 = \qq{....}{..++}{....}{..--}
62 \def\\{\noalign{\vskip 7pt}}
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