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 $\Theta \left(n^{3}\right)$ opérations sur le corps de base pour multiplier deux matrices d'ordre $n$ . 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 $n$ 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 $n^{2}$ .

En octobre 2022, la meilleure complexité en temps de multiplication de matrices est $O\left(n^{2,37188}\right)$ , valeur annoncée par Ran Duan, Hongxun Wu et Renfei Zhou dans une prépublication^[2]. Cette borne améliore la borne de $O\left(n^{2,3728596}\right)$ 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 $O$ 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 | modifier le code]

Article détaillé : Produit matriciel.

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

(AB)_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj}

.

Algorithme élémentaire[modifier | modifier le code]

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

Cet algorithme nécessite, dans le pire des cas $n^{3}$ multiplications et $n^{3}-n^{2}$ additions scalaires pour calculer le produit de deux matrices carrées d'ordre $n$ . Sa complexité de calcul est $O\left(n^{3}\right)$ 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 | modifier le code]

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 $n$ comme des matrices à entrées en blocs de taille 2, la multiplication des matrices de taille $n$ peut être réduite à 7 sous-problèmes de multiplication des matrices de taille $n/2$ . L'application récursive de cette démarche donne un algorithme nécessitant $O\left(n^{\log _{2}7}\right)\approx O\left(n^{2,807}\right)$ 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 $n>100$ ^[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 | modifier le code]

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 $n$ sur un corps peuvent être multipliées en utilisant $n^{\omega +o(1)}$ 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 \times k$ avec moins de $k 3$ 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 | modifier le code]

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 | modifier le code]

Il existe une borne inférieure triviale pour $ω$ , à savoir $ω$ ≥ 2. Étant donné que tout algorithme de multiplication de deux matrices de taille $n$ doit traiter toutes les $2n^{2}$ entrées, il existe une borne inférieure asymptotique triviale d'opérations $\Omega \left(n^{2}\right)$ pour tout algorithme de multiplication de matrices. On ne sait pas si $ω$ > 2. Une borne inférieure est $\Omega \left(n^{2}\right)\log n$ , 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 $O\left(n^{\omega }\right)$ opérations : il y au moins un facteur supplémentaire en $n^{o(1)}$ ^[13].

Multiplication de matrices rectangulaires[modifier | modifier le code]

Des techniques similaires s'appliquent à la multiplication de matrices rectangulaires. L'objet d'étude central est $\omega (k)$ , qui est le plus petit exposant $c$ tel que l'on peut multiplier une matrice de taille $n\times \left\lceil n^{k}\right\rceil$ avec une matrice de taille $\left\lceil n^{k}\right\rceil \times n$ en $O\left(n^{c+o(1)}\right)$ opérations arithmétiques. Un résultat en complexité algébrique montre que la multiplication des matrices de taille $n\times \left\lceil n^{k}\right\rceil$ et $\left\lceil n^{k}\right\rceil \times n$ nécessite le même nombre d'opérations arithmétiques que la multiplication de matrices de taille $n\times \left\lceil n^{k}\right\rceil$ et $n\times n$ et de taille $n\times n$ et $n\times \left\lceil n^{k}\right\rceil$ , 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 $\omega (1)=\omega$ .

Comme la sortie du problème de multiplication matricielle est de taille $n^{2}$ , on a $\omega (k)\geq 2$ pour toutes les valeurs de $k$ . Si l'on peut prouver pour certaines valeurs de $k$ entre 0 et 1 que $\omega (k)\leq 2$ , alors un tel résultat montre que $\omega (k)=2$ pour ces $k$ . Le plus grand k tel que $\omega (k)=2$ est connu sous le nom d'« exposant dual de multiplication de matrices », généralement noté $\alpha$ ; il est appelé le « dual » car montrer que $\alpha =1$ équivaut à montrer que $\omega =2$ . 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 $\alpha$ est celle de Coppersmith en 1982, qui a montré que $\alpha >0,17227$ ^[28]. La meilleure borne connue sur $\alpha$ est $\alpha >0,31389$ , donnée par Le Gall et Urrutia^[26]. Cet article contient également des bornes sur $\omega (k)$ .

Problèmes connexes[modifier | modifier le code]

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 $\omega$ comprennent le polynôme caractéristique, les valeurs propres (mais pas les vecteurs propres).

Inversion de matrice, déterminant et élimination gaussienne[modifier | modifier le code]

Dans son article de 1969, où il prouve la complexité $O\left(n^{\log _{2}7}\right)\approx O\left(n^{2.807}\right)$ 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 $O\left(n^{\omega }\right)$ pour certains $\omega$ ≥ 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 $(2n,2n)$ peut être partitionnée en quatre blocs de taille $(n,n)$ :

{\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.

Sous cette forme, son inverse est

{\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},

pourvu que $A$ et son complément de Schur ${D}-{CA}^{-1}{B}$ soient inversibles.

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

I(2n)\leq 2I(n)+6M(n)+4A(n)

.

Pour $n=2^{k}$ on peut appliquer cette formule récursivement,

{\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}

et pour $M(n)\leq cn^{\omega }$ , et $\alpha =2^{\omega }\geq 4$ , on obtient finalement

{\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\leq d\left(2^{k}\right)^{\omega }\end{aligned}}

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é

{\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}

définit une décomposition LU par blocs qui peut être appliquée récursivement à $A$ et à $D-CA^{-1}B,$ 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

\det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det \left(D-CA^{-1}B\right)

.

Minimiser le nombre d'opérations[modifier | modifier le code]

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 $n^{3}$ multiplications ; ainsi des matrices de taille 4 dans $\mathbb {Z} /2\mathbb {Z}$ 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 $2mn+2n-m-2$ (multiplication d'une matrice $(n,m)$ par une matrice $(m,n)$ , avec $m\geq n\geq 3$ ), ce qui signifie que le cas $n=3$ nécessite au moins 19 multiplications et le cas $n=4$ au moins 34^[34]. Pour $n=2$ , les 7 multiplications et 15 additions sont minimales, contre seulement 4 additions avec 8 multiplications^[35]^,^[36]^,^[37].

Articles liés[modifier | modifier le code]

Algorithme de Cocke-Younger-Kasami
Algorithme de Freivalds, un simple algorithme de Monte-Carlo qui, étant donné les matrices $A$ , $B$ et $C$ , vérifie en temps $\Theta \left(n^{2}\right)$ si $AB=C$ .
Problème des multiplications matricielles enchaînées
Produit matriciel, pour les définitions abstraites
Matrice creuse.

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Computational complexity of matrix multiplication » (voir la liste des auteurs).

↑ ^{a et b} (en) Volker Strassen, « Gaussian elimination is not optimal », Numerische Mathematik, vol. 13, n^o 4,‎ août 1969, p. 354-356 (DOI 10.1007/BF02165411, S2CID 121656251, lire en ligne).
↑ ^{a b et c} (en) Ran Duan, Hongxun Wu et Renfei Zhou, « Faster Matrix Multiplication via Asymmetric Hashing », Arxiv,‎ 2022 (arXiv 2210.10173).
↑ ^{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),‎ 2020, p. 522-539 (arXiv 2010.05846, lire en ligne)
↑ (en) Hartnett, « Matrix Multiplication Inches Closer to Mythic Goal », Quanta Magazine, 23 mars 2021 (consulté le 1^er avril 2021).
↑ (en) Webb Miller, « Computational complexity and numerical stability », SIAM News, vol. 4, n^o 2,‎ 1975, p. 97–107 (DOI 10.1137/0204009, CiteSeer^x 10.1.1.148.9947)
↑ (en) Steven Skiena, The Algorithm Design Manual, Springer, 2008 (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.
↑ (en) William H. Press, Brian P. Flannery, Saul A. Teukolsky et William T. Vetterling, Numerical Recipes: The Art of Scientific Computing, 2007, 3^e éd. (ISBN 978-0-521-88068-8), 108.
↑ (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, n^o 4,‎ 2016, p. 1382–1418 (DOI 10.1137/15M1032168, arXiv 1507.00687, S2CID 2853388).
↑ (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,‎ octobre 1978, p. 166-176 (DOI 10.1109/SFCS.1978.34, S2CID 14348408).
↑ (en) Dario Andrea Bini, Milvio Capovani, Francesco Romani et Grazia Lotti, « $O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication », Information Processing Letters, vol. 8, n^o 5,‎ juin 1979, p. 234-235 (DOI 10.1016/0020-0190(79)90113-3, lire en ligne).
↑ (en) Arnold Schönhage, « Partial and total matrix multiplication », SIAM Journal on Computing, vol. 10, n^o 3,‎ 1981, p. 434-455 (DOI 10.1137/0210032).
↑ (en) Francesco Romani, « Some properties of disjoint sums of tensors related to matrix multiplication », SIAM Journal on Computing, vol. 11, n^o 2,‎ 1982, p. 263-267 (DOI 10.1137/0211020).
↑ ^{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),‎ 1981, p. 82-90 (DOI 10.1109/SFCS.1981.27, S2CID 206558664).
↑ (en) Volker Strassen, « The asymptotic spectrum of tensors and the exponent of matrix multiplication », Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS),‎ octobre 1986, p. 49-54 (DOI 10.1109/SFCS.1986.52, S2CID 15077423).
↑ (en) Don Coppersmith et Shmuel Winograd, « Matrix multiplication via arithmetic progressions », Journal of Symbolic Computation, vol. 9, n^o 3,‎ mars 1990, p. 251-280 (DOI 10.1016/S0747-7171(08)80013-2 ).
↑ (en) Andrew James Stothers, On the complexity of matrix multiplication (thèse Ph.D.), University of Edinburgh, 2010 (lire en ligne).
↑ (en) Virginia V. Williams, « Multiplying Matrices Faster than Coppersmith-Winograd », Proc. 44th Symposium on Theory of Computing (STOC), ACM,‎ 2012, p. 887-898 (DOI 10.1145/2213977.2214056, S2CID 14350287).
↑ (en) Virginia Vassilevska Williams, Multiplying matrices in $O(n^{2.373})$ time (Technical Report), Stanford University (lire en ligne).
↑ (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,‎ 2014, p. 296-303 (DOI 10.1145/2608628.2627493, Bibcode 2014arXiv1401.7714L, arXiv 1401.7714, S2CID 2597483)
↑ ^{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,‎ 14 juin 2015, p. 585–593 (ISBN 978-1-4503-3536-2, DOI 10.1145/2746539.2746554, arXiv 1411.5414, S2CID 8332797, lire en ligne).
↑ (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),‎ 2005, p. 379 (DOI 10.1109/SFCS.2005.39, S2CID 41278294, lire en ligne).
↑ (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,‎ 2003, p. 438–449 (DOI 10.1109/SFCS.2003.1238217, arXiv math.GR/0307321, S2CID 5890100).
↑ (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,‎ 2017, p. 1245 (DOI 10.19086/da.1245, S2CID 9687868, lire en ligne).
↑ (en) Alon, Shpilka et Umans, « On Sunflowers and Matrix Multiplication », Electronic Colloquium on Computational Complexity,‎ avril 2011 (lire en ligne).
↑ (en) Ran Raz, « On the complexity of matrix product », Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing,‎ 2002, p. 144–151 (ISBN 1581134959, DOI 10.1145/509907.509932, S2CID 9582328).
↑ ^{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,‎ 1^er janvier 2018, p. 1029–1046 (DOI 10.1137/1.9781611975031.67, arXiv 1708.05622, S2CID 33396059, lire en ligne).
↑ (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, n^o 1,‎ 5 janvier 2021, p. 3:1–3:39 (DOI 10.1145/3424305, arXiv 1810.07896, S2CID 231955576).
↑ (en) D. Coppersmith, « Rapid Multiplication of Rectangular Matrices », SIAM Journal on Computing, vol. 11, n^o 3,‎ 1^er août 1982, p. 467–471 (ISSN 0097-5397, DOI 10.1137/0211037, lire en ligne).
↑ (en) Fawzi, A., Balog, M., Huang, A. et al., « Discovering faster matrix multiplication algorithms with reinforcement learning », Nature, n^o 610,‎ 5 octobre 2022, p. 47–53 (DOI 10.1038/s41586-022-05172-4 , lire en ligne).
↑ (en) Andreas Rosowski, « Fast Commutative Matrix Algorithm », Arxiv,‎ 27 juillet 2020 (arXiv 1904.07683)
↑ O. M. Makarov, « An algorithm for multiplying 3×3 matrices », U.S.S.R. Comput. Math. Math. Phys., vol. 26, n^o 1,‎ 1986, p. 179-180.
↑ (en) O. M. Makarov, « A noncommutative algorithm for multiplying 5×5 matrices using 102 multiplications », Inf. Process. Lett., vol. 23, n^o 3,‎ 1986, p. 115-117 (zbMATH 0614.65037).
↑ (en) Julian D. Laderman, « A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications », Bulletin of the American Mathematical Society, vol. 82, n^o 1,‎ 1976, p. 126–128 (DOI 10.1090/S0002-9904-1976-13988-2, lire en ligne).
↑ Markus Bläser, « On the complexity of the multiplication of matrices of small formats », Journal of Complexity, vol. 19, n^o 1,‎ février 2003, p. 43–60 (DOI 10.1016/S0885-064X(02)00007-9).
↑ (en) Shmuel Winograd, « On multiplication of 2 × 2 matrices », Linear Algebra and Its Applications, vol. 4, n^o 4,‎ 1^er octobre 1971, p. 381–388 (DOI 10.1016/0024-3795(71)90009-7).
↑ (en) Robert L. Probert, On the complexity of matrix multiplication, University of Waterloo, 1973 (OCLC 1124200063).
↑ (en) Robert L. Probert et Patrick Carl Fischer, « Decomposition techniques for matrix multiplication problems », Utilitas Mathematica, vol. 18,‎ 1980, p. 257-267.

Liens externes[modifier | modifier le code]

« Encore un autre catalogue d'algorithmes de multiplication matricielle rapide », sur Université de Lille.

[strassen69-1] {a et b} (en) Volker Strassen, « Gaussian elimination is not optimal », Numerische Mathematik, vol. 13, n^o 4,‎ août 1969, p. 354-356 (DOI 10.1007/BF02165411, S2CID 121656251, lire en ligne).

[dwz22-2] {a b et c} (en) Ran Duan, Hongxun Wu et Renfei Zhou, « Faster Matrix Multiplication via Asymmetric Hashing », Arxiv,‎ 2022 (arXiv 2210.10173).

[aw20-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),‎ 2020, p. 522-539 (arXiv 2010.05846, lire en ligne)

[4] (en) Hartnett, « Matrix Multiplication Inches Closer to Mythic Goal », Quanta Magazine, 23 mars 2021 (consulté le 1^er avril 2021).

[5] (en) Webb Miller, « Computational complexity and numerical stability », SIAM News, vol. 4, n^o 2,‎ 1975, p. 97–107 (DOI 10.1137/0204009, CiteSeer^x 10.1.1.148.9947)

[skiena-6] (en) Steven Skiena, The Algorithm Design Manual, Springer, 2008 (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, 2007, 3^e éd. (ISBN 978-0-521-88068-8), 108.

[bdl16-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, n^o 4,‎ 2016, 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,‎ octobre 1978, p. 166-176 (DOI 10.1109/SFCS.1978.34, S2CID 14348408).

[10] (en) Dario Andrea Bini, Milvio Capovani, Francesco Romani et Grazia Lotti, « $O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication », Information Processing Letters, vol. 8, n^o 5,‎ juin 1979, 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, n^o 3,‎ 1981, 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, n^o 2,‎ 1982, p. 263-267 (DOI 10.1137/0211020).

[CW.81-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),‎ 1981, 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),‎ octobre 1986, 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, n^o 3,‎ mars 1990, 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, 2010 (lire en ligne).

[17] (en) Virginia V. Williams, « Multiplying Matrices Faster than Coppersmith-Winograd », Proc. 44th Symposium on Theory of Computing (STOC), ACM,‎ 2012, p. 887-898 (DOI 10.1145/2213977.2214056, S2CID 14350287).

[Williams.2014-18] (en) Virginia Vassilevska Williams, Multiplying matrices in $O(n^{2.373})$ time (Technical Report), Stanford University (lire en ligne).

[LeGall2014-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,‎ 2014, p. 296-303 (DOI 10.1145/2608628.2627493, Bibcode 2014arXiv1401.7714L, arXiv 1401.7714, S2CID 2597483)

[afl14-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,‎ 14 juin 2015, 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),‎ 2005, 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,‎ 2003, 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,‎ 2017, 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,‎ avril 2011 (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,‎ 2002, p. 144–151 (ISBN 1581134959, DOI 10.1145/509907.509932, S2CID 9582328).

[gall18-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,‎ 1^er janvier 2018, 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, n^o 1,‎ 5 janvier 2021, 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, n^o 3,‎ 1^er août 1982, 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, n^o 610,‎ 5 octobre 2022, p. 47–53 (DOI 10.1038/s41586-022-05172-4 , lire en ligne).

[30] (en) Andreas Rosowski, « Fast Commutative Matrix Algorithm », Arxiv,‎ 27 juillet 2020 (arXiv 1904.07683)

[31] O. M. Makarov, « An algorithm for multiplying 3×3 matrices », U.S.S.R. Comput. Math. Math. Phys., vol. 26, n^o 1,‎ 1986, p. 179-180.

[32] (en) O. M. Makarov, « A noncommutative algorithm for multiplying 5×5 matrices using 102 multiplications », Inf. Process. Lett., vol. 23, n^o 3,‎ 1986, 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, n^o 1,‎ 1976, 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, n^o 1,‎ février 2003, 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, n^o 4,‎ 1^er octobre 1971, 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, 1973 (OCLC 1124200063).

[37] (en) Robert L. Probert et Patrick Carl Fischer, « Decomposition techniques for matrix multiplication problems », Utilitas Mathematica, vol. 18,‎ 1980, p. 257-267.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]