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^{[réf. nécessaire]} ; 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}$:

Affichage-Parenthésage-Minimal(l,i,j)
si i=j
  afficher "A_i"
sinon afficher "("
  Affichage-Parenthésage-Minimal(l,i,l[i][j])
  Affichage-Parenthésage-Minimal(l,l[i][j]+1,j)
  afficher ")"

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

Affichage-Parenthésage-Minimal(l,1,k)

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. 1 2 3 4 5 6 1 0 300 1 200 1 140 1 380 2 228 2 NIL 0 1 800 960 1 440 2 368 3 NIL NIL 0 720 1 008 1 872 4 NIL NIL NIL 0 1 440 2 688 5 NIL NIL NIL NIL 0 768 6 NIL NIL NIL NIL NIL 0

Tableau $l$ d'indices de séparation optimaux. 1 2 3 4 5 6 1 NIL 1 2 2 4 4 2 NIL NIL 2 2 4 4 3 NIL NIL NIL 3 4 4 4 NIL NIL NIL NIL 4 4 5 NIL NIL NIL NIL NIL 5 6 NIL NIL NIL NIL NIL NIL

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.

Bibliographie

Ana Bušić, « Programmation Dynamique appliquée à l'algorithmique Numérique: Multiplications matricielles enchaînées (Cours Licence 3) », 2012