Le produit matriciel et son coût

Composer des applications

Le produit $AB$ est l'application obtenue en appliquant d'abord $B$ puis $A$ : $(AB)\mathbf{x}=A(B\mathbf{x})$. L'entrée $(i,j)$ du produit est la ligne $i$ de $A$ multipliée scalairement par la colonne $j$ de $B$, donc les tailles doivent s'accorder : une matrice $m\times n$ fois une matrice $n\times p$ donne une matrice $m\times p$. Le produit est associatif, $(AB)C=A(BC)$, et distributif sur la somme, mais en général il n'est pas commutatif : $AB\neq BA$, car l'ordre de deux actions compte.

Calculer $AB$ pour une matrice $m\times n$ et une matrice $n\times p$ demande $mnp$ multiplications-additions (environ $2mnp$ opérations flottantes). Pour deux matrices $n\times n$, cela fait $n^3$ : doubler $n$ multiplie le travail par huit. Une matrice fois un vecteur ne coûte que $n^2$. Comme le produit est associatif, la place des parenthèses ne change pas le résultat mais peut changer énormément le coût.

• Règle des tailles : $(m\times n)(n\times p)=(m\times p)$ ; les tailles intérieures doivent coïncider.
• Non commutatif : $AB\neq BA$ en général, donc n'échangez jamais les facteurs.
• Coût : $mnp$ multiplications-additions ; matrice fois vecteur $n^2$, matrice fois matrice $n^3$.

Lab : ce qui est noté

• Le produit AB20 pts
• Le produit BA15 pts
• La taille d'un produit10 pts
• Compter les multiplications-additions15 pts
• Deux façons de parenthéser20 pts
• Pourquoi le parenthésage compte20 pts