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[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 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é où 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 d'indices de séparation optimaux.
|
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ésage | Nombre de multiplications |
---|---|
2 228 | |
3 000 | |
7 328 | |
12 900 |
Algorithme quasi linéaire
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
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
- ↑ 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, , 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é Stanford, (lire en ligne, consulté le )
v · m | |||||
---|---|---|---|---|---|
| |||||
Propriétés | |||||
Exemples | |||||
Algorithmes de multiplication |
| ||||
Algorithmes de vérification |
|
Portail des mathématiques
Portail de l'informatique théorique