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)$ .