6.4.2.2 : Multiplication rapide de matrice 3x3

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_{13} \\ C_{21} & C_{22} & C_{23} \\ C_{31} & C_{32} & C_{33}\end{matrix}\right) & = & \left(\begin{matrix}A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33}\end{matrix}\right) \times \left(\begin{matrix}B_{11} & B_{12} & B_{13} \\ B_{21} & B_{22} & B_{23} \\ B_{31} & B_{32} & B_{33}\end{matrix}\right) \end{eqnarray*}$$

Qui se développe sous la forme :

$$\begin{eqnarray*} C_{11} & = & A_{11}B_{11} + A_{12}B_{21} + A_{13}B_{31} \\ C_{12} & = & A_{11}B_{12} + A_{12}B_{22} + A_{13}B_{32} \\ C_{13} & = & A_{11}B_{13} + A_{12}B_{23} + A_{13}B_{33} \\ C_{21} & = & A_{21}B_{11} + A_{22}B_{21} + A_{23}B_{31} \\ C_{22} & = & A_{21}B_{12} + A_{22}B_{22} + A_{23}B_{32} \\ C_{23} & = & A_{21}B_{13} + A_{22}B_{23} + A_{23}B_{33} \\ C_{31} & = & A_{31}B_{11} + A_{32}B_{21} + A_{33}B_{31} \\ C_{32} & = & A_{31}B_{12} + A_{32}B_{22} + A_{33}B_{32} \\ C_{33} & = & A_{31}B_{13} + A_{32}B_{23} + A_{33}B_{33} \end{eqnarray*}$$

Ce calcul utilise donc :

  • $27$ multiplications
  • $18$ additions


Sa complexité est en $O\left(N^3\right)$ .