WikiMath

---

Le produit classique

Présentation

Le produit de deux matrices ne peut se définir que si le nombre de colonnes de la première matrice est le même que le nombre de lignes de la deuxième matrice.

Si $A = (a_{ij})$ est une matrice de type $(m,n)$ et $B = (b_{ij})$ est une matrice de type $(n,p)$, alors leur produit, noté $AB = (c_{ij})$ est la matrice de type $(m,p)$ donnée par :

$c_{ij}= \sum_{k=1}^n a_{ik}\cdot b_{kj} = a_{i1} \cdot b_{1j} + a_{i2} \cdot b_{2j}+ \ldots + a_{in} \cdot b_{nj}$

pour chaque $1 \le i \le m$ et $1 \le j \le p$.

La figure suivante (extraite de http://fr.wikipedia.org/wiki/Produit_matriciel) montre comment calculer les coefficients $c_{12}$ et $c_{33}$ de la matrice produit $AB$ si $A$ est une matrice de type (4,2), et $B$ est une matrice de type (2,3).

Par exemple :

• ${c_{12}} = \sum_{r=1}^2 a_{1r}b_{r2} = a_{11}b_{12}+a_{12}b_{22}$,
• ${c_{33}} = \sum_{r=1}^2 a_{3r}b_{r3} = a_{31}b_{13}+a_{32}b_{23}$.

Un mot de complexité

La complexité de la multiplication naïve est en $O(n^3)$ :

• Pour chaque $c_{i,j}$, on effectue $n$ multiplications et $n-1$ additions.
• On a donc $2n-1$ opérations par coefficient, et $n^2$ coefficients.
• On trouve au final $2 n^3 - n^2$ opérations pour la multiplication, qui est du même ordre de grandeur que $n^3$ : on note cela $O(n^3)$.

Notons, pour finir cette section, que les additions sont généralement ignorées dans le calcul de la complexité : elles sont beaucoup plus rapides que la multiplication, en particulier si la taille des entrées est supérieure à la taille du mot machine.

Travaux pratiques

1. Programmez une fonction de produit matriciel.

L'algorithme de Strassen

Ce qui suit est à réserver aux étudiants en avance, et que cela intéresse. Le travail demandé est assez compliqué.

Présentation

Cet algorithme, dû à Volker Strassen (1969), permet d'obtenir le produit de deux matrices de taille $n$ en $O(n^{2,807})$. Ce résultat prouve que la multiplication naïve, et donc le pivot de Gauss, ne sont pas optimaux.

Description de l'algorithme

Soient $A$ et $B$ deux matrices carrées de taille $n$, dont on souhaite calculer le produit $C = A \times B$. On suppose, pour se simplifier la vie, que $n$ est de la forme une puissance de 2 : si tel n'est pas le cas, il suffit de compléter les matrices avec des 0.

Les trois matrices A, B et C sont divisées en matrices par blocs de taille égale :

$ \mathbf{A} = \left(\begin{array}{cc} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{array}\right) \mbox { , } \mathbf{B} = \left(\begin{array}{cc} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{array}\right) \mbox { , } \mathbf{C} = \left(\begin{array}{cc} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{array}\right)$

où les $\mathbf{A}_{i,j}, \mathbf{B}_{i,j}$, et $\mathbf{C}_{i,j}$ ont une taille $\frac{n}{2}$. On a alors, en identifiant $A\times B$ et $C$ :

• $\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \times \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \times \mathbf{B}_{2,1}$
• $\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \times \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \times \mathbf{B}_{2,2}$
• $\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \times \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \times \mathbf{B}_{2,1}$
• $\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \times \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \times \mathbf{B}_{2,2}$

On constate que cette méthode nécessite 8 multiplications de matrices pour calculer les $C_{i,j}$, et ce comme dans le produit classique.

L'idée de Strassen est de réussir à obtenir ces $C_{i,j}$ avec seulement 7 multiplications, en introduisant les matrices suivantes :

• $\mathbf{M}_{1} = (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) \times (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})$
• $\mathbf{M}_{2} = (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \times \mathbf{B}_{1,1}$
• $\mathbf{M}_{3} = \mathbf{A}_{1,1} \times (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})$
• $\mathbf{M}_{4} = \mathbf{A}_{2,2} \times (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})$
• $\mathbf{M}_{5} = (\mathbf{A}_{1,1} + \mathbf{A}_{1,2})\times \mathbf{B}_{2,2}$
• $\mathbf{M}_{6} = (\mathbf{A}_{2,1} - \mathbf{A}_{1,1})\times (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})$
• $\mathbf{M}_{7} = (\mathbf{A}_{1,2} - \mathbf{A}_{2,2})\times (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$

Les $C_{i,j}$ sont alors exprimées comme

• $\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}$
• $\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}$
• $\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}$
• $\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$

On fait plus d'additions et de soustractions matricielles (qui ont une complexité linéaire) que dans la méthode naïve, mais une multiplication de moins : le gain est énorme.

Le procédé est répété jusqu'à ce que les matrices $A$ et $B$ soient tailles raisonnables.

Complexité

Le nombre de multiplications $T(n)$ est ici de l'ordre de $n^{\log_{2}7}\approx n^{2.807}$, solution de l'équation par récurrence $T(n) = 7T\left(\frac{n}{2}\right) + O(n^2)$ : pour faire une multiplication de taille $n$, on fait 7 multiplications de taille $\frac{n}{2}$ et quelques opérations annexes.

Discussion

La constante dans la complexité est proche de 50 : l'algorithme de Strassen n'est efficace que pour des matrices de grandes tailles.

De plus, cet algorithme est peu efficace sur les matrices creuses (qui ont peu de coefficients non-nuls), courantes en analyse numérique.

Enfin, l'algorithme n'est pas très stable numériquement.

Importance du résultat

Le travail de Strassen a permis de développer un nouveau champ de la recherche en informatique théorique : le calcul rapide du produit matriciel.

Plusieurs résultats importants suivront : Samuel Winograd publie un algorithme en 1980 qui utilise moins d'additions que celui de Strassen. Et, surtout, Don Coppersmith et Winograd publient en 1987 l'algorithme du même nom, améliorant grandement la complexité de la multiplication (en $O(n^{2,376})$).

Ce dernier algorithme est le plus efficace en théorie ; cependant, rien n'indique qu'il est optimal, en terme de complexité : on pense pouvoir atteindre l'exposant 2.

D'un point de vue théorique, donc, cet algorithme est d'importance, mais il n'a aucun intérêt pratique : la constante dans le grand $O$ est beaucoup trop grande.

Travaux pratiques

1. Mettre en place l'algorithme de Strassen, pour améliorer votre méthode de multiplication matricielle.
2. Comparer les temps de calcul pour des matrices d'une certaine taille. On pourra utiliser PyX pour illustrer cela.