Problème des multiplications matricielles enchaînées
# Problème des multiplications matricielles enchaînées

En informatique, un algorithme de multiplication de matrices enchaînées est un algorithme d'optimisation qui sert à trouver un ordre dans lequel calculer un produit de plusieurs matrices $A_{1}\cdot \dots \cdot A_{k}$ de façon à minimiser le nombre de multiplications scalaires à effectuer.

## Exemple élémentaire

On considère $A={\begin{pmatrix}a_{1}&a_{2}&a_{3}\\\end{pmatrix}}$, $B={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\\end{pmatrix}}$ et $C={\begin{pmatrix}c_{1}&c_{2}&c_{3}\\\end{pmatrix}}$. Comme le produit matriciel est associatif on a $(AB)C$ = $A(BC)$ mais le calcul de $(AB)C$ nécessite 6 multiplications scalaires tandis que celui de $A(BC)$ en nécessite 18. Il est donc préférable de calculer d'abord $AB$ puis $(AB)C$ plutôt que d'abord $BC$ puis $A(BC)$.

## Énoncé du problème

On se donne une suite de matrices rectangulaires $\langle A_{1}\dots ,A_{k}\rangle$ et on souhaite en calculer le produit $A_{1,k}=A_{1}\dots A_{k}$ (on suppose que toutes les matrices ont une taille compatible, c'est-à-dire que le produit est bien défini). Le produit matriciel étant associatif, n'importe quel parenthésage du produit donnera le même résultat. On cherche à déterminer avant d'effectuer tout calcul quel parenthésage nécessitera le moins de multiplications scalaires.

Un parenthésage optimal pour un produit matriciel naïf ayant une complexité en $O(k^{3})$ est a priori également optimal pour les algorithmes de produit optimisé comme l'algorithme de Strassen ; on supposera donc par la suite que le parenthésage à trouver concerne un produit matriciel classique.

### Détermination du nombre d'opérations associées à un parenthésage particulier

Lorsque l'on multiplie deux matrices rectangulaires $A$ et $B$ ayant respectivement $p$ lignes et $q$ colonnes, et $q$ lignes et $r$ colonnes, la matrice $AB$ obtenue a $p$ lignes et $r$ colonnes. Le calcul de chacun de ses $pr$ coefficients nécessite $q$ multiplications scalaires d'après la définition du produit matriciel ; le calcul de $AB$ requiert donc $pqr$ multiplications scalaires.

On peut donc calculer de proche en proche le nombre de multiplications scalaires associées à un parenthésage particulier. Cette détermination a une complexité $O(k)$ où $k$ est le nombre de matrices à multiplier.

## Algorithme naïf

Une solution possible est de procéder par force brute en énumérant tous les parenthésage possibles pour retenir le meilleur. Ce n'est pas envisageable car pour un produit de $k$ facteurs, le nombre de parenthésages possibles est égal au $k-1$-ième nombre de Catalan, dont la suite a une croissance exponentielle.

## Algorithme utilisant la programmation dynamique

Le problème a une structure telle qu'un sous-parenthésage d'un parenthésage optimal est lui-même optimal. De plus un même sous-parenthésage peut intervenir dans plusieurs parenthésages différents. Ces deux conditions rendent possible la mise en œuvre de techniques de programmation dynamique.

### Structure d'un parenthésage optimal

On remarque que pour un parenthésage optimal du produit $A_{i,j}=A_{i}\dots A_{j}$ (où on a $1\leq i<j\leq k$), si le dernier produit matriciel calculé est $(A_{i}\dots A_{l})\cdot (A_{l+1}\dots A_{j})$ alors les parenthésages utilisés pour le calcul de $A_{i}\dots A_{l}$ et $A_{l+1}\dots A_{j}$ sont eux aussi optimaux. En effet si ce n'était pas le cas on pourrait les remplacer par un meilleur parenthésage et donc avoir un meilleur parenthésage pour le produit $A_{i}\dots A_{j}$, ce qui est contradictoire avec l'hypothèse d'optimalité que l'on a faite.

La même hypothèse d'optimalité peut être faite pour tous les parenthésages de tous les produits intermédiaires au calcul de $A_{i,j}$ et donc pour tous ceux du calcul de $A_{1,k}$. Cela permet une résolution grâce à la programmation dynamique.

### Calcul du coût des sous-parenthésages

Pour tout $i\in [1,k]$ on note $p_{i-1}$ le nombre de lignes de $A_{i}$ et $p_{i}$ son nombre de colonnes.

On définit les tableaux à deux dimensions $m[1\dots k][1\dots k]$ et $l[1\dots k][1\dots k]$ tels que pour tout couple d'indices $(i,j)$ tel que $i\leq j$, la case $m[i][j]$ contient le nombre minimal de multiplications scalaires nécessaire au calcul de $A_{i,j}$ et $l[i][j]$ contient un indice tel que le parenthésage optimal du produit soit $A_{i,j}=A_{i,l}\cdot A_{l+1,j}$ on obtient:

$m[i][j]={\begin{cases}0&{\text{ si }}i=j,\\\min _{i\leq l<j}\{m[i][l]+m[l+1][j]+p_{i-1}p_{l}p_{j}\}&{\text{ si }}i<j,\\{\text{NIL}}&{\text{ si }}i>j.\end{cases}}$

et

$l[i][j]={\begin{cases}s{\text{ tel que }}\min _{i\leq l<j}\{m[i][l]+m[l+1][j]+p_{i-1}p_{l}p_{j}\}=m[i][s]+m[s+1][i]+p_{i-1}p_{s}p_{j}&{\text{ si }}i<j,\\{\text{NIL}}&{\text{ sinon}}.\end{cases}}$

On peut calculer le contenu des cases de $m$ et de $s$ simultanément de proche en proche.

### Reconstitution d'un parenthésage optimal

Étant donné le tableau $l$, on peut utiliser l'algorithme récursif suivant pour étant donnés deux indices $i$ et $j$ déterminer un parenthésage optimal du produit $A_{i,j}$:

On obtient alors un parenthésage optimal en exécutant :

### Calcul de la complexité

Comme il y a $O(k^{2})$ cases dans le tableau et que le coût d'un sous-parenthésage peut être calculé en $O(k)$, il s'ensuit que l'on peut calculer les coûts de l'ensemble des sous-parenthésages optimaux en $O(k^{3})$ avec une capacité de stockage mémoire $\Theta (k^{2})$. On peut également montrer que la complexité en temps du calcul de $m$ est $\Omega (k^{3})$ : la complexité est cubique même dans le meilleur des cas.

Une fois déterminés $m$ et $s$, l'algorithme affichant le parenthésage a une complexité $O(k)$.

### Exemple d'exécution

Soit $M_{5,10},M_{10,6},M_{6,30},M_{30,4},M_{4,12},M_{12,16}$ six matrices rectangulaires (pour chaque matrice, le premier indice indique son nombre de lignes et le second son nombre de colonnes). On cherche un parenthésage optimal pour calculer le produit $M=M_{5,10}\cdot M_{10,6}\cdot M_{6,30}\cdot M_{30,4}\cdot M_{4,12}\cdot M_{12,16}$. Si l'on souhaite procéder par recherche exhaustive il y a $C_{5}=42$ parenthésages à tester, on opte donc pour l'algorithme par programmation dynamique.

On remplit les cases $(i,j)$ des tableaux $c[1..6][1..6]$ et $l[1..6][1..6]$ en suivant l'ordre :

| Première diagonale | $(1,2)-(2,3)-(3,4)-(4,5)-(5,6)$ |
| - | - |
| Deuxième diagonale | $(1,3)-(2,4)-(3,5)-(4,6)$ |
| Troisième diagonale | $(1,4)-(2,5)-(3,6)$ |
| Quatrième diagonale | $(1,5)-(2,6)$ |
| Cinquième diagonale | $(1,6)$ |

On obtient alors les tableaux suivants :

| Tableau $c$ des coûts des sous-parenthésages. 123456 1 03001 2001 1401 3802 228 2 NIL01 8009601 4402 368 3 NILNIL07201 0081 872 4 NILNILNIL01 4402 688 5 NILNILNILNIL0768 6 NILNILNILNILNIL0 | Tableau $l$ d'indices de séparation optimaux. 123456 1 NIL12244 2 NILNIL2244 3 NILNILNIL344 4 NILNILNILNIL44 5 NILNILNILNILNIL5 6 NILNILNILNILNILNIL |
| - | - |

D'où l'on déduit qu'un parenthésage optimal est $M=((M_{5,10}\cdot M_{10,6})\cdot (M_{6,30}\cdot M_{30,4}))\cdot (M_{4,12}\cdot M_{12,16})$ qui permet un calcul de $M$ avec 2 228 multiplications scalaires. À titre de comparaison, le tableau suivant présente les coûts de différents parenthésages.

| Parenthésage | Nombre de multiplications |
| - | - |
| $M=((M_{5,10}\cdot M_{10,6})\cdot (M_{6,30}\cdot M_{30,4}))\cdot (M_{4,12}\cdot M_{12,16})$ | 2 228 |
| $M=M_{5,10}\cdot (M_{10,6}\cdot (M_{6,30}\cdot (M_{30,4}\cdot (M_{4,12}\cdot M_{12,16}))))$ | 3 000 |
| $M=((((M_{5,10}\cdot M_{10,6})\cdot M_{6,30})\cdot M_{30,4})\cdot M_{4,12})\cdot M_{12,16}$ | 7 328 |
| $M=(M_{5,10}\cdot (M_{10,6}\cdot M_{6,30}))\cdot ((M_{30,4}\cdot M_{4,12})\cdot M_{12,16})$ | 12 900 |

## Algorithme quasi linéaire

Un algorithme a été proposé en 1981 dont la complexité est $O(k\log k)$.

## Applications

Dans la pratique, la taille des matrices à multiplier excède souvent le nombre de facteurs du produit matriciel. Ainsi même si la complexité de l'algorithme d'optimisation est $O(k^{3})$, l'appliquer pour minimiser le nombre de multiplications scalaires à effectuer dans le produit proprement dit représente un gain de temps.

