Complexité de la multiplication de matrices

En informatique théorique, la complexité de la multiplication de matrices est le nombre d'opérations requises pour l'opération de produit matriciel. Les algorithmes de multiplication de matrices constituent un sujet central dans les algorithmes théoriques et numériques en algèbre linéaire numérique et en optimisation, donc déterminer la complexité en temps du produit est d'une importance pratique.

L'application directe de la définition mathématique de la multiplication de matrices donne un algorithme qui nécessite opérations sur le corps de base pour multiplier deux matrices d'ordre . Il existe des algorithmes qui demandent moins d'opérations que le simple « algorithme naïf ». Le premier de ces algorithmes est l'algorithme de Strassen, conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide »[1]. Le nombre minimal d'opérations du corps de base nécessaires pour multiplier deux matrices carrées d'ordre est encore inconnu en 2023. Il s'agit là d'une question ouverte majeure en informatique théorique. Toutefois, ce nombre est au moins d'ordre .

En octobre 2022, la meilleure complexité en temps de multiplication de matrices est , valeur annoncée par Ran Duan, Hongxun Wu et Renfei Zhou dans une prépublication[2]. Cette borne améliore la borne de donnée par Josh Alman et Virginia Vassilevska Williams[3],[4]. Cependant, cette amélioration et d'autres améliorations similaires de l'algorithme de Strassen ne sont pas utilisées en pratique, car elles sont des « algorithmes galactiques » en ce sens que la constante du est si élevée qu'ils ne sont utiles que pour les matrices trop grandes pour être traitées par les ordinateurs actuels.

Algorithmes simples

modifier

Si   et   sont deux matrices d'ordre   sur un anneau, leur produit   est aussi une matrice d'ordre   sur cet anneau, dont les entrées sont :

 .

Algorithme élémentaire

modifier

L'approche la plus simple pour calculer le produit de deux matrices   et   d'ordre   consiste à évaluer les expressions arithmétiques issues de la définition de la multiplication matricielle.

Cet algorithme nécessite, dans le pire des cas   multiplications et   additions scalaires pour calculer le produit de deux matrices carrées d'ordre  . Sa complexité de calcul est   dans un modèle de calcul où les opérations élémentaires d'addition et de multiplication prennent un temps constant (en pratique, c'est le cas pour les nombres en virgule flottante, mais pas nécessairement pour les entiers).

Algorithme de Strassen

modifier

L'algorithme de Strassen améliore la multiplication matricielle naïve grâce à une approche diviser pour régner.

L'observation clé est que la multiplication de deux matrices de taille 2 peut être effectuée avec seulement 7 multiplications, au lieu des 8 habituelles, au prix de 11 opérations d'addition et de soustraction supplémentaires. Ainsi, en traitant les matrices de taille   comme des matrices à entrées en blocs de taille 2, la multiplication des matrices de taille   peut être réduite à 7 sous-problèmes de multiplication des matrices de taille  . L'application récursive de cette démarche donne un algorithme nécessitant   opérations scalaires.

Contrairement aux algorithmes qui ont une complexité asymptotique meilleure, l'algorithme de Strassen est utilisable et utilisé dans la pratique. La stabilité numérique est moins bonne que pour l'algorithme naïf[5], mais la multiplication est plus rapide pour  [6] et l'algorithme figure dans plusieurs bibliothèques de programmes, telles que BLAS[7]. Les algorithmes de multiplication matricielle rapide ne peuvent pas atteindre la « stabilité par composant, mais certains peuvent afficher une « stabilité par norme »[8]. L'algorithme est utile pour les grandes matrices sur des domaines exacts tels que les corps finis, où la stabilité numérique ne pose pas de problème.

Exposant de la multiplication matricielle

modifier
 
Amélioration successives des estimations de l'exposant   de la complexité de calcul de la multiplication matricielle  .
Chronologie de l'exposant de multiplication matricielle
Année Oméga Auteurs
1969 2,8074 Strassen[1]
1978 2,796 Pan[9]
1979 2,780 Bini, Capovani, Romani, Lotti[10]
1981 2,522 Schönhage[11]
1981 2,517 Romani[12]
1981 2,496 Coppersmith, Winograd[13]
1986 2,479 Strassen[14]
1990 2,3755 Coppersmith, Winograd[15]
2010 2,3737 Stothers[16]
2013 2.3729 Williams[17],[18]
2014 2.3728639 Le Gall[19]
2020 2.3728596 Alman, Williams[3]
2022 2.371866 Duan, Wu, Zhou[2]

L'exposant de la multiplication matricielle, généralement noté ω, est le plus petit nombre réel pour lequel deux matrices de taille   sur un corps peuvent être multipliées en utilisant   opérations élémentaires.

La borne inférieure naïve et la multiplication élémentaire de matrices donnent l'encadrement 2 ≤ ω ≤ 3. Il existe une série d'algorithmes de multiplication matricielle pour améliorer ces bornes sur ω.

Avant l'algorithme de Duan, Wu et Zhou, la meilleure borne sur ω était ω < 2,3728596, due à Josh Alman et Virginia Vassilevska Williams[3]. Cet algorithme, comme tous les autres algorithmes récents dans cette direction de recherche, utilise une méthode dite méthode laser, qui est une généralisation de l'algorithme donné par Don Coppersmith et Shmuel Winograd en 1990 et qui était le meilleur algorithme de multiplication matricielle jusqu'en 2010. L'idée fondamentale de ces algorithmes est similaire à l'algorithme de Strassen : c'est une méthode pour multiplier deux matrices k × k avec moins de k3 multiplications, et qui applique la technique de manière récursive. La méthode laser a des limites sur l'exposant et ne peut pas être utilisée pour montrer que ω < 2,3725[20]. Duan, Wu et Zhou identifient une source d'amélioration dans la méthode laser appelée « perte de combinaison »[2]. Ils l'exploitent dans une variante de la méthode laser qu'ils utilisent pour montrer ω < 2,37188, améliorant ainsi la barrière de la méthode laser conventionnelle. Avec cette nouvelle approche, une autre limite[20] s'applique selon Duan, Wu et Zhou et qui montre qu'à son tour la valeur ω < 2,3078 ne peut être franchie uniquement en traitant la perte de combinaison dans la méthode laser.

Algorithmes de multiplication matricielle et théorie des groupes

modifier

Henry Cohn, Robert Kleinberg, Balázs Szegedy et Chris Umans[21],[22] placent les méthodes telles que les algorithmes de Strassen et de Coppersmith–Winograd dans le contexte entièrement différent de théorie des groupes, en utilisant des triplets de sous-ensembles de groupes finis qui satisfont une propriété de disjonction appelée la propriété du triple produit (en) (abrégée en PTP). Ils énoncent également un ensemble de conjectures qui, si elles sont vraies, impliqueraient qu'il existe des algorithmes de multiplication matricielle avec une complexité essentiellement quadratique. Cela démontrerait que l'exposant optimal de la multiplication matricielle est 2, ce qui est effectivement conjecturé. Une de ces conjectures est que les familles de produits en couronne de groupes abéliens avec des groupes symétriques réalisent des familles de triplets de sous-ensembles avec une version simultanée du PTP. Plusieurs de leurs conjectures ont depuis été réfutées par Blasiak, Cohn, Church, Grochow, Naslund, Sawin et Umans en utilisant la méthode dite du Slice Rank[23]. De plus, Alon, Shpilka et Chris Umans ont montré que certaines de ces conjectures impliquant l'existence d'une multiplication matricielle rapide sont incompatibles avec une autre conjecture plausible, la conjecture du tournesol[24].

Bornes inférieures pour ω

modifier

Il existe une borne inférieure triviale pour ω, à savoir ω ≥ 2. Étant donné que tout algorithme de multiplication de deux matrices de taille   doit traiter toutes les   entrées, il existe une borne inférieure asymptotique triviale d'opérations   pour tout algorithme de multiplication de matrices. On ne sait pas si ω > 2. Une borne inférieure est  , et concerne les circuits arithmétiques à coefficients bornés sur les nombres réels ou complexes, et elle est due à Ran Raz[25].

L'exposant ω est un point d'accumulation, en ce sens qu'il est le minimum de l'exposant, pris sur tout algorithme de multiplication matricielle. On sait que ce point d'accumulation n'est pas atteint. En d'autres termes, dans le modèle de calcul usuel, il n'y a pas d'algorithme de multiplication matricielle qui utilise exactement   opérations : il y au moins un facteur supplémentaire en  [13].

Multiplication de matrices rectangulaires

modifier

Des techniques similaires s'appliquent à la multiplication de matrices rectangulaires. L'objet d'étude central est  , qui est le plus petit exposant   tel que l'on peut multiplier une matrice de taille   avec une matrice de taille   en   opérations arithmétiques. Un résultat en complexité algébrique montre que la multiplication des matrices de taille   et   nécessite le même nombre d'opérations arithmétiques que la multiplication de matrices de taille   et   et de taille   et  , de sorte que cela englobe la complexité de la multiplication matricielle rectangulaire[26]. Cela généralise l'exposant de multiplication de matrice carrée, puisque  .

Comme la sortie du problème de multiplication matricielle est de taille  , on a   pour toutes les valeurs de  . Si l'on peut prouver pour certaines valeurs de   entre 0 et 1 que  , alors un tel résultat montre que   pour ces  . Le plus grand k tel que   est connu sous le nom d'« exposant dual de multiplication de matrices », généralement noté   ; il est appelé le « dual » car montrer que   équivaut à montrer que  . Comme l'exposant de multiplication matricielle, l'exposant dual de multiplication matricielle apparaît parfois dans la complexité des algorithmes d'algèbre linéaire numérique et d'optimisation[27].

La première borne sur   est celle de Coppersmith en 1982, qui a montré que   [28]. La meilleure borne connue sur   est  , donnée par Le Gall et Urrutia[26]. Cet article contient également des bornes sur  .

Problèmes connexes

modifier

Les problèmes qui ont la même complexité asymptotique que la multiplication matricielle comprennent le déterminant, l'inversion matricielle, l'élimination gaussienne. Les problèmes dont la complexité s'exprime en termes de   comprennent le polynôme caractéristique, les valeurs propres (mais pas les vecteurs propres).

Inversion de matrice, déterminant et élimination gaussienne

modifier

Dans son article de 1969, où il prouve la complexité   pour le calcul matriciel, Strassen a également prouvé que l'inversion matricielle, le calcul du déterminant et l'élimination gaussienne ont, à une constante multiplicative près, la même complexité de calcul que la multiplication matricielle. La preuve ne fait aucune hypothèse sur la multiplication matricielle utilisée, sauf que sa complexité est   pour certains   ≥ 2.

Le point de départ de la preuve de Strassen utilise la multiplication matricielle par blocs. Plus précisément, une matrice de dimension paire   peut être partitionnée en quatre blocs de taille   :

 

Sous cette forme, son inverse est

 

pourvu que   et son complément de Schur   soient inversibles.

Ainsi, l'inverse d'une matrice de taille   peut être calculée avec deux inversions, six multiplications et quatre additions ou inverses additifs de matrices  . En notant respectivement  ,   et   le nombre d'opérations nécessaires pour inverser, multiplier et additionner de matrices de taille  , on obtient

 .

Pour   on peut appliquer cette formule récursivement,

 

et pour  , et  , on obtient finalement

 

pour une constante d. Ceci prouve la complexité annoncée pour les matrices telles que toutes les sous-matrices qui doivent être inversées sont inversibles. Cette complexité est donc prouvée pour presque toutes les matrices, car une matrice avec des entrées choisies au hasard est inversible avec probabilité 1.

Le même argument s'applique à la décomposition LU, car, si la matrice A est inversible, l'égalité

 

définit une décomposition LU par blocs qui peut être appliquée récursivement à   et à   pour obtenir finalement une décomposition LU de la matrice d'origine.

L'argument s'applique également au déterminant, puisqu'il résulte de la décomposition LU par blocs que

 .

Minimiser le nombre d'opérations

modifier

Le problème de la minimisation du nombre d'opérations arithmétiques est lié à la minimisation du nombre de multiplications, qui est généralement une opération plus coûteuse que l'addition, mais ces algorithmes ne sont pas pratiques, notamment pour des petites matrices. On peut améliorer la méthode usuelle en   multiplications ; ainsi des matrices de taille 4 dans   peuvent être multipliées en 47 multiplications[29] ; des matrices de taille 3 sur un anneau commutatif, peuvent être multipliées en 21 multiplications [30],[31],[32] (23 si l'anneau n'est pas commutatif [33]). La borne inférieure des multiplications nécessaires est   (multiplication d'une matrice   par une matrice  , avec  ), ce qui signifie que le cas   nécessite au moins 19 multiplications et le cas   au moins 34[34]. Pour  , les 7 multiplications et 15 additions sont minimales, contre seulement 4 additions avec 8 multiplications[35],[36],[37].

Articles liés

modifier

Références

modifier
  1. a et b (en) Volker Strassen, « Gaussian elimination is not optimal », Numerische Mathematik, vol. 13, no 4,‎ , p. 354-356 (DOI 10.1007/BF02165411, S2CID 121656251, lire en ligne).
  2. a b et c (en) Ran Duan, Hongxun Wu et Renfei Zhou, « Faster Matrix Multiplication via Asymmetric Hashing », Arxiv,‎ (arXiv 2210.10173).
  3. a b et c (en) Josh Alman et Virginia Vassilevska Williams, « A Refined Laser Method and Faster Matrix Multiplication », 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021),‎ , p. 522-539 (arXiv 2010.05846, lire en ligne)
  4. (en) Hartnett, « Matrix Multiplication Inches Closer to Mythic Goal », Quanta Magazine, (consulté le ).
  5. (en) Webb Miller, « Computational complexity and numerical stability », SIAM News, vol. 4, no 2,‎ , p. 97–107 (DOI 10.1137/0204009, CiteSeerx 10.1.1.148.9947)
  6. (en) Steven Skiena, The Algorithm Design Manual, Springer, (ISBN 978-1-84800-069-8, DOI 10.1007/978-1-84800-070-4_4, lire en ligne), « Sorting and Searching », p. 45–46, 401–403.
  7. (en) William H. Press, Brian P. Flannery, Saul A. Teukolsky et William T. Vetterling, Numerical Recipes: The Art of Scientific Computing, , 3e éd. (ISBN 978-0-521-88068-8), 108.
  8. (en) Grey Ballard, Austin R. Benson, Alex Druinsky, Benjamin Lipshitz et Oded Schwartz, « Improving the numerical stability of fast matrix multiplication », SIAM Journal on Matrix Analysis and Applications, vol. 37, no 4,‎ , p. 1382–1418 (DOI 10.1137/15M1032168, arXiv 1507.00687, S2CID 2853388).
  9. (en) Victor Y. Pan, « Strassen's Algorithm is not Optimal: Trilinear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations », Proc. 19th FOCS,‎ , p. 166-176 (DOI 10.1109/SFCS.1978.34, S2CID 14348408).
  10. (en) Dario Andrea Bini, Milvio Capovani, Francesco Romani et Grazia Lotti, «   complexity for   approximate matrix multiplication », Information Processing Letters, vol. 8, no 5,‎ , p. 234-235 (DOI 10.1016/0020-0190(79)90113-3, lire en ligne).
  11. (en) Arnold Schönhage, « Partial and total matrix multiplication », SIAM Journal on Computing, vol. 10, no 3,‎ , p. 434-455 (DOI 10.1137/0210032).
  12. (en) Francesco Romani, « Some properties of disjoint sums of tensors related to matrix multiplication », SIAM Journal on Computing, vol. 11, no 2,‎ , p. 263-267 (DOI 10.1137/0211020).
  13. a et b (en) Don Coppersmith et Shmuel Winograd, « On the asymptotic complexity of matrix multiplication », Proc. 22nd Annual Symposium on Foundations of Computer Science (FOCS),‎ , p. 82-90 (DOI 10.1109/SFCS.1981.27, S2CID 206558664).
  14. (en) Volker Strassen, « The asymptotic spectrum of tensors and the exponent of matrix multiplication », Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS),‎ , p. 49-54 (DOI 10.1109/SFCS.1986.52, S2CID 15077423).
  15. (en) Don Coppersmith et Shmuel Winograd, « Matrix multiplication via arithmetic progressions », Journal of Symbolic Computation, vol. 9, no 3,‎ , p. 251-280 (DOI 10.1016/S0747-7171(08)80013-2  ).
  16. (en) Andrew James Stothers, On the complexity of matrix multiplication (thèse Ph.D.), University of Edinburgh, (lire en ligne).
  17. (en) Virginia V. Williams, « Multiplying Matrices Faster than Coppersmith-Winograd », Proc. 44th Symposium on Theory of Computing (STOC), ACM,‎ , p. 887-898 (DOI 10.1145/2213977.2214056, S2CID 14350287).
  18. (en) Virginia Vassilevska Williams, Multiplying matrices in   time (Technical Report), Stanford University (lire en ligne).
  19. (en) Jean-François Le Gall, « Algebraic complexity theory and matrix multiplication », Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14,‎ , p. 296-303 (DOI 10.1145/2608628.2627493, Bibcode 2014arXiv1401.7714L, arXiv 1401.7714, S2CID 2597483)
  20. a et b (en) Ambainis, Filmus et Le Gall, « Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method », Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15), Portland, Oregon, USA, Association for Computing Machinery,‎ , p. 585–593 (ISBN 978-1-4503-3536-2, DOI 10.1145/2746539.2746554, arXiv 1411.5414, S2CID 8332797, lire en ligne).
  21. (en) Henry Cohn, R. Kleinberg, B. Szegedy et Chris Umans, « Group-theoretic Algorithms for Matrix Multiplication », 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05),‎ , p. 379 (DOI 10.1109/SFCS.2005.39, S2CID 41278294, lire en ligne).
  22. (en) Henry Cohn et Chris Umans, « A Group-theoretic Approach to Fast Matrix Multiplication », Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003, IEEE Computer Society,‎ , p. 438–449 (DOI 10.1109/SFCS.2003.1238217, arXiv math.GR/0307321, S2CID 5890100).
  23. (en) J. Blasiak, H. Cohn, T. Church, J. Grochow, Naslund, Sawin et Umans, « On cap sets and the group-theoretic approach to matrix multiplication », Discrete Analysis,‎ , p. 1245 (DOI 10.19086/da.1245, S2CID 9687868, lire en ligne).
  24. (en) Alon, Shpilka et Umans, « On Sunflowers and Matrix Multiplication », Electronic Colloquium on Computational Complexity,‎ (lire en ligne).
  25. (en) Ran Raz, « On the complexity of matrix product », Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing,‎ , p. 144–151 (ISBN 1581134959, DOI 10.1145/509907.509932, S2CID 9582328).
  26. a et b (en) Francois Le Gall et Florent Urrutia, « Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor », Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics,‎ , p. 1029–1046 (DOI 10.1137/1.9781611975031.67, arXiv 1708.05622, S2CID 33396059, lire en ligne).
  27. (en) Michael B. Cohen, Yin Tat Lee et Zhao Song, « Solving Linear Programs in the Current Matrix Multiplication Time », Journal of the ACM, vol. 68, no 1,‎ , p. 3:1–3:39 (DOI 10.1145/3424305, arXiv 1810.07896, S2CID 231955576).
  28. (en) D. Coppersmith, « Rapid Multiplication of Rectangular Matrices », SIAM Journal on Computing, vol. 11, no 3,‎ , p. 467–471 (ISSN 0097-5397, DOI 10.1137/0211037, lire en ligne).
  29. (en) Fawzi, A., Balog, M., Huang, A. et al., « Discovering faster matrix multiplication algorithms with reinforcement learning », Nature, no 610,‎ , p. 47–53 (DOI 10.1038/s41586-022-05172-4  , lire en ligne).
  30. (en) Andreas Rosowski, « Fast Commutative Matrix Algorithm », Arxiv,‎ (arXiv 1904.07683)
  31. O. M. Makarov, « An algorithm for multiplying 3×3 matrices », U.S.S.R. Comput. Math. Math. Phys., vol. 26, no 1,‎ , p. 179-180.
  32. (en) O. M. Makarov, « A noncommutative algorithm for multiplying 5×5 matrices using 102 multiplications », Inf. Process. Lett., vol. 23, no 3,‎ , p. 115-117 (zbMATH 0614.65037).
  33. (en) Julian D. Laderman, « A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications », Bulletin of the American Mathematical Society, vol. 82, no 1,‎ , p. 126–128 (DOI 10.1090/S0002-9904-1976-13988-2, lire en ligne).
  34. Markus Bläser, « On the complexity of the multiplication of matrices of small formats », Journal of Complexity, vol. 19, no 1,‎ , p. 43–60 (DOI 10.1016/S0885-064X(02)00007-9).
  35. (en) Shmuel Winograd, « On multiplication of 2 × 2 matrices », Linear Algebra and Its Applications, vol. 4, no 4,‎ , p. 381–388 (DOI 10.1016/0024-3795(71)90009-7).
  36. (en) Robert L. Probert, On the complexity of matrix multiplication, University of Waterloo, (OCLC 1124200063).
  37. (en) Robert L. Probert et Patrick Carl Fischer, « Decomposition techniques for matrix multiplication problems », Utilitas Mathematica, vol. 18,‎ , p. 257-267.

Liens externes

modifier