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 ${\displaystyle A_{1}\cdot \dots \cdot A_{k}}$ de façon à minimiser le nombre de multiplications scalaires à effectuer.

Exemple élémentaire

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

Énoncé du problème

On se donne une suite de matrices rectangulaires ${\displaystyle \langle A_{1}\dots ,A_{k}\rangle }$ et on souhaite en calculer le produit ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle A}$ et ${\displaystyle B}$ ayant respectivement ${\displaystyle p}$ lignes et ${\displaystyle q}$ colonnes, et ${\displaystyle q}$ lignes et ${\displaystyle r}$ colonnes, la matrice ${\displaystyle AB}$ obtenue a ${\displaystyle p}$ lignes et ${\displaystyle r}$ colonnes. Le calcul de chacun de ses ${\displaystyle pr}$ coefficients nécessite ${\displaystyle q}$ multiplications scalaires d'après la définition du produit matriciel ; le calcul de ${\displaystyle AB}$ requiert donc ${\displaystyle 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é ${\displaystyle O(k)}$ où ${\displaystyle 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 ${\displaystyle k}$ facteurs, le nombre de parenthésages possibles est égal au ${\displaystyle k-1}$-ième nombre de Catalan, dont la suite a une croissance exponentielle^[1].

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 ${\displaystyle A_{i,j}=A_{i}\dots A_{j}}$ (où on a ${\displaystyle 1\leq i<j\leq k}$), si le dernier produit matriciel calculé est ${\displaystyle (A_{i}\dots A_{l})\cdot (A_{l+1}\dots A_{j})}$ alors les parenthésages utilisés pour le calcul de ${\displaystyle A_{i}\dots A_{l}}$ et ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle A_{i,j}}$ et donc pour tous ceux du calcul de ${\displaystyle A_{1,k}}$. Cela permet une résolution grâce à la programmation dynamique^[1].

Calcul du coût des sous-parenthésages

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

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

${\displaystyle 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

${\displaystyle 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 ${\displaystyle m}$ et de ${\displaystyle s}$ simultanément de proche en proche.

Reconstitution d'un parenthésage optimal

Étant donné le tableau ${\displaystyle l}$, on peut utiliser l'algorithme récursif suivant pour étant donnés deux indices ${\displaystyle i}$ et ${\displaystyle j}$ déterminer un parenthésage optimal du produit ${\displaystyle 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é

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

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

Exemple d'exécution

Soit ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle C_{5}=42}$ parenthésages à tester, on opte donc pour l'algorithme par programmation dynamique.

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

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

On obtient alors les tableaux suivants :

Tableau ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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
${\displaystyle 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
${\displaystyle 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
${\displaystyle 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
${\displaystyle 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

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 ${\displaystyle O(k\log k)}$^[3].

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 ${\displaystyle 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

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

Références

• Portail des mathématiques
• Portail de l'informatique théorique