¿Cuál es el algoritmo más rápido para la multiplicación de matrices?
En informática teórica , la complejidad computacional de la multiplicación de matrices dicta la rapidez con la que se puede realizar la operación de multiplicación de matrices . 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 la cantidad de tiempo correcta que debería tomar es de gran relevancia práctica.
La aplicación directa de la definición matemática de multiplicación de matrices proporciona un algoritmo que requiere n 3 operaciones de campo para multiplicar dos n × n matrices sobre ese campo ( Θ ( n 3 ) en notación O grande ). Sorprendentemente, existen algoritmos que proporcionan mejores tiempos de ejecución que este sencillo "algoritmo de libros de texto". El primero en ser descubierto 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] Aún se desconoce el número óptimo de operaciones de campo necesarias para multiplicar dos matrices cuadradas n × n hasta factores constantes . Ésta es una importante cuestión abierta en la informática teórica .
A diciembre de 2020 [actualizar], el algoritmo de multiplicación de matrices con la mejor complejidad asintótica se ejecuta en tiempo O ( n 2.3728596 ) , proporcionado por Josh Alman y Virginia Vassilevska Williams . [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 Big O es tan grande que solo valen la pena para matrices que son demasiado grandes para manejar en las computadoras actuales. [4] [5]
Algoritmos simples
Si A , B son n × n matrices sobre un campo, entonces su producto AB también es una matriz n × n sobre ese campo, definido por entrada como
Algoritmo del libro escolar
El método más simple para calcular el producto de dos n × n matrices A y B es calcular las expresiones aritméticas que provienen de la definición de multiplicación de matrices. En pseudocódigo:
de entrada A y B , tanto n por n matrices inicializan C para ser un n por n matriz de todo 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 y adiciones para calcular el producto de dos matrices cuadradas n × n . Su complejidad computacional es por tanto, 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 coma flotante , pero no necesariamente de los enteros).
Algoritmo de Strassen
El algoritmo de Strassen mejora la multiplicación de matrices ingenua a través de un enfoque de divide y vencerás . La observación clave es que la multiplicación de dos matrices 2 × 2 se puede hacer con solo 7 multiplicaciones, en lugar de las 8 habituales (a expensas de varias operaciones adicionales de suma y resta). Esto significa que, al tratar las matrices n × n de entrada como matrices de bloque 2 × 2 , la tarea de multiplicar n × n matrices se puede reducir a 7 subproblemas de multiplicar n / 2 × n / 2 matrices. Aplicar esto de forma recursiva da un algoritmo que necesita operaciones de campo.
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 los casos en los que n > 100 aproximadamente [7] y aparece en varias bibliotecas, como BLAS . [8] 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
Año | Atado a omega | Autores |
---|---|---|
1969 | 2.8074 | Strassen [1] |
1978 | 2.796 | Pan [9] |
1979 | 2.780 | Bini, Capovani, Romani [10] |
1981 | 2.522 | Schönhage [11] |
1981 | 2.517 | Romaní [12] |
1981 | 2.496 | Calderero , Winograd [13] |
1986 | 2.479 | Strassen [14] |
1990 | 2.3755 | Calderero , Winograd [15] |
2010 | 2.3737 | Stothers [16] |
2013 | 2.3729 | Williams [17] [18] |
2014 | 2.3728639 | Le Gall [19] |
2020 | 2.3728596 | Alman, Williams [2] |
El exponente de la multiplicación de matrices , generalmente denotado ω , es el número real más pequeño para el cual cualquier La matriz sobre un campo se puede multiplicar usando operaciones de campo. Esta notación se usa comúnmente en la investigación de algoritmos , por lo que los algoritmos que usan la multiplicación de matrices como una subrutina tienen límites significativos en el tiempo de ejecución independientemente del valor real de ω .
Utilizando un límite inferior ingenuo y una multiplicación de matrices de libros escolares para el límite superior, se puede concluir directamente que 2 ≤ ω ≤ 3 . Si ω = 2 es una cuestión abierta importante en la informática teórica , y existe una línea de investigación que desarrolla algoritmos de multiplicación de matrices para mejorar los límites de ω .
El mejor límite actual en ω es ω <2.3728596 , por Josh Alman y Virginia Vassilevska Williams . [2] Este algoritmo, como todos los otros algoritmos recientes en esta línea de investigación, utiliza 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. [20] La idea conceptual de estos algoritmos es similar al algoritmo de Strassen: se ideó una forma de multiplicar dos k × k -matrices con menos de k 3 multiplicaciones, y esta técnica se aplica de forma recursiva. El método láser tiene limitaciones de potencia y no se puede utilizar para mostrar que ω <2,3725 . [21]
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 colocan métodos como los algoritmos de Strassen y Coppersmith-Winograd en un contexto de teoría de grupos completamente diferente , utilizando triples de subconjuntos de grupos finitos que satisfacen una propiedad de disjunción llamada propiedad de producto triple ( TPP) . También dan conjeturas que, de ser ciertas, implicarían que existen 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 el caso. [5] Una de esas conjeturas es que las familias de productos de coronas de grupos abelianos con grupos simétricos realizan familias de subconjuntos triples con una versión simultánea del TPP. [22] [23] Varias de sus conjeturas han sido refutadas desde entonces por Blasiak, Cohn, Church, Grochow, Naslund, Sawin y Umans usando el método Slice Rank. [24] Además, Alon, Shpilka y Chris Umans han demostrado recientemente que algunas de estas conjeturas que implican una multiplicación de matrices rápida son incompatibles con otra conjetura plausible, la conjetura del girasol . [25]
Límites inferiores para ω
Hay un límite inferior trivial de . Dado que cualquier algoritmo para multiplicar dos matrices n × n tiene que procesar las 2 n 2 entradas, existe un límite inferior asintótico trivial de operaciones Ω ( n 2 ) para cualquier algoritmo de multiplicación de matrices. Por lo tanto. Se desconoce si. El límite inferior más conocido para la complejidad de la multiplicación de matrices es Ω ( n 2 log ( n )) , para circuitos aritméticos de coeficientes acotados sobre números reales o complejos, y se debe a Ran Raz . [26]
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 mas pequeño tal que se pueda multiplicar una matriz de tamaño con una matriz de tamaño con operaciones aritmeticas. 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. [27] Esto generaliza el exponente de multiplicación de matrices cuadradas, ya que.
Es de interés probar que, para valores de k entre 0 y 1, que. Dado que la salida del problema de multiplicación de matrices es el tamaño, siempre, por lo que estos resultados muestran que exactamente. El mayor k tal quese conoce como exponente de multiplicación de matriz dual , generalmente denotado α . α se denomina " dual " porque muestra que es equivalente a mostrar que . Al igual que el exponente de multiplicación de matrices, el exponente de multiplicación de matrices dual a veces aparece en la complejidad de los algoritmos en álgebra lineal numérica y optimización. [28]
El primer límite en α es de Coppersmith en 1982, quien demostró que. [29] El mejor límite actual en α es, a cargo de Le Gall y Urrutia. [30] Este documento también contiene límites sobre.
Complejidades relacionadas
Los problemas que tienen la misma complejidad asintótica que la multiplicación de matrices incluyen determinante , inversión de matriz , eliminación gaussiana (ver la siguiente sección). Problemas de complejidad que se pueden expresar en términos deincluyen el polinomio característico, los valores propios (pero no los vectores propios), la forma normal de Hermite y la forma normal de Smith . [ cita requerida ]
Inversión de matrices, determinante y eliminación gaussiana
En su artículo de 1969, donde demostró la complejidad Para el cálculo de matrices, Strassen demostró también que la inversión de matrices , el determinante y la eliminación de Gauss tienen, hasta una constante multiplicativa, la misma complejidad computacional que la multiplicación de matrices. La demostración no hace suposiciones sobre la multiplicación de matrices que se usa, excepto que su complejidad es para algunos
El punto de partida de la demostración de Strassen es el uso de la multiplicación de matrices de bloques . Específicamente, una matriz de dimensión par 2 n × 2 n puede dividirse en cuatro n × n bloques
Bajo esta forma, su inverso es
siempre que A y son invertibles.
Por lo tanto, la inversa de una matriz de 2 n × 2 n se puede calcular con dos inversiones, seis multiplicaciones y cuatro adiciones o inversas aditivas de n × n matrices. De ello se deduce que, denotando respectivamente por I ( n ) , M ( n ) y A ( n ) = n 2 el número de operaciones necesarias para invertir, multiplicar y sumar n × n matrices, se tiene
Si se puede aplicar esta fórmula de forma recursiva:
Si y uno llega eventualmente
por 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 afirmada para las matrices, de modo que todas las submatrices que deben invertirse son, de hecho, invertibles. Esta complejidad queda así probada para casi todas las matrices, ya que una matriz con entradas elegidas al azar 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
define una descomposición de LU de bloque que se puede aplicar de forma recursiva a y para obtener eventualmente una verdadera descomposición LU de la matriz original.
El argumento se aplica también para el determinante, ya que resulta de la descomposición LU del bloque que
Ver también
- Complejidad computacional de operaciones matemáticas
- Algoritmo CYK, algoritmo de §Valiant
- Algoritmo Freivalds' , un simple algoritmo de Monte Carlo que, dada matrices A , B y C , verifica en Θ ( n 2 ) tiempo si AB = C .
- Multiplicación de cadenas de matrices
- Multiplicación de matrices , para definiciones abstractas
- Algoritmo de multiplicación de matrices , para detalles prácticos de implementación
- Multiplicación dispersa matriz-vector
Referencias
- ↑ a b Volker Strassen (agosto de 1969). "La eliminación gaussiana no es óptima" . Numerische Mathematik . 13 (4): 354–356. doi : 10.1007 / BF02165411 . S2CID 121656251 .
- ^ a b c 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
- ^ Hartnett, Kevin. "La multiplicación de la matriz se acerca más a la meta mítica" . Revista Quanta . Consultado el 1 de abril de 2021 .
- ^ Iliopoulos, Costas S. (1989), "Límites de complejidad del peor caso 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) en 2014-03-05 , obtenido 2015-01-16 ,
El algoritmo Coppersmith – Winograd no es práctico, debido a la gran constante oculta en el límite superior del número de multiplicaciones necesarias.
- ^ a b Robinson, Sara (noviembre de 2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF) , SIAM News , 38 (9),
Incluso si alguien logra probar una de las conjeturas, demostrando así que ω = 2 - el producto de la corona Es poco probable que este enfoque 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 de tiempo sea evidente.
- ^ 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
- ^ Skiena, Steven (2008). "Ordenar y buscar". El Manual de diseño de algoritmos . Saltador. págs. 45 –46, 401–403. doi : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
- ^ Prensa, William H .; Flannery, Brian P .; Teukolsky, Saul A .; Vetterling, William T. (2007). Recetas numéricas: el arte de la informática científica (3ª ed.). Prensa de la Universidad de Cambridge . pag. 108 . ISBN 978-0-521-88068-8.
- ^ 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 la construcción de algoritmos rápidos para operaciones matriciales". Proc. 19o FOCS . págs. 166-176. doi : 10.1109 / SFCS.1978.34 . S2CID 14348408 .
- ^ Dario Andrea Bini; Milvio Capovani; Francesco Romani; Grazia Lotti (junio de 1979). " O ( norte 2.7799 ) {\ Displaystyle O (n ^ {2.7799})} complejidad para norte × norte {\ Displaystyle n \ times n} multiplicación aproximada de matrices " . Information Processing Letters . 8 (5): 234-235. doi : 10.1016 / 0020-0190 (79) 90113-3 .
- ^ A. Schönhage (1981). "Multiplicación de matrices total y parcial". Revista SIAM de Computación . 10 (3): 434–455. doi : 10.1137 / 0210032 .
- ^ 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 .
- ^ D. Calderero; S. Winograd (1981). "Sobre la complejidad asintótica de la multiplicación de matrices". Proc. 22º Simposio Anual sobre Fundamentos de la Informática (FOCS) . págs. 82–90. doi : 10.1109 / SFCS.1981.27 . S2CID 206558664 .
- ^ Volker Strassen (octubre de 1986). "El espectro asintótico de tensores y el exponente de la multiplicación de matrices". Proc. 27th Ann. Symp. sobre la Fundación de Ciencias de la Computación (FOCS) . págs. 49–54. doi : 10.1109 / SFCS.1986.52 . S2CID 15077423 .
- ^ D. Calderero; S. Winograd (marzo de 1990). "Multiplicación de matrices mediante progresiones aritméticas" . Revista de Computación Simbólica . 9 (3): 251–280. doi : 10.1016 / S0747-7171 (08) 80013-2 .
- ^ Stothers, Andrew James (2010). Sobre la complejidad de la multiplicación de matrices (tesis doctoral). Universidad de Edimburgo.
- ^ Virginia Vassilevska Williams (2012). "Multiplicar matrices más rápido que calderero-Winograd". En Howard J. Karloff; Toniann Pitassi (eds.). Proc. 44º Simposio de Teoría de la Computación (STOC) . ACM. págs. 887–898. doi : 10.1145 / 2213977.2214056 .
- ^ Williams, Virginia Vassilevska . Multiplicar matrices en O ( norte 2.373 ) {\ Displaystyle O (n ^ {2.373})} time (PDF) (Informe técnico). Universidad Stanford.
- ^ Le Gall, François (2014), "Poderes de tensores y multiplicación rápida de matrices", en Katsusuke Nabeshima (ed.), Actas del 39º Simposio Internacional de Computación Simbólica y Algebraica (ISSAC) , págs. 296-303, arXiv : 1401.7714 , Código bibliográfico : 2014arXiv1401.7714L , ISBN 978-1-4503-2501-1
- ^ Calderero, 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
- ^ Ambainis, Andris; Filmus, Yuval; Le Gall, François (14 de junio de 2015). "Multiplicación rápida de matrices: limitaciones del método Calderero-Winograd" . Actas del cuadragésimo séptimo simposio anual de ACM sobre teoría de la computación . STOC '15. Portland, Oregón, EE. UU.: Asociación de Maquinaria de Computación: 585–593. doi : 10.1145 / 2746539.2746554 . ISBN 978-1-4503-3536-2.
- ^ Cohn, H .; Kleinberg, R .; Szegedy, B .; Umans, C. (2005). "Algoritmos teóricos de grupos para la multiplicación de matrices". 46º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS'05) . pag. 379. doi : 10.1109 / SFCS.2005.39 . ISBN 0-7695-2468-0. S2CID 41278294 .
- ^ Henry Cohn, Chris Umans. Un enfoque teórico de grupos para la multiplicación de matrices rápida. arXiv : matemáticas.GR / 0307321 . Actas del 44º Simposio anual del IEEE sobre los fundamentos de la informática , del 11 al 14 de octubre de 2003, Cambridge, MA, IEEE Computer Society, págs. 438–449.
- ^ Blasiak, J .; Cohn, H .; Church, T .; Grochow, J .; Naslund, E .; Sawin, W .; Umans, C. (2017). "Sobre los conjuntos de límites y el enfoque teórico de grupos para la multiplicación de matrices". Análisis discreto . doi : 10.19086 / da.1245 . S2CID 9687868 .
- ^ Alon , Shpilka, Umans, Sobre girasoles y multiplicación de matrices
- ^ Raz, Ran (2002). "Sobre la complejidad del producto matricial". Actas del Trigésimo Cuarto Simposio Anual de ACM sobre Teoría de la Computación : 144. doi : 10.1145 / 509907.509932 . ISBN 1581134959. S2CID 9582328 .
- ^ Gall, Francois Le; Urrutia, Florent (2018-01-01), "Multiplicación de matrices rectangulares mejorada utilizando los poderes del tensor de calderero-Winograd" , Actas del Simposio anual ACM-SIAM de 2018 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas , págs. 1029–1046, arXiv : 1708.05622 , doi : 10.1137 / 1.9781611975031.67 , consultado el 23 de mayo de 2021
- ^ 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 .
- ^ Calderero, D. (1 de agosto de 1982). "Multiplicación rápida de matrices rectangulares" . Revista SIAM de Computación . 11 (3): 467–471. doi : 10.1137 / 0211037 . ISSN 0097-5397 .
- ^ Le Gall, Francois; Urrutia, Florent (2018-01-01), "Multiplicación de matrices rectangulares mejorada utilizando los poderes del tensor de calderero-Winograd" , Actas del Simposio anual ACM-SIAM de 2018 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas , págs. 1029–1046, arXiv : 1708.05622 , doi : 10.1137 / 1.9781611975031.67 , consultado el 23 de mayo de 2021