6.4.2.1.1 : Algorithme de Strassen (fast 2x2)
La multiplication selon Strassen définit des coéficients intermédiaires :

M1=(A12A22)×(B21+B22)M2=(A11+A22)×(B11+B22)M3=(A11A21)×(B11+B12)M4=(A11+A12)×B22M5=A11(B12B22)M6=A22(B21B11)M7=(A21+A22)×B11

Enfin, le calcul final :

C11=M1+M2M4+M6C12=M4+M5C21=M6+M7C22=M2M3+M5M7

Le calcul de Strassen utilise donc :

  • 7 multiplications
  • 17 additions


Sa complexité est de O(N2.81) au lieu de O(N3) .