Utilisateur:Mattelbe/Algorithme de multiplication de matrices
De par le fait que la multiplication matricielle est une opération centrale dans de nombreux algorithmes numériques, un travail considérable a été effectué pour rendre les algorithmes de multiplication matricielle efficaces. Les applications de la multiplication matricielle dans des problèmes calculatoires se retrouvent dans de nombreux domaines, notamment le calcul scientifique et la reconnaissance des formes, ainsi que dans des problèmes apparemment sans rapport, tels que le comptage des chemins à travers un graphe.[1] De nombreux algorithmes différents ont été conçus pour multiplier les matrices sur différents types de matériel informatique, y compris les systèmes parallèles et distribués, où les calculs sont répartis sur plusieurs processeurs pouvant être eux-même répartis sur un réseau.
L'application directe de la définition mathématique de la multiplication matricielle donne un algorithme qui prend un temps de l'ordre de pour multiplier deux matrices ( en notation grand O). Bien que de meilleures limites asymptotiques sur le temps nécessaire pour multiplier les matrices sont connues depuis les travaux de Strassen dans les années 1960, on ignore encore la complexité du problème et donc le temps optimal théorique pour ces calculs.
Le résultat de la multiplication matricielle pour deux matrices et de tailles respectives et est la matrice de taille ayant pour éléments
- .
On peut construire à partir de cette définition un algorithme simple qui boucle sur les indices de 1 à et de 1 à , calculant le résultat précédent à l'aide d'une boucle imbriquée :
- Entrée: matricesA et B
- Soit C une nouvelle matrice de taille appropriée
- Pour i de 1 à n:
- Pour j de 1 à p:
- Soit somme = 0
- Pour k de 1 à m:
- Affecter somme ← somme + Aik × Bkj
- Affecter Cij ← somme
- Pour j de 1 à p:
- Return C
Cet algorithme a une complexité temporelle en (en notation asymptotique).[1]
Une simplification courante pour faciliter l'analyse des algorithmes consiste à supposer que les matrices en entrée sont toutes des matrices carrées de taille . Dans ce cas la complexité temporelle de l'algorithme naïf est en , c'est-à-dire cubique.[2]
Comportement du cache
modifierLes trois boucles de la multiplication matricielle itérative peuvent être arbitrairement interchangées sans impacter la validité du résultat ou le temps d'exécution asymptotique. Toutefois, l'ordre peut avoir un impact considérable sur les performances en pratique en raison des modèles d'accès à la mémoire du matériel utilisé et de l'utilisation du cache de l'algorithme[1] ; l'ordre optimal dépend aussi du fait que les matrices sont stockées dans l'ordre des lignes principales, des colonnes principales ou un mélange des deux.
En particulier, dans le cas idéal d'un cache entièrement associatif composé de octets et octets par ligne de cache (c'est-à-dire lignes de cache), l'algorithme ci-dessus n'est pas optimal pour et stockées dans l'ordre des lignes principales. Lorsque , chaque itération de la boucle interne (consistant en un balayage simultané à travers une ligne de et une colonne de ) entraîne un échec de cache lors de l'accès à un élément de . Cela signifie que l'algorithme génère échecs de cache dans le pire cas.
Depuis 2010, la vitesse des mémoires par rapport à celle des processeurs est telle que les échecs de cache sont le principal facteur augmentant le temps d'exécution des algorithmes de multiplication de matrices de tailles importantes.[3]
La variante optimale de l'algorithme itératif pour et dans la disposition en ligne principale est une version en mosaïque, où la matrice est implicitement divisée en carreaux carrés de taille : [3] [4]
- Input: matrices A and B
- Let C be a new matrix of the appropriate size
- Pick a tile size T = Θ(Modèle:Radic)
- For I from 1 to n in steps of T:
- For J from 1 to p in steps of T:
- For K from 1 to m in steps of T:
- Multiply AI:I+T, K:K+T and BK:K+T, J:J+T into CI:I+T, J:J+T, that is:
- For i from I to min(I + T, n):
- For j from J to min(J + T, p):
- Let sum = 0
- For k from K to min(K + T, m):
- Set sum ← sum + Aik × Bkj
- Set Cij ← Cij + sum
- For j from J to min(J + T, p):
- For K from 1 to m in steps of T:
- For J from 1 to p in steps of T:
- Return C
Dans un modèle de cache idéalisé, cet algorithme n'engendre que échecs de cache.
Le diviseur équivaut à plusieurs ordres de grandeur sur les machines modernes, de sorte que les calculs réels dominent le temps de fonctionnement, plutôt que les échecs de cache.[3]
Algorithme diviser pour régner
modifierUne alternative à l'algorithme itératif est un algorithme de type diviser pour régner. Il repose sur le partitionnement des blocs
- ,
qui fonctionne pour toutes les matrices carrées dont les dimensions sont des puissances de deux, c'est-à-dire de forme pour donné. Le produit matriciel devient
et consiste en huit multiplications de paires de sous-matrices, suivies d'une étape d'addition. L'algorithme diviser pour régner calcule récursivement les plus petites multiplications, en utilisant la multiplication scalaire comme cas de base.
La complexité de cet algorithme en fonction de est donnée par la relation de récurrence[5]
- ;
- ,
qui tient compte des huit appels récursifs sur des matrices de taille et pour additionner les quatre paires de matrices résultantes par élément. L'application du théorème sur les récurrences de partition montre que cette récurrence a une solution asymptotique en identique à la complexité de l'algorithme itératif.
Matrices non carrées
modifierUne variante de cet algorithme qui fonctionne pour les matrices de formes arbitraires et qui est plus rapide en pratique[3] divise les matrices en deux au lieu de quatre sous-matrices, comme suit. Fractionner une matrice signifie désormais la diviser en deux parties de taille à peu près égales.
Algorithmes sous-cubiques
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e9/Bound_on_matrix_multiplication_omega_over_time.svg/400px-Bound_on_matrix_multiplication_omega_over_time.svg.png)
Il existe des algorithmes offrant de meilleurs temps d'exécution que les approches naïves. Le premier proposé fut l'algorithme de Strassen, conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide ». Il repose sur une manière de multiplier deux matrices 2 × 2 qui ne nécessite que 7 multiplications (au lieu des 8 habituelles), au détriment de plusieurs opérations supplémentaires d'addition et de soustraction. L'application récursive donne un algorithme avec un coût en multiplications de . L'algorithme de Strassen est plus complexe, et sa stabilité numérique est inférieure à celle de l'algorithme naïf, mais il est plus rapide dans les cas où environ[1] et apparaît dans plusieurs bibliothèques logicielles, comme BLAS.[6] Il est très utile pour les grandes matrices sur des domaines exacts tels que les champs finis, où la stabilité numérique n'est pas un problème.
L'algorithme en actuel avec l'exposant k le plus bas est une généralisation de l'algorithme Coppersmith – Winograd qui a une complexité asymptotique de , proposé par François Le Gall. L'algorithme de Le Gall et l'algorithme de Coppersmith – Winograd sur lequel il est basé sont similaires à l'algorithme de Strassen : on trouve un moyen de multiplier deux matrices avec moins de multiplications, puis cette technique est appliquée récursivement. Cependant, le coefficient constant caché par la notation grand O est si grand que ces algorithmes ne valent que pour les matrices trop grandes pour être manipulées sur les ordinateurs actuels en pratique.[7]
Étant donné que tout algorithme de multiplication de deux matrices doit traiter l'ensemble des entrées, il existe une borne inférieure asymptotique des opérations qui est . Raz a démontré une borne inférieure de pour les circuits arithmétiques à coefficient borné sur les nombres réels ou complexes.
Cohn et al. placent les méthodes telles que les algorithmes Strassen et Coppersmith – Winograd dans un contexte de théorie des groupes entièrement différent, en utilisant des triplets de sous-ensembles de groupes finis qui satisfont une propriété de disjonction appelée propriété du triple produit. Ils montrent que si les familles de produits en couronne de groupes abéliens avec des groupes symétriques réalisent des familles de sous-ensembles triples avec une version simultanée du triple produit, alors il existe des algorithmes de multiplication matricielle avec une complexité essentiellement quadratique. [8] La plupart des chercheurs pensent que c'est effectivement le cas. [7] Cependant, Alon, Shpilka et Chris Umans ont récemment montré que certaines de ces conjectures impliquant une multiplication matricielle rapide sont incompatibles avec une autre conjecture plausible, la conjecture de tournesol.[9]
L'algorithme de Freivalds est un algorithme de Monte Carlo simple qui, étant donné les matrices , et , vérifie en un temps si .
Algorithmes distribués et évitant la communication
modifierSur les architectures modernes à mémoire hiérarchique, le coût de chargement et de stockage des éléments de matrice d'entrée a tendance à dominer le coût des calculs arithmétiques. Sur une seule machine, il s'agit de la quantité de données transférées entre la RAM et le cache, tandis que dans un système multi-nœuds à mémoire distribuée, il s'agit plutôt de la quantité de données transférée entre les nœuds. Dans les deux cas, il s'agit de la bande passante. L'algorithme naïf utilisant trois boucles imbriquées utilise une bande passante de communication .
L'algorithme de Cannon, également connu sous le nom d'algorithme 2D, est un algorithme de limitation des mouvements de données qui partitionne chaque matrice d'entrée en une matrice de blocs dont les éléments sont des sous-matrices de taille , où est la taille de la mémoire rapide.[10] L'algorithme naïf est ensuite utilisé sur les matrices de blocs, calculant les produits de sous-matrices intégralement en mémoire rapide. Cela réduit la bande passante à , ce qui est asymptotiquement optimal (pour les algorithmes effectuant le calcul de ). [11] [12]
Dans un environnement distribué avec processeurs disposés dans un réseau maillé 2D de forme , une sous-matrice du résultat peut être affectée à chaque processeur, et le produit peut être calculé avec chaque processeur transmettant mots, ce qui est asymptotiquement optimal si l'on suppose que chaque nœud stocke les O(n2/p) éléments minimaux.[12] Ceci peut être amélioré par l'algorithme 3D, qui organise les processeurs en une maille de cube 3D, affectant chaque produit de deux sous-matrices d'entrée à un seul processeur. Les sous-matrices résultantes sont ensuite générées en effectuant une réduction sur chaque ligne.[13] Cet algorithme transmet mots par processeur, ce qui est asymptotiquement optimal. Cependant, cela nécessite de répliquer chaque élément de matrice d'entrée fois, et nécessite donc un facteur de mémoire de plus que ce qui est nécessaire pour stocker les entrées. Cet algorithme peut être combiné avec celui de Strassen pour réduire davantage le temps d'exécution. Les algorithmes dits "2,5D" offrent un compromis continu entre l'utilisation de la mémoire et la bande passante.[14] Sur les environnements informatiques distribués modernes tels que MapReduce, des algorithmes de multiplication spécialisés ont été développés.[15]
Algorithmes pour les maillages
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png/240px-Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png)
Il existe une variété d'algorithmes de multiplication sur les réseaux maillés. Pour la multiplication de deux matrices de taille sur un réseau maillé bidimensionnel standard en utilisant l'algorithme de Cannon 2D, on peut effectuer la multiplication en étapes.[16] Le tableau standard est inefficace car les données des deux matrices n'arrivent pas simultanément et doivent être remplies de zéros.
Le résultat est encore plus rapide sur un maillage croisé à deux couches, où seulement étapes sont nécessaires.[17] Les performances s'améliorent encore pour les calculs répétés conduisant à une efficacité de 100%.[18]
Voir également
modifierRéférences
modifier- Steven Skiena, The Algorithm Design Manual, Springer, , 45–46, 401–403 (ISBN 978-1-84800-069-8, DOI 10.1007/978-1-84800-070-4_4), « Sorting and Searching »
- (en) Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, (ISBN 0-262-03384-4), p. 75–79
- Amarasinghe et Leiserson, « 6.172 Performance Engineering of Software Systems, Lecture 8 », MIT OpenCourseWare, Massachusetts Institute of Technology, (consulté le )
- Monica S. Lam, Edward E. Rothberg et Michael E. Wolf « The Cache Performance and Optimizations of Blocked Algorithms » ()
—Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS) - (en) Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, (ISBN 0-262-03384-4), p. 75–79
- William H. Press, Brian P. Flannery, Saul A. Teukolsky et William T. Vetterling, Numerical Recipes: The Art of Scientific Computing, 3rd, (ISBN 978-0-521-88068-8), p. 108
- Robinson, « Toward an Optimal Algorithm for Matrix Multiplication », SIAM News, vol. 38, no 9, (lire en ligne)
- Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. « math.GR/0307321 », texte en accès libre, sur arXiv.. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.
- Alon, Shpilka, Umans, On Sunflowers and Matrix Multiplication
- Lynn Elliot Cannon, A cellular computer to implement the Kalman Filter Algorithm, Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.
- Hong et Kung, « I/O complexity: The red-blue pebble game », STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, , p. 326–333 (lire en ligne)
- Irony, Toledo et Tiskin, « Communication lower bounds for distributed-memory matrix multiplication », J. Parallel Distrib. Comput., vol. 64, no 9, , p. 1017–1026 (DOI 10.1016/j.jpdc.2004.03.021)
- Agarwal, Balle, Gustavson et Joshi, « A three-dimensional approach to parallel matrix multiplication », IBM J. Res. Dev., vol. 39, no 5, , p. 575–582 (DOI 10.1147/rd.395.0575)
- Solomonik et Demmel, « Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms », Proceedings of the 17th International Conference on Parallel Processing, vol. Part II, , p. 90–109
- Bosagh Zadeh et Carlsson, « Dimension Independent Matrix Square Using MapReduce », {{Article}} : paramètre «
périodique
» manquant, paramètre «date
» manquant (lire en ligne, consulté le ) - Bae, S.E., T.-W. Shinn, T. Takaoka (2014) A faster parallel algorithm for matrix multiplication on a mesh array. Procedia Computer Science 29: 2230-2240
- Kak, S. (1988) A two-layered mesh array for matrix multiplication. Parallel Computing 6: 383-385
- Kak, S. (2014) Efficiency of matrix multiplication on the cross-wired mesh array. https://arxiv.org/abs/1411.3273
[[Catégorie:Pages avec des traductions non relues]]