6.4.2.2.1 : Algorithme de Laderman (fast 3x3)
Cet algorithme, découvert en 1975 par Laderman, utilise le même principe que celui de Winograd (voir section 6.4.2.1) pour des matrices 3x3 [8]A NONCOMMUTATIVE ALGORITHM FOR MULTIPLYING 3 x 3 MATRICES USING 23 MULTIPLICATIONS, October 9, 1975, JULIAN D. LADERMAN.

De la même manière que précédemment, nous utiliserons des valeurs temporaires :



$$\begin{eqnarray*} M_1 & = & \left(A_{11} + A_{12} + A_{13} - A_{21} - A_{22} - A_{32} - A_{33}\right)B_{22} \\ M_2 & = & \left(A_{11} - A_{21}\right)\left(A_{22} - A_{12}\right) \\ M_3 & = & A_{22}\left(- B_{11} + B_{12} + B_{21} - B_{22} - B_{23} - B_{31} + B_{33}\right) \\ M_4 & = & \left(-A_{11} + A_{21} + A_{22}\right)\left(B_{11} - B_{12} + B_{22}\right) \\ M_5 & = & \left(A_{21} + A_{22}\right)\left(- B_{11} + B_{12}\right) \\ M_6 & = & A_{11}B_{11} \\ M_7 & = & \left(-A_{11} + A_{31} + A_{32}\right)\left(B_{11} - B_{13} + B_{32}\right) \\ M_8 & = & \left(-A_{11} + A_{31}\right)\left(B_{13} - B_{23}\right) \\ M_9 & = & \left(A_{31} + A_{32}\right)\left(-B_{11} + B_{13}\right) \\ M_{10} & = & \left(A_{11} + A_{12} + A_{13} - A_{22} - A_{23} - A_{31} + A_{32}\right)B_{23} \\ M_{11} & = & A_{32}\left(- B_{11} + B_{13} + B_{21} - B_{22} - B_{23} - B_{31} + B_{32}\right) \\ M_{12} & = & \left(- A_{13} + A_{32} + A_{33}\right)\left(B_{22} + B_{31} - B_{32}\right) \\ M_{13} & = & \left(A_{13} - A_{33}\right)\left(B_{22} - B_{32}\right) \\ M_{14} & = & A_{13}B_{31} \\ M_{15} & = & \left(A_{32} + A_{33}\right)\left(- B_{31} + B_{32}\right) \\ M_{16} & = & \left(- A_{13} + A_{22} + A_{23}\right)\left(B_{23} + B_{31} - B_{33}\right) \\ M_{17} & = & \left(A_{13} - A_{23}\right)\left(B_{23} - B_{33}\right) \\ M_{18} & = & \left(A_{22} + A_{23}\right)\left(- B_{31} + B_{33}\right) \\ M_{19} & = & A_{12}B_{21} \\ M_{20} & = & A_{23}B_{32} \\ M_{21} & = & A_{21}B_{13} \\ M_{22} & = & A_{31}B_{12} \\ M_{23} & = & A_{33}B_{33} \end{eqnarray*}$$

Qui nous donnerons : $$\begin{eqnarray*} C_{11} & = & M_6 + M_{14} + M_{19} \\ C_{12} & = & M_1 + M_4 + M_5 + M_6 + M_{12} + M_{14} + M_{15} \\ C_{13} & = & M_6 + M_7 + M_9 + M_{10} + M_{14} + M_{16} + M_{18} \\ C_{21} & = & M_2 + M_3 + M_4 + M_6 + M_{14} + M_{16} + M_{17} \\ C_{22} & = & M_2 + M_4 + M_5 + M_6 + M_{20} \\ C_{23} & = & M_{14} + M_{16} + M_{17} + M_{18} + M_{21} \\ C_{31} & = & M_6 + M_7 + M_8 + M_{11} + M_{12} + M_{13} + M_{14} \\ C_{32} & = & M_{12} + M_{13} + M_{14} + M_{15} + M_{22} \\ C_{33} & = & M_6 + M_7 + M_8 + M_9 + M_{23} \end{eqnarray*}$$

Ce calcul utilise donc :

  • $23$ multiplications
  • $109$ additions


Sa complexité est de $O\left(N^{2.854}\right)$ .