6.4.2.1 : Multiplication rapide de matrice 2x2
La question de la mutiplication de matrices $2\times 2$
sucite l'intéret depuis 1969.La table 1 montre quelques algorithmes de multiplication rapide de matrices $2\times 2$ .
| Année | Exposant complexité | Algorithmes |
| $< 1969$ | $3$ | Classique |
| $1969$ | $2.81$ | Strassen |
| $1978$ | $2.79$ | Pan |
| $1979$ | $2.78$ | Bini et al. |
| $1981$ | $2.55$ | Schonhage |
| $1982$ | $2.50$ | Pan, Romani, Coppersmith, Winograd |
| $1987$ | $2.48$ | Strassen |
| $1987$ | $2.38$ | Coppersmith, Winograd |
Table 1 : Différents algorithmes datés de multiplications de matrice $2\times 2$
et leur complexité.
Dans ce qui suit, nous allons considérer la multiplication de matrices $2\times 2$ suivante :
$$\begin{eqnarray*} C & = & A \times B \\ \left(\begin{matrix}C_{11} & C_{12} \\ C_{21} & C_{22}\end{matrix}\right) & = & \left(\begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22}\end{matrix}\right) \times \left(\begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22}\end{matrix}\right) \end{eqnarray*}$$
Qui se développe sous la forme :
$$\begin{eqnarray*} C_{11} & = & A_{11}B_{11} + A_{12}B_{21} \\ C_{12} & = & A_{11}B_{12} + A_{12}B_{22} \\ C_{21} & = & A_{21}B_{11} + A_{22}B_{21} \\ C_{22} & = & A_{21}B_{12} + A_{22}B_{22} \end{eqnarray*}$$
Ce calcul utilise donc :
- $8$ multiplications
- $4$ additions
Sa complexité est en $O\left(N^3\right)$ .