Algorithme de Winograd (fast 2x2)

6.4.2.1.2 : Algorithme de Winograd (fast 2x2)

La méthode de Winograd utilise plus de calcul intermédiaires pour décomposer le calcul des coéfficients intermédiaires $M$ de Strassen :

$$\begin{eqnarray*} S_1 & = & A_{21} + A_{22} \\ S_2 & = & S_1 - A_{11} \\ S_3 & = & A_{11} - A_{21} \\ S_4 & = & A_{12} - S_2 \\ S_5 & = & B_{12} - B_{11} \\ S_6 & = & B_{22} - S_5 \\ S_7 & = & B_{22} - B_{12} \\ S_8 & = & S_6 - B_{21} \\ M_1 & = & S_2 \times S_6 \\ M_2 & = & A_{11} \times B_{11} \\ M_3 & = & A_{12} \times B_{21} \\ M_4 & = & S_3 \times S_7 \\ M_5 & = & S_1 \times S_5 \\ M_6 & = & S_4 \times B_{22} \\ M_7 & = & A_{22} \times S_8 \\ T_1 & = & M_1 + M_2 \\ T_2 & = & T_1 + M_4 \end{eqnarray*}$$

Ce qui donne les résultats suivants :

$$\begin{eqnarray*} C_{11} = M_2 + M_3 \\ C_{12} = T_1 + M_5 + M_6 \\ C_{21} = T_2 - M_7 \\ C_{22} = T_2 + M_5 \end{eqnarray*}$$

Le calcul de Winograd utilise donc :

$7$ multiplications
$15$ additions

Sa complexité est $O\left(N^{2.80}\right)$ , donc légèrement meilleure que l'algorithme de Strassen (voir section 6.4.2.1.1).