6.4.2.1.1 : Algorithme de Strassen (fast 2x2)
La multiplication selon Strassen définit des coéficients intermédiaires :$$\begin{eqnarray*} M_1 & = & \left(A_{12} - A_{22}\right) \times \left(B_{21} + B_{22}\right) \\ M_2 & = & \left(A_{11} + A_{22}\right) \times \left(B_{11} + B_{22}\right) \\ M_3 & = & \left(A_{11} - A_{21}\right) \times \left(B_{11} + B_{12}\right) \\ M_4 & = & \left(A_{11} + A_{12}\right) \times B_{22} \\ M_5 & = & A_{11} ∗ \left(B_{12} - B_{22}\right) \\ M_6 & = & A_{22} ∗ \left(B_{21} - B_{11}\right) \\ M_7 & = & \left(A_{21} + A_{22}\right) \times B_{11} \\ \end{eqnarray*}$$
Enfin, le calcul final :
$$\begin{eqnarray*} C_{11} & = & M_1 + M_2 - M_4 + M_6 \\ C_{12} & = & M_4 + M_5 \\ C_{21} & = & M_6 + M_7 \\ C_{22} & = & M_2 - M_3 + M_5 - M_7 \end{eqnarray*}$$
Le calcul de Strassen utilise donc :
- $7$ multiplications
- $17$ additions
Sa complexité est de $O\left(N^{2.81}\right)$ au lieu de $O\left(N^3\right)$ .