Accueil🇫🇷Chercher

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 de façon à minimiser le nombre de multiplications scalaires à effectuer.

Exemple élémentaire

On considère , et . Comme le produit matriciel est associatif on a = mais le calcul de nécessite 6 multiplications scalaires tandis que celui de en nécessite 18. Il est donc préférable de calculer d'abord puis plutôt que d'abord puis .

Énoncé du problème

On se donne une suite de matrices rectangulaires et on souhaite en calculer le produit (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 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 et ayant respectivement lignes et colonnes, et lignes et colonnes, la matrice obtenue a lignes et colonnes. Le calcul de chacun de ses coefficients nécessite multiplications scalaires d'après la définition du produit matriciel ; le calcul de requiert donc 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é 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 facteurs, le nombre de parenthésages possibles est égal au -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 (où on a ), si le dernier produit matriciel calculé est alors les parenthésages utilisés pour le calcul de et 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 , 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 et donc pour tous ceux du calcul de . Cela permet une résolution grâce à la programmation dynamique[1].

Calcul du coût des sous-parenthésages

Pour tout on note le nombre de lignes de et son nombre de colonnes[2].

On définit les tableaux à deux dimensions et tels que pour tout couple d'indices tel que , la case contient le nombre minimal de multiplications scalaires nécessaire au calcul de et contient un indice tel que le parenthésage optimal du produit soit on obtient[1]:

et

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

Reconstitution d'un parenthésage optimal

Étant donné le tableau , on peut utiliser l'algorithme récursif suivant pour étant donnés deux indices et déterminer un parenthésage optimal du produit [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 cases dans le tableau et que le coût d'un sous-parenthésage peut être calculé en , il s'ensuit que l'on peut calculer les coûts de l'ensemble des sous-parenthésages optimaux en avec une capacité de stockage mémoire [1]. On peut également montrer que la complexité en temps du calcul de est : la complexité est cubique même dans le meilleur des cas[1].

Une fois déterminés et , l'algorithme affichant le parenthésage a une complexité [1].

Exemple d'exécution

Soit 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 . Si l'on souhaite procéder par recherche exhaustive il y a parenthésages à tester, on opte donc pour l'algorithme par programmation dynamique.

On remplit les cases des tableaux et en suivant l'ordre :

Première diagonale
Deuxième diagonale
Troisième diagonale
Quatrième diagonale
Cinquième diagonale


On obtient alors les tableaux suivants :


Tableau 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 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 qui permet un calcul de avec 2 228 multiplications scalaires. À titre de comparaison, le tableau suivant présente les coûts de différents parenthésages.

ParenthésageNombre de multiplications
2 228
3 000
7 328
12 900

Algorithme quasi linéaire

Un algorithme a été proposé en 1981 dont la complexité est [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 , 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) »,

Références

  1. (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, , 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, (lire en ligne, consulté le )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.