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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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^[1].

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[modifier | modifier le code]

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^[1].

Algorithme utilisant la programmation dynamique[modifier | modifier le code]

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[modifier | modifier le code]

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^[1].

Calcul du coût des sous-parenthésages[modifier | modifier le code]

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^[2].

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^[1]:

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[modifier | modifier le code]

É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}$ ^[1]:

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é[modifier | modifier le code]

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})$ ^[1]. 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^[1].

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

Exemple d'exécution[modifier | modifier le code]

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[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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

Applications[modifier | modifier le code]

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^[1].

Bibliographie[modifier | modifier le code]

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

Références[modifier | modifier le code]

↑ ^{a b c d e f g h et i} (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, 2002, xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), chap. 15 (« Programmation dynamique »).
↑ La notation est cohérente car pour que le produit de deux matrices soit défini, le nombre de colonnes de celle de gauche doit être égal au nombre de lignes de celle de droite.
↑ T. C. Hu et M.T. Shing, « Computation of Matrix Chain Products. Part I, Part II », Technical Reports of Stanford University, Université de Stanford,‎ 1981 (lire en ligne, consulté le 30 janvier 2018)

[Cormen2-1] {a b c d e f g h et i} (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, 2002, xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), chap. 15 (« Programmation dynamique »).

[2] La notation est cohérente car pour que le produit de deux matrices soit défini, le nombre de colonnes de celle de gauche doit être égal au nombre de lignes de celle de droite.

[3] T. C. Hu et M.T. Shing, « Computation of Matrix Chain Products. Part I, Part II », Technical Reports of Stanford University, Université de Stanford,‎ 1981 (lire en ligne, consulté le 30 janvier 2018)

[1]

[2]

[3]