Problème des multiplications matricielles enchaînées

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.

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].

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.

É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)

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].

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