Complejidad computacional de la multiplicación de matrices

Requisitos de tiempo de ejecución algorítmico para la multiplicación de matrices

Problema sin resolver en informática :

¿Cuál es el algoritmo más rápido para la multiplicación de matrices?

(más problemas sin resolver en informática)

En informática teórica , la complejidad computacional de la multiplicación de matrices determina la rapidez con la que se puede realizar la operación . Los algoritmos de multiplicación de matrices son una subrutina central en los algoritmos teóricos y numéricos para el álgebra lineal numérica y la optimización , por lo que encontrar el algoritmo más rápido para la multiplicación de matrices es de gran relevancia práctica.

La aplicación directa de la definición matemática de multiplicación de matrices da como resultado un algoritmo que requiere n ³ operaciones de campo para multiplicar dos matrices n × n sobre ese campo ( Θ( n ³ ) en notación O mayúscula ). Sorprendentemente, existen algoritmos que proporcionan mejores tiempos de ejecución que este sencillo "algoritmo de libro de texto". El primero en descubrirse fue el algoritmo de Strassen , ideado por Volker Strassen en 1969 y al que a menudo se hace referencia como "multiplicación rápida de matrices". ^[1] El número óptimo de operaciones de campo necesarias para multiplicar dos matrices cuadradas n × n hasta factores constantes aún se desconoce. Esta es una importante pregunta abierta en la informática teórica .

A partir de enero de 2024 ^[actualizar], el mejor límite de la complejidad asintótica de un algoritmo de multiplicación de matrices es O( n ^2,371552 ) . ^{[2] [3]} Sin embargo, esta y otras mejoras similares a Strassen no se utilizan en la práctica, porque son algoritmos galácticos : el coeficiente constante oculto por la notación O grande es tan grande que solo valen la pena para matrices que son demasiado grandes para manejarlas en las computadoras actuales. ^{[4] [5]}

Algoritmos simples

Si A , B son matrices n × n sobre un campo, entonces su producto AB también es una matriz n × n sobre ese campo, definida por entrada como

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

Algoritmo del libro escolar

El método más simple para calcular el producto de dos matrices A y B de n × n es calcular las expresiones aritméticas que surgen de la definición de multiplicación de matrices. En pseudocódigo:

entrada  A y B , ambas matrices n por n inicializan  C para que sea una matriz n por n de todos ceros para  i de 1 a n : para  j de 1 a n : para  k de 1 a n : C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ]* B [ k ][ j ] salida  C (como A*B)

Este algoritmo requiere, en el peor de los casos , multiplicaciones de escalares ${\displaystyle n^{3}}$ y sumas ${\displaystyle n^{3}-n^{2}}$ para calcular el producto de dos matrices cuadradas n × n . Por lo tanto , su complejidad computacional es ⁠ ⁠ ${\displaystyle O(n^{3})}$ , en un modelo de cálculo donde las operaciones de campo (suma y multiplicación) toman un tiempo constante (en la práctica, este es el caso de los números de punto flotante , pero no necesariamente de los enteros).

Algoritmo de Strassen

El algoritmo de Strassen mejora la multiplicación de matrices ingenua mediante un enfoque de divide y vencerás . La observación clave es que la multiplicación de dos matrices de 2 × 2 se puede realizar con solo 7 multiplicaciones, en lugar de las 8 habituales (a expensas de 11 operaciones de suma y resta adicionales). Esto significa que, al tratar las matrices de entrada n × n como matrices de bloque 2 × 2 , la tarea de multiplicar matrices n × n se puede reducir a 7 subproblemas de multiplicación de matrices n/2 × n/2 . La aplicación recursiva de esto da como resultado un algoritmo que necesita operaciones de campo. ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$

A diferencia de los algoritmos con una complejidad asintótica más rápida, el algoritmo de Strassen se utiliza en la práctica. La estabilidad numérica se reduce en comparación con el algoritmo ingenuo, ^[6] pero es más rápido en casos donde n > 100 o más ^[7] y aparece en varias bibliotecas, como BLAS . ^[8] Los algoritmos rápidos de multiplicación de matrices no pueden lograr estabilidad por componentes , pero se puede demostrar que algunos exhiben estabilidad por normas . ^[9] Es muy útil para matrices grandes sobre dominios exactos como campos finitos , donde la estabilidad numérica no es un problema.

Exponente de multiplicación de matrices

Mejora de las estimaciones del exponente ω a lo largo del tiempo para la complejidad computacional de la multiplicación de matrices ${\displaystyle O(n^{\omega })}$

Primer plano de 1990-2023

El exponente de multiplicación de matrices , que se suele denotar como ω , es el número real más pequeño para el cual dos matrices cualesquiera sobre un cuerpo pueden multiplicarse entre sí mediante operaciones de cuerpo. Esta notación se utiliza habitualmente en la investigación de algoritmos , de modo que los algoritmos que utilizan la multiplicación de matrices como subrutina tienen límites en el tiempo de ejecución que pueden actualizarse a medida que mejoran los límites de ω . ${\displaystyle n\times n}$ ${\displaystyle n^{\omega +o(1)}}$

Usando un límite inferior ingenuo y una multiplicación de matrices de libro para el límite superior, uno puede concluir directamente que 2 ≤ ω ≤ 3 . Si ω = 2 es una pregunta abierta importante en la ciencia informática teórica , y hay una línea de investigación que desarrolla algoritmos de multiplicación de matrices para obtener límites mejorados en ω .

Todos los algoritmos recientes en esta línea de investigación utilizan el método láser , una generalización del algoritmo Coppersmith-Winograd, que fue dado por Don Coppersmith y Shmuel Winograd en 1990 y fue el mejor algoritmo de multiplicación de matrices hasta 2010. ^[24] La idea conceptual de estos algoritmos es similar al algoritmo de Strassen: se idea una forma de multiplicar dos k × k -matrices con menos de k ³ multiplicaciones, y esta técnica se aplica de forma recursiva. El método láser tiene limitaciones en su potencia, Ambainis , Filmus y Le Gall demuestran que no se puede utilizar para mostrar que ω < 2,3725 analizando potencias tensoriales cada vez más altas de una cierta identidad de Coppersmith y Winograd y tampoco ω < 2,3078 para una amplia clase de variantes de este enfoque. ^[25] En 2022, Duan, Wu y Zhou idearon una variante que rompe la primera de las dos barreras con ω < 2,37188 , ^[23] lo hacen identificando una fuente de optimización potencial en el método láser denominada pérdida de combinación , que compensan utilizando una versión asimétrica del método hash en el algoritmo Coppersmith–Winograd.

Reformulación de la teoría de grupos de algoritmos de multiplicación de matrices

Henry Cohn , Robert Kleinberg , Balázs Szegedy y Chris Umans ponen métodos como los algoritmos de Strassen y Coppersmith–Winograd en un contexto de teoría de grupos completamente diferente, al utilizar triples de subconjuntos de grupos finitos que satisfacen una propiedad de disyunción llamada propiedad del producto triple (TPP) . También dan conjeturas que, de ser ciertas, implicarían que hay algoritmos de multiplicación de matrices con complejidad esencialmente cuadrática. Esto implica que el exponente óptimo de la multiplicación de matrices es 2, lo que la mayoría de los investigadores creen que es de hecho el caso. ^[5] Una de esas conjeturas es que las familias de productos de corona de grupos abelianos con grupos simétricos realizan familias de triples de subconjuntos con una versión simultánea de la TPP. ^{[26] [27]} Varias de sus conjeturas han sido refutadas desde entonces por Blasiak, Cohn, Church, Grochow, Naslund, Sawin y Umans utilizando el método Slice Rank. ^[28] Además, Alon, Shpilka y Chris Umans han demostrado recientemente que algunas de estas conjeturas que implican una multiplicación rápida de matrices son incompatibles con otra conjetura plausible, la conjetura del girasol , ^[29] que a su vez está relacionada con el problema del conjunto de tapas. ^[28]

Límites inferiores para ω

Hay un límite inferior trivial de ⁠ ⁠ ${\displaystyle \omega \geq 2}$ . Dado que cualquier algoritmo para multiplicar dos n × n -matrices tiene que procesar las 2 n ² entradas, hay un límite inferior asintótico trivial de Ω( n ² ) operaciones para cualquier algoritmo de multiplicación de matrices. Por lo tanto ⁠ ⁠ ${\displaystyle 2\leq \omega <2.37188}$ . Se desconoce si ⁠ ⁠ ${\displaystyle \omega >2}$ . El límite inferior más conocido para la complejidad de la multiplicación de matrices es Ω( n ² log( n )) , para circuitos aritméticos de coeficientes acotados sobre los números reales o complejos, y se debe a Ran Raz . ^[30]

El exponente ω se define como un punto límite , en el sentido de que es el ínfimo del exponente en todos los algoritmos de multiplicación de matrices. Se sabe que este punto límite no se alcanza. En otras palabras, bajo el modelo de cálculo típicamente estudiado, no existe ningún algoritmo de multiplicación de matrices que utilice precisamente O( n ^ω ) operaciones; debe haber un factor adicional de n ^o(1) . ^[14]

Multiplicación de matrices rectangulares

También se aplican técnicas similares a la multiplicación de matrices rectangulares. El objeto central de estudio es , que es el más pequeño tal que se puede multiplicar una matriz de tamaño con una matriz de tamaño con operaciones aritméticas. Un resultado en complejidad algebraica establece que multiplicar matrices de tamaño y requiere el mismo número de operaciones aritméticas que multiplicar matrices de tamaño y y de tamaño y , por lo que esto abarca la complejidad de la multiplicación de matrices rectangulares. ^[31] Esto generaliza el exponente de multiplicación de matrices cuadradas, ya que . ${\displaystyle \omega (k)}$ ${\displaystyle c}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \lceil n^{k}\rceil \times n}$ ${\displaystyle O(n^{c+o(1)})}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \lceil n^{k}\rceil \times n}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \omega (1)=\omega }$

Como la salida del problema de multiplicación de matrices es tamaño , tenemos para todos los valores de . Si uno puede probar para algunos valores de entre 0 y 1 que , entonces tal resultado muestra que para aquellos . El k más grande tal que se conoce como el exponente dual de multiplicación de matrices , generalmente denotado α . α se conoce como el " dual " porque mostrar que es equivalente a mostrar que . Al igual que el exponente de multiplicación de matrices, el exponente dual de multiplicación de matrices aparece a veces en la complejidad de algoritmos en álgebra lineal numérica y optimización. ^[32] ${\displaystyle n^{2}}$ ${\displaystyle \omega (k)\geq 2}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \omega (k)\leq 2}$ ${\displaystyle \omega (k)=2}$ ${\displaystyle k}$ ${\displaystyle \omega (k)=2}$ ${\displaystyle \alpha =1}$ ${\displaystyle \omega =2}$

El primer límite de α fue creado por Coppersmith en 1982, quien demostró que . ^[33] El mejor límite revisado por pares actual de α es , dado por Williams, Xu, Xu y Zhou. ^[2] ${\displaystyle \alpha >0.17227}$ ${\displaystyle \alpha \geq 0.321334}$

Problemas relacionados

Los problemas que tienen la misma complejidad asintótica que la multiplicación de matrices incluyen determinante , inversión de matrices y eliminación gaussiana (ver la siguiente sección). Los problemas con complejidad que se puede expresar en términos de incluyen polinomio característico, valores propios (pero no vectores propios), forma normal de Hermite y forma normal de Smith . ^{[ cita requerida ]} ${\displaystyle \omega }$

Inversión de matrices, determinante y eliminación gaussiana

En su artículo de 1969, donde demostró la complejidad del cálculo de matrices, Strassen demostró también que la inversión de matrices , el determinante y la eliminación gaussiana tienen, hasta una constante multiplicativa, la misma complejidad computacional que la multiplicación de matrices. La prueba no hace ninguna suposición sobre la multiplicación de matrices que se utiliza, excepto que su complejidad es para algunos ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ ${\displaystyle O(n^{\omega })}$ ${\displaystyle \omega \geq 2}$

El punto de partida de la demostración de Strassen es la multiplicación de matrices por bloques . En concreto, una matriz de dimensión par 2 n × 2 n puede dividirse en cuatro bloques n × n

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

Bajo esta forma, su inversa es

${\displaystyle {\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}},}$

siempre que A y sean invertibles. ${\displaystyle {D}-{CA}^{-1}{B}}$

Así, la inversa de una matriz 2 n × 2 n se puede calcular con dos inversiones, seis multiplicaciones y cuatro adiciones o inversas aditivas de matrices n × n . De ello se deduce que, denotando respectivamente por I ( n ) , M ( n ) y A ( n ) = n ² el número de operaciones necesarias para invertir, multiplicar y sumar matrices n × n , se tiene

${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$

Si se puede aplicar esta fórmula recursivamente: ${\displaystyle n=2^{k},}$

${\displaystyle {\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}}}$

Si uno finalmente consigue ${\displaystyle M(n)\leq cn^{\omega },}$ ${\displaystyle \alpha =2^{\omega }\geq 4,}$

${\displaystyle {\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(2^{k})^{\omega }\end{aligned}}}$

para alguna constante d .

Para matrices cuya dimensión no es una potencia de dos, se alcanza la misma complejidad aumentando la dimensión de la matriz a una potencia de dos, rellenando la matriz con filas y columnas cuyas entradas son 1 en la diagonal y 0 en el resto.

Esto demuestra la complejidad supuesta para matrices tales que todas las submatrices que deben invertirse son, de hecho, invertibles. Esta complejidad queda así demostrada para casi todas las matrices, ya que una matriz con elementos elegidos aleatoriamente es invertible con probabilidad uno.

El mismo argumento se aplica a la descomposición LU , ya que, si la matriz A es invertible, la igualdad

${\displaystyle {\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}}}$

define una descomposición LU en bloque que puede aplicarse recursivamente a y para obtener eventualmente una verdadera descomposición LU de la matriz original. ${\displaystyle A}$ ${\displaystyle D-CA^{-1}B,}$

El argumento se aplica también al determinante, ya que resulta de la descomposición LU en bloques que

${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$

Minimizar el número de multiplicaciones

Relacionado con el problema de minimizar el número de operaciones aritméticas está el de minimizar el número de multiplicaciones, que es típicamente una operación más costosa que la suma. Un algoritmo para la multiplicación de matrices necesariamente debe usar solo operaciones de multiplicación, pero estos algoritmos son poco prácticos. Mejorando las multiplicaciones ingenuas para la multiplicación de libros escolares, las matrices en se pueden hacer con 47 multiplicaciones, ^[34] la multiplicación de matrices sobre un anillo conmutativo se puede hacer en 21 multiplicaciones ^{[35] [36]} (23 si no es conmutativa ^[37] ). El límite inferior de las multiplicaciones necesarias es 2 mn +2 n − m −2 (multiplicación de matrices n × m con matrices m × n utilizando el método de sustitución, m ⩾ n ⩾3), lo que significa que el caso n = 3 requiere al menos 19 multiplicaciones y n = 4 al menos 34. ^[38] Para n = 2, 7 multiplicaciones óptimas, 15 adiciones son mínimas, en comparación con solo 4 adiciones para 8 multiplicaciones. ^{[39] [40]} ${\displaystyle O(n^{\omega })}$ ${\displaystyle O(n^{\omega })}$ ${\displaystyle n^{3}}$ ${\displaystyle 4\times 4}$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle 3\times 3}$

Véase también

• Complejidad computacional de operaciones matemáticas
• Algoritmo CYK, §Algoritmo de Valiant
• Algoritmo de Freivalds , un algoritmo de Monte Carlo simple que , dadas las matrices A , B y C , verifica en tiempo Θ( n ² ) si AB = C.
• Multiplicación de cadenas de matrices
• Multiplicación de matrices , para definiciones abstractas
• Algoritmo de multiplicación de matrices , para detalles de implementación práctica
• Multiplicación de matrices dispersas por vectores

Referencias

1. Volker Strassen (agosto de 1969). "La eliminación gaussiana no es óptima". Matemática numérica . 13 (4): 354–356. doi :10.1007/BF02165411. S2CID  121656251.
2. Vassilevska Williams, Virginia; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei. Nuevos límites para la multiplicación de matrices: de alfa a omega . Actas del Simposio anual ACM-SIAM de 2024 sobre algoritmos discretos (SODA). págs. 3792–3835. arXiv : 2307.07970 . doi :10.1137/1.9781611977912.134.
3. Nadis, Steve (7 de marzo de 2024). «Un nuevo avance acerca la multiplicación de matrices al ideal» . Consultado el 9 de marzo de 2024 .
4. Iliopoulos, Costas S. (1989). "Límites de complejidad en el peor de los casos en algoritmos para calcular la estructura canónica de grupos abelianos finitos y las formas normales de Hermite y Smith de una matriz entera" (PDF) . SIAM Journal on Computing . 18 (4): 658–669. CiteSeerX 10.1.1.531.9309 . doi :10.1137/0218045. MR  1004789. Archivado desde el original (PDF) el 2014-03-05 . Consultado el 2015-01-16 . El algoritmo Coppersmith–Winograd no es práctico, debido a la constante oculta muy grande en el límite superior del número de multiplicaciones requeridas. 
5. Robinson, Sara (noviembre de 2005). "Hacia un algoritmo óptimo para la multiplicación de matrices" (PDF) . SIAM News . 38 (9). Incluso si alguien logra demostrar una de las conjeturas (demostrando así que ω = 2) , es poco probable que el enfoque del producto en corona sea aplicable a los grandes problemas de matrices que surgen en la práctica. [...] las matrices de entrada deben ser astronómicamente grandes para que la diferencia en el tiempo sea evidente.
6. Miller, Webb (1975). "Complejidad computacional y estabilidad numérica". SIAM News . 4 (2): 97–107. CiteSeerX 10.1.1.148.9947 . doi :10.1137/0204009. 
7. Skiena, Steven (2012). "Ordenamiento y búsqueda". Manual de diseño de algoritmos . Springer. págs. 45-46, 401-403. doi :10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
8. Press, William H.; Flannery, Brian P.; Teukolsky, Saul A .; Vetterling, William T. (2007). Recetas numéricas: el arte de la computación científica (3.ª ed.). Cambridge University Press . p. 108. ISBN 978-0-521-88068-8.
9. Ballard, Grey; Benson, Austin R.; Druinsky, Alex; Lipshitz, Benjamin; Schwartz, Oded (2016). "Mejora de la estabilidad numérica de la multiplicación rápida de matrices". Revista SIAM sobre análisis de matrices y aplicaciones . 37 (4): 1382–1418. arXiv : 1507.00687 . doi :10.1137/15M1032168. S2CID  2853388.
10. Victor Yakovlevich Pan (octubre de 1978). "El algoritmo de Strassen no es óptimo: técnica trilineal de agregación, unión y cancelación para construir algoritmos rápidos para operaciones matriciales". Proc. 19th FOCS . págs. 166–176. doi :10.1109/SFCS.1978.34. S2CID  14348408.
11. Darío Andrea Bini; Milvio Capovani; Francisco Romani; Grazia Lotti (junio de 1979). " O ( n 2.7799 ) {\displaystyle O(n^{2.7799})} complejidad para n × n {\displaystyle n\times n} multiplicación de matrices aproximada". Cartas de procesamiento de información . 8 (5): 234–235. doi :10.1016/0020-0190(79)90113-3.
12. A. Schönhage (1981). "Multiplicación de matrices parciales y totales". Revista SIAM de Informática . 10 (3): 434–455. doi :10.1137/0210032.
13. Francesco Romani (1982). "Algunas propiedades de sumas disjuntas de tensores relacionadas con la multiplicación de matrices". Revista SIAM de Computación . 11 (2): 263–267. doi :10.1137/0211020.
14. D. Coppersmith; S. Winograd (1981). "Sobre la complejidad asintótica de la multiplicación de matrices". Proc. 22.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS) . págs. 82–90. doi :10.1109/SFCS.1981.27. S2CID  206558664.
15. Volker Strassen (octubre de 1986). "El espectro asintótico de los tensores y el exponente de la multiplicación de matrices". Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS) . págs. 49-54. doi :10.1109/SFCS.1986.52. ISBN 0-8186-0740-8.S2CID 15077423  .
16. D. Coppersmith; S. Winograd (marzo de 1990). "Multiplicación de matrices mediante progresiones aritméticas". Journal of Symbolic Computation . 9 (3): 251–280. doi : 10.1016/S0747-7171(08)80013-2 .
17. Stothers, Andrew James (2010). Sobre la complejidad de la multiplicación de matrices (tesis doctoral). Universidad de Edimburgo.
18. Virginia Vassilevska Williams (2012). "Multiplicación de matrices más rápida que Coppersmith-Winograd". En Howard J. Karloff; Toniann Pitassi (eds.). Proc. 44.° Simposio sobre teoría de la computación (STOC) . ACM. págs. 887–898. doi :10.1145/2213977.2214056. ISBN . 978-1-4503-1245-5. Número de identificación del sujeto  14350287.
19. Williams, Virginia Vassilevska . Multiplicación de matrices en tiempo O ( n 2.373 ) {\displaystyle O(n^{2.373})} (PDF) (Informe técnico). Universidad de Stanford.
20. Le Gall, François (2014). "Teoría de la complejidad algebraica y multiplicación de matrices". En Katsusuke Nabeshima (ed.). Actas del 39.° Simposio Internacional sobre Computación Simbólica y Algebraica - ISSAC '14 . págs. 296–303. arXiv : 1401.7714 . Bibcode :2014arXiv1401.7714L. doi :10.1145/2608628.2627493. ISBN: 978-1-4503-2501-1. Número de identificación del sujeto  2597483.
21. Alman, Josh; Williams, Virginia Vassilevska (2020). "Un método láser refinado y una multiplicación de matrices más rápida". 32.º Simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2021). arXiv : 2010.05846 .
22. Hartnett, Kevin (23 de marzo de 2021). "La multiplicación de matrices se acerca cada vez más a la meta mítica". Revista Quanta . Consultado el 1 de abril de 2021 .
23. Duan, Ran; Wu, Hongxun; Zhou, Renfei (2022). "Multiplicación de matrices más rápida mediante hash asimétrico". arXiv : 2210.10173 [cs.DS].
24. Coppersmith, Don; Winograd, Shmuel (1990). "Multiplicación de matrices mediante progresiones aritméticas" (PDF) . Journal of Symbolic Computation . 9 (3): 251. doi : 10.1016/S0747-7171(08)80013-2 .
25. Ambainis, Andris; Filmus, Yuval; Le Gall, François (14 de junio de 2015). "Multiplicación rápida de matrices". Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación . STOC '15. Portland, Oregón, EE. UU.: Association for Computing Machinery. págs. 585–593. arXiv : 1411.5414 . doi :10.1145/2746539.2746554. ISBN 978-1-4503-3536-2.S2CID8332797  .​
26. Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). "Algoritmos de teoría de grupos para la multiplicación de matrices". 46.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'05). pág. 379. doi :10.1109/SFCS.2005.39. ISBN 0-7695-2468-0. Número de identificación del sujeto  41278294.
27. Cohn, Henry; Umans, Chris (2003). "Un enfoque de teoría de grupos para la multiplicación rápida de matrices". Actas del 44.º Simposio anual IEEE sobre fundamentos de la informática, 11-14 de octubre de 2003. IEEE Computer Society. págs. 438-449. arXiv : math.GR/0307321 . doi :10.1109/SFCS.2003.1238217. ISBN . 0-7695-2040-5. Número de identificación del sujeto  5890100.
28. Blasiak, J.; Cohn, H.; Church, T.; Grochow, J.; Naslund, E.; Sawin, W.; Umans, C. (2017). "Sobre los conjuntos de tapas y el enfoque de teoría de grupos para la multiplicación de matrices". Análisis discreto. pág. 1245. doi :10.19086/da.1245. S2CID  9687868.
29. Alon, N. ; Shpilka, A.; Umans, C. (abril de 2011). "Sobre los girasoles y la multiplicación de matrices". Coloquio electrónico sobre complejidad computacional . TR11-067.
30. Raz, Ran (2002). "Sobre la complejidad del producto matricial". Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación . págs. 144-151. doi :10.1145/509907.509932. ISBN 1581134959.S2CID 9582328  .
31. Gall, Francois Le; Urrutia, Florent (1 de enero de 2018). Multiplicación de matrices rectangulares mejorada usando potencias del tensor de Coppersmith-Winograd. Actas. Sociedad de Matemáticas Industriales y Aplicadas. págs. 1029–1046. arXiv : 1708.05622 . doi :10.1137/1.9781611975031.67. ISBN . 978-1-61197-503-1. S2CID  33396059 . Consultado el 23 de mayo de 2021 . {{cite book}}: |work=ignorado ( ayuda )
32. Cohen, Michael B.; Lee, Yin Tat; Song, Zhao (5 de enero de 2021). "Resolución de programas lineales en el tiempo de multiplicación de matrices actual". Revista de la ACM . 68 (1): 3:1–3:39. arXiv : 1810.07896 . doi :10.1145/3424305. ISSN  0004-5411. S2CID  231955576.
33. Coppersmith, D. (1 de agosto de 1982). "Multiplicación rápida de matrices rectangulares" . Revista SIAM de informática . 11 (3): 467–471. doi :10.1137/0211037. ISSN  0097-5397.
34. Ver Datos ampliados Fig. 1: Algoritmo para multiplicar matrices de 4 × 4 en aritmética modular ( Z 2 {\displaystyle \mathbb {Z} _{2}} )) con 47 multiplicaciones en Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; r Ruiz, FJ; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). "Descubrimiento de algoritmos de multiplicación de matrices más rápidos con aprendizaje de refuerzo". Nature . 610 (7930): 47–53. Código Bibliográfico :2022Natur.610...47F. doi :10.1038/s41586-022-05172-4. PMC 9534758. PMID  36198780 . 
35. Rosowski, Andreas (27 de julio de 2020). "Algoritmo matricial conmutativo rápido". arXiv : 1904.07683 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
36. Makarov, OM (1986). "Un algoritmo para multiplicar matrices de 3 × 3". Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki . 26 (2): 293–294 . Consultado el 5 de octubre de 2022 .

    También en Makarov, OM (1986). "Un algoritmo para multiplicar matrices 3×3". Matemáticas computacionales y física matemática de la URSS . 26 : 179–180. doi :10.1016/0041-5553(86)90203-X.

37. Laderman, Julian D. (1976). "Un algoritmo no conmutativo para multiplicar matrices 3×3 usando 23 multiplicaciones". Boletín de la Sociedad Americana de Matemáticas . 82 (1): 126–128. doi : 10.1090/S0002-9904-1976-13988-2 . ISSN  0002-9904.
38. Bläser, Markus (febrero de 2003). "Sobre la complejidad de la multiplicación de matrices de pequeños formatos". Journal of Complexity . 19 (1): 43–60. doi : 10.1016/S0885-064X(02)00007-9 .
39. Winograd, S. (1971-10-01). "Sobre la multiplicación de matrices 2 × 2". Álgebra lineal y sus aplicaciones . 4 (4): 381–388. doi : 10.1016/0024-3795(71)90009-7 . ISSN  0024-3795.
40. L., Probert, R. (1973). Sobre la complejidad de la multiplicación de matrices. Universidad de Waterloo. OCLC  1124200063.{{cite book}}: CS1 maint: multiple names: authors list (link)

Enlaces externos

• Otro catálogo de algoritmos rápidos de multiplicación de matrices
• Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Ruiz, FJR; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). "Descubrimiento de algoritmos de multiplicación de matrices más rápidos con aprendizaje de refuerzo". Nature . 610 (7930): 47–53. Bibcode :2022Natur.610...47F. doi :10.1038/s41586-022-05172-4. PMC  9534758 . PMID  36198780.