8.4 Strassenův algoritmus
- Na stejném principu je postavené i zrychlení maticového násobení.
- Rozdělíme matice na čtvrtiny (předpokládáme \(A, B, C ∈ \mathbb{R}^{n×n}\) pro \(n = 2^k\)).
\[ \left(
\begin{matrix}
A_{11} & A_{12} \\
A_{21} & A_{22}\\
\end{matrix}
\right) \cdot \left(
\begin{matrix}
B_{11} & B_{12} \\
B_{21} & B_{22}\\
\end{matrix}
\right) = \left(
\begin{matrix}
C_{11} & C_{12} \\
C_{21} & C_{22}\\
\end{matrix}
\right)
\]
\[ \begin{align*}
M_1 &= (A_{11} + A_{22}) \cdot (B_{11} + B_{22}) \\
M_2 &= (A_{21} + A_{22}) \cdot B_{11} \\
M_3 &= A_{11} \cdot (B_{12} - B_{22}) \\
M_4 &= A_{22} \cdot (B_{21} - B_{11}) \\
M_5 &= (A_{11} + A_{12}) \cdot B_{22} \\
M_6 &= (A_{21} - A_{11}) \cdot (B_{11} + B_{12}) \\
M_7 &= (A_{12} - A_{22}) \cdot (B_{21} + B_{22})
\end{align*}
\]
\[ A \cdot B =
\begin{pmatrix}
M_1 + M_4 - M_5 + M_7 & M_3 - M_5 \\
M_2 + M_4 & M_1 - M_2 + M_3 + M_6
\end{pmatrix}\]
Věta 8.4
Složitost Strassenova algoritmu
Složitost Strassenova algoritmu je \(O(n^{log_2{7}})\).
Další vylepšení na podobném principu
- Ladermanův algoritmus (matice \(3 ×3\); celkem \(23\) násobení)
- ...
- AlphaTensor (DeepAI)
- pro matice \(4 ×4\) stačí \(47\) násobení (předchozí výsledek 49; 1969)
- pro matice \(5 ×5\) stačí \(96\) násobení (předchozí výsledek 98)