En matemáticas , particularmente en álgebra lineal , la multiplicación de matrices es una operación binaria que produce una matriz a partir de dos matrices. Para la multiplicación de matrices, el número de columnas en la primera matriz debe ser igual al número de filas en la segunda matriz. La matriz resultante, conocida como el producto de la matriz , tiene el número de filas de la primera y el número de columnas de la segunda matriz. El producto de las matrices A y B se denota como AB . [1] [2]
La multiplicación de matrices fue descrita por primera vez por el matemático francés Jacques Philippe Marie Binet en 1812, [3] para representar la composición de mapas lineales que están representados por matrices. La multiplicación de matrices es, por tanto, una herramienta básica del álgebra lineal y, como tal, tiene numerosas aplicaciones en muchas áreas de las matemáticas, así como en matemáticas aplicadas , estadística , física , economía e ingeniería . [4] [5] Calcular productos matriciales es una operación central en todas las aplicaciones computacionales del álgebra lineal.
Notación
Este artículo utilizará las siguientes convenciones de notación: las matrices se representan con letras mayúsculas en negrita, por ejemplo, A ; vectores en minúscula y negrita, por ejemplo, a ; y las entradas de vectores y matrices están en cursiva (ya que son números de un campo), por ejemplo, A y a . La notación de índice es a menudo la forma más clara de expresar definiciones y se utiliza como estándar en la literatura. La entrada i, j de la matriz A está indicada por ( A ) ij , A ij o a ij , mientras que una etiqueta numérica (no entradas de matriz) en una colección de matrices solo tiene subíndices, por ejemplo, A 1 , A 2 , etc.
Definición
Si A es una matriz m × n y B es una matriz n × p ,
el producto matricial C = AB (denotado sin puntos o signos de multiplicación) se define como la matriz m × p [6] [7] [8] [9]
tal que
para i = 1, ..., m y j = 1, ..., p .
Es decir, la entrada del producto se obtiene multiplicando término por término las entradas de la i- ésima fila de A y la j- ésima columna de B , y sumando estos n productos. En otras palabras,es el producto escalar de la i ª fila de A y la j ésima columna de B . [1]
Por lo tanto, AB también se puede escribir como
Así, el producto AB se define si y solo si el número de columnas en A es igual al número de filas en B , [2] en este caso n .
En la mayoría de los escenarios, las entradas son números, pero pueden ser cualquier tipo de objetos matemáticos para los que se definen una suma y una multiplicación, que son asociativas y tales que la suma es conmutativa y la multiplicación es distributiva con respecto a la suma. . En particular, las entradas pueden ser matrices en sí mismas (ver matriz de bloques ).
Ilustración
La figura de la derecha ilustra esquemáticamente el producto de dos matrices A y B , mostrando cómo cada intersección en los corresponde matriz del producto a una fila de A y una columna de B .
Los valores en las intersecciones marcadas con círculos son:
Aplicaciones fundamentales
Históricamente, la multiplicación de matrices se ha introducido para facilitar y aclarar los cálculos en álgebra lineal . Esta fuerte relación entre la multiplicación de matrices y el álgebra lineal sigue siendo fundamental en todas las matemáticas, así como en física , ingeniería e informática .
Mapas lineales
Si un espacio vectorial tiene una base finita , cada uno de sus vectores está representado de forma única por una secuencia finita de escalares, denominada vector de coordenadas , cuyos elementos son las coordenadas del vector de la base. Estos vectores de coordenadas forman otro espacio vectorial, que es isomorfo al espacio vectorial original. Un vector de coordenadas se organiza comúnmente como una matriz de columna (también llamado vector de columna ), que es una matriz con una sola columna. Entonces, un vector de columna representa tanto un vector de coordenadas como un vector del espacio vectorial original.
Un mapa lineal A de un espacio vectorial de dimensión n a un espacio vectorial de dimensión m mapea un vector columna
en el vector de columna
Por tanto, el mapa lineal A está definido por la matriz
y mapea el vector de columna al producto de la matriz
Si B es otro mapa lineal del espacio vectorial anterior de dimensión m , en un espacio vectorial de dimensión p , está representado por un matriz Un cálculo sencillo muestra que la matriz del mapa compuesto es el producto de la matriz La formula general ) que define la composición de la función se ejemplifica aquí como un caso específico de asociatividad del producto de matriz (ver § Asociatividad a continuación):
Sistema de ecuaciones lineales
La forma general de un sistema de ecuaciones lineales es
Utilizando la misma notación anterior, dicho sistema es equivalente a la ecuación de matriz única
Producto escalar, forma bilineal y producto interno
El producto escalar de dos vectores de columna es el producto matricial
dónde es el vector de fila obtenido al transponer y la matriz 1 × 1 resultante se identifica con su entrada única.
De manera más general, cualquier forma bilineal sobre un espacio vectorial de dimensión finita puede expresarse como un producto matricial
y cualquier producto interno puede expresarse como
dónde denota la transposición conjugada de (conjugado de la transpuesta, o equivalentemente transpuesta de la conjugada).
Propiedades generales
La multiplicación de matrices comparte algunas propiedades con la multiplicación habitual . Sin embargo, la multiplicación de matrices no está definida si el número de columnas del primer factor difiere del número de filas del segundo factor, y es no conmutativa , [10] incluso cuando el producto permanece definido después de cambiar el orden de los factores. . [11] [12]
No conmutatividad
Una operación es conmutativa si, dados dos elementos A y B tales que el producto está definido, entonces también está definido, y
Si A y B son matrices de tamaños respectivos y , luego se define si , y se define si . Por tanto, si uno de los productos está definido, el otro no está definido en general. Si, los dos productos están definidos, pero tienen diferentes tamaños; por tanto, no pueden ser iguales. Sólo si, es decir, si A y B son matrices cuadradas del mismo tamaño, ambos productos están definidos y tienen el mismo tamaño. Incluso en este caso, uno tiene en general
Por ejemplo
pero
Este ejemplo puede ampliarse para mostrar que, si A es unmatriz con entradas en un campo F , entonces para cada matriz B con entradas en F , si y solo si dónde y yo soy el matriz de identidad . Si, en lugar de un campo, se supone que las entradas pertenecen a un anillo , entonces se debe agregar la condición de que c pertenece al centro del anillo.
Un caso especial donde ocurre conmutatividad es cuando D y E son dos matrices diagonales (cuadradas) (del mismo tamaño); luego DE = ED . [10] Nuevamente, si las matrices están sobre un anillo general en lugar de un campo, las entradas correspondientes en cada una también deben conmutar entre sí para que esto se mantenga.
Distributividad
El producto de la matriz es distributivo con respecto a la adición de la matriz . Es decir, si A , B , C , D son matrices de tamaños respectivos m × n , n × p , n × p y p × q , uno tiene (distributividad izquierda)
y (distributividad derecha)
- [10]
Esto resulta de la distributividad de los coeficientes por
Producto con escalar
Si A es una matriz yc un escalar, entonces las matrices y se obtienen multiplicando todas las entradas de A por c . Si los escalares tienen la propiedad conmutativa , entonces
Si el producto está definido (es decir, el número de columnas de A es igual al número de filas de B ), entonces
- y
Si los escalares tienen la propiedad conmutativa, entonces las cuatro matrices son iguales. Más generalmente, los cuatro son iguales si c pertenece al centro de un anillo que contiene las entradas de las matrices, porque en este caso, c X = X c para todas las matrices X .
Estas propiedades resultan de la bilinealidad del producto de los escalares:
Transponer
Si los escalares tienen la propiedad conmutativa , la transposición de un producto de matrices es el producto, en orden inverso, de las transposiciones de los factores. Es decir
donde T denota la transposición, que es el intercambio de filas y columnas.
Esta identidad no es válida para las entradas no conmutativas, ya que el orden entre las entradas de A y B se invierte cuando se amplía la definición del producto matricial.
Complejo conjugado
Si A y B tienen entradas complejas , entonces
donde * denota el conjugado complejo de entrada de una matriz.
Esto resulta de aplicar a la definición de producto matricial el hecho de que el conjugado de una suma es la suma de los conjugados de los sumandos y el conjugado de un producto es el producto de los conjugados de los factores.
La transposición actúa sobre los índices de las entradas, mientras que la conjugación actúa de forma independiente sobre las propias entradas. Resulta que, si A y B tienen entradas complejas, uno tiene
donde † denota la transpuesta conjugada (conjugada de la transpuesta, o equivalentemente transpuesta de la conjugada).
Asociatividad
Dadas tres matrices A , B y C , los productos ( AB ) C y A ( BC ) se definen si y solo si el número de columnas de A es igual al número de filas de B , y el número de columnas de B es igual al número de filas de C (en particular, si uno de los productos está definido, el otro también está definido). En este caso, uno tiene la propiedad asociativa
Como para cualquier operación asociativa, esto permite omitir los paréntesis y escribir los productos anteriores como
Esto se extiende naturalmente al producto de cualquier número de matrices siempre que las dimensiones coincidan. Es decir, si A 1 , A 2 , ..., A n son matrices tales que el número de columnas de A i es igual al número de filas de A i + 1 para i = 1, ..., n - 1 , entonces el producto
está definido y no depende del orden de las multiplicaciones , si el orden de las matrices se mantiene fijo.
Estas propiedades pueden demostrarse mediante manipulaciones de suma sencillas pero complicadas . Este resultado también se deriva del hecho de que las matrices representan mapas lineales . Por lo tanto, la propiedad asociativa de las matrices es simplemente un caso específico de la propiedad asociativa de la composición de funciones .
La complejidad no es asociativa
Aunque el resultado de una secuencia de productos matriciales no depende del orden de operación (siempre que no se cambie el orden de las matrices), la complejidad computacional puede depender dramáticamente de este orden.
Por ejemplo, si A , B y C son matrices de tamaños respectivos 10 × 30, 30 × 5, 5 × 60 , el cálculo de ( AB ) C necesita 10 × 30 × 5 + 10 × 5 × 60 = 4500 multiplicaciones, mientras que el cálculo de A ( BC ) necesita 30 × 5 × 60 + 10 × 30 × 60 = 27,000 multiplicaciones.
Los algoritmos se han diseñado para elegir el mejor orden de productos, consulte Multiplicación de cadenas de matrices . Cuando aumenta el número n de matrices, se ha demostrado que la elección del mejor orden tiene una complejidad de
Aplicación a la similitud
Cualquier matriz invertible define una transformación de similitud (en matrices cuadradas del mismo tamaño que)
Las transformaciones de similitud mapean producto a productos, es decir
De hecho, uno tiene
Matrices cuadradas
Denotemos el conjunto de n × n matrices cuadradas con entradas en un anillo R , que, en la práctica, suele ser un campo .
En , el producto se define para cada par de matrices. Esto haceun anillo , que tiene la matriz de identidad I como elemento de identidad (la matriz cuyas entradas diagonales son iguales a 1 y todas las demás entradas son 0). Este anillo también es un álgebra R asociativa .
Si n > 1 , muchas matrices no tienen inverso multiplicativo . Por ejemplo, una matriz tal que todas las entradas de una fila (o columna) son 0 no tiene una inversa. Si existe, la inversa de una matriz A se denota A −1 y, por lo tanto, verifica
Una matriz que tiene una inversa es una matriz invertible . De lo contrario, es una matriz singular .
Un producto de matrices es invertible si y solo si cada factor es invertible. En este caso, uno tiene
Cuando R es conmutativo y, en particular, cuando es un campo, el determinante de un producto es el producto de los determinantes. Como los determinantes son escalares y los escalares conmutan, uno tiene
Las otras matrices invariantes no se comportan tan bien con los productos. Sin embargo, si R es conmutativo, AB y BA tienen la misma traza , el mismo polinomio característico y los mismos valores propios con las mismas multiplicidades. Sin embargo, los autovectores son generalmente diferentes si AB ≠ BA .
Poderes de una matriz
Se puede elevar una matriz cuadrada a cualquier potencia entera no negativa multiplicándola por sí misma repetidamente de la misma manera que para los números ordinarios. Es decir,
Calcular la potencia k de una matriz necesita k - 1 veces el tiempo de una sola multiplicación de matrices, si se hace con el algoritmo trivial (multiplicación repetida). Como esto puede llevar mucho tiempo, generalmente se prefiere usar la exponenciación al cuadrado , que requiere menos de 2 log 2 k multiplicaciones de matrices y, por lo tanto, es mucho más eficiente.
Un caso fácil de exponenciación es el de una matriz diagonal . Dado que el producto de las matrices diagonales equivale simplemente a multiplicar los elementos diagonales correspondientes, la k- ésima potencia de una matriz diagonal se obtiene elevando las entradas a la potencia k :
Álgebra abstracta
La definición de producto matricial requiere que las entradas pertenezcan a un semiring y no requiere la multiplicación de elementos del semiring para que sean conmutativas . En muchas aplicaciones, los elementos de la matriz pertenecen a un campo, aunque el semirecolado tropical también es una opción común para problemas de trayectorias más cortas de gráficos . [13] Incluso en el caso de matrices sobre campos, el producto no es conmutativo en general, aunque es asociativo y distributivo sobre la suma de matrices . Las matrices de identidad (que son las matrices cuadradas cuyas entradas son cero fuera de la diagonal principal y 1 en la diagonal principal) son elementos de identidad del producto matricial. De ello se deduce que las n × n matrices sobre un anillo forman un anillo, que no es conmutativo, excepto si n = 1 y el anillo de tierra es conmutativo.
Una matriz cuadrada puede tener un inverso multiplicativo , llamado matriz inversa . En el caso común donde las entradas pertenecen a un anillo conmutativo r , una matriz tiene una inversa si y solo si su determinante tiene una inversa multiplicativa en r . El determinante de un producto de matrices cuadradas es el producto de los determinantes de los factores. Las n × n matrices que tienen una inversa forman un grupo bajo la multiplicación de matrices, cuyos subgrupos se denominan grupos de matrices . Muchos grupos clásicos (incluidos todos los grupos finitos ) son isomorfos a los grupos matriciales; este es el punto de partida de la teoría de las representaciones de grupos .
Complejidad computacional
El algoritmo de multiplicación de matrices que resulta de la definición 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 para el que las operaciones escalares requieren un tiempo constante (en la práctica, este es el caso de los números de coma flotante , pero no de los enteros).
Sorprendentemente, esta complejidad no es óptima, como lo demostró en 1969 Volker Strassen , quien proporcionó un algoritmo, ahora llamado algoritmo de Strassen , con una complejidad de[14] El exponente que aparece en la complejidad de la multiplicación de matrices se ha mejorado varias veces, [15] [16] [17] [18] [19] [20] lo que lleva al algoritmo Coppersmith-Winograd con una complejidad de O ( n 2.3755 ) (1990). [21] [22] Este algoritmo ha sido ligeramente mejorado en 2010 por Stothers a una complejidad de O ( n 2.3737 ) , [23] en 2013 por Virginia Vassilevska Williams a O ( n 2.3729 ) , [22] [24] y en 2014 de François Le Gall para O ( n. 2.3728639 ) . [25] Esto fue refinado aún más en 2020 por Josh Alman y Virginia Vassilevska Williams hasta una complejidad final (actualizada) de O ( n 2.3728596 ) . [26]
El límite inferior más grande para el exponente del algoritmo de multiplicación de matrices generalmente se llama. Es trivialmente cierto que, porque hay que leer el elementos de una matriz para multiplicarla por otra matriz. Por lo tanto. Se desconoce si. El límite inferior más grande conocido para la complejidad de la multiplicación de matrices es Ω ( n 2 log ( n )) , para un tipo restringido de circuitos aritméticos , y se debe a Ran Raz . [27]
Complejidades relacionadas
La importancia de la complejidad computacional de la multiplicación de matrices se basa en el hecho de que muchos problemas algorítmicos pueden resolverse mediante el cálculo de matrices, y la mayoría de los problemas de matrices tienen una complejidad que es igual a la de la multiplicación de matrices (hasta una constante multiplicativa ), o puede expresarse en términos de la complejidad de la multiplicación de matrices o su exponente
Hay varias ventajas de expresar complejidades en términos del exponente de la multiplicación de matrices. En primer lugar, sise mejora, esto mejorará automáticamente el límite superior conocido de complejidad de muchos algoritmos. En segundo lugar, en implementaciones prácticas, nunca se usa el algoritmo de multiplicación de matrices que tiene la mejor complejidad asintótica, porque la constante oculta detrás de la notación O grande es demasiado grande para hacer que el algoritmo sea competitivo para tamaños de matrices que se pueden manipular en una computadora. [ cita requerida ] Expresando así complejidades en términos de proporcionan una complejidad más realista, ya que sigue siendo válido cualquier algoritmo que se elija para el cálculo de matrices.
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
- Cálculo de matrices , para la interacción de la multiplicación de matrices con operaciones de cálculo.
- Otros tipos de productos de matrices:
- Multiplicación de matriz de bloques
- Producto cracoviano , definido como A ∧ B = B T A
- Producto interno de Frobenius , el producto escalar de las matrices consideradas como vectores o, de manera equivalente, la suma de las entradas del producto de Hadamard
- Producto de Hadamard de dos matrices del mismo tamaño, que da como resultado una matriz del mismo tamaño, que es el producto entrada por entrada
- Producto Kronecker o producto tensorial , la generalización a cualquier tamaño del anterior
- Producto Khatri-Rao y producto para dividir la cara
- Producto externo , también llamado producto diádico o producto tensorial de matrices de dos columnas, que es
- Multiplicación escalar
Notas
- ^ a b "Lista completa de símbolos de álgebra" . Bóveda de matemáticas . 2020-03-25 . Consultado el 6 de septiembre de 2020 .
- ^ a b Nykamp, Duane. "Multiplicar matrices y vectores" . Perspectiva matemática . Consultado el 6 de septiembre de 2020 .
- ^ O'Connor, John J .; Robertson, Edmund F. , "Jacques Philippe Marie Binet" , archivo MacTutor de Historia de las Matemáticas , Universidad de St Andrews.
- ^ Lerner, RG ; Trigg, GL (1991). Enciclopedia de Física (2ª ed.). Editores de VHC. ISBN 978-3-527-26954-9.
- ^ Parker, CB (1994). Enciclopedia de Física de McGraw Hill (2ª ed.). ISBN 978-0-07-051400-3.
- ^ Lipschutz, S .; Lipson, M. (2009). Álgebra lineal . Esquemas de Schaum (4ª ed.). McGraw Hill (Estados Unidos). págs. 30–31. ISBN 978-0-07-154352-1.
- ^ Riley, KF; Hobson, diputado; Bence, SJ (2010). Métodos matemáticos para la física y la ingeniería . Prensa de la Universidad de Cambridge. ISBN 978-0-521-86153-3.
- ^ Adams, RA (1995). Cálculo, un curso completo (3ª ed.). Addison Wesley. pag. 627. ISBN 0-201-82823-5.
- ^ Horn, Johnson (2013). Análisis matricial (2ª ed.). Prensa de la Universidad de Cambridge. pag. 6. ISBN 978-0-521-54823-6.
- ^ a b c Weisstein, Eric W. "Multiplicación de matrices" . mathworld.wolfram.com . Consultado el 6 de septiembre de 2020 .
- ^ Lipcshutz, S .; Lipson, M. (2009). "2". Álgebra lineal . Esquemas de Schaum (4ª ed.). McGraw Hill (Estados Unidos). ISBN 978-0-07-154352-1.
- ^ Horn, Johnson (2013). "0". Análisis matricial (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 978-0-521-54823-6.
- ^ Motwani, Rajeev ; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge. pag. 280. ISBN 9780521474658.
- ^ Volker Strassen (agosto de 1969). "La eliminación gaussiana no es óptima" . Numerische Mathematik . 13 (4): 354–356. doi : 10.1007 / BF02165411 . S2CID 121656251 .
- ^ 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 .
- ^ a b Williams, Virginia Vassilevska . Multiplicar matrices en O ( norte 2.373 ) {\ Displaystyle O (n ^ {2.373})} time (PDF) (Informe técnico). Universidad Stanford.
- ^ 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 .
- ^ 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
- ^ 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
- ^ Raz, Ran (enero de 2003). "Sobre la complejidad del producto matricial". Revista SIAM de Computación . 32 (5): 1356-1369. doi : 10.1137 / s0097539702402147 . ISSN 0097-5397 .
Referencias
- Henry Cohn, Robert Kleinberg , Balázs Szegedy y Chris Umans. Algoritmos teóricos de grupos para la multiplicación de matrices. arXiv : matemáticas.GR / 0511460 . Actas del 46º Simposio Anual sobre Fundamentos de las Ciencias de la Computación , 23-25 de octubre de 2005, Pittsburgh, PA, IEEE Computer Society, págs. 379–388.
- 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.
- Calderero, D .; Winograd, S. (1990). "Multiplicación de matrices mediante progresiones aritméticas". J. Computación simbólica . 9 (3): 251–280. doi : 10.1016 / s0747-7171 (08) 80013-2 .
- Horn, Roger A .; Johnson, Charles R. (1991), Temas de análisis matricial , Cambridge University Press , ISBN 978-0-521-46713-1
- Knuth, DE , El arte de la programación informática Volumen 2: Algoritmos seminuméricos . Addison-Wesley Professional; 3a edición (14 de noviembre de 1997). ISBN 978-0-201-89684-8 . págs. 501.
- 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.a ed.), Cambridge University Press , ISBN 978-0-521-88068-8.
- Ran Raz . Sobre la complejidad del producto matricial. En Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la computación. Prensa ACM, 2002. doi : 10.1145 / 509907.509932 .
- Robinson, Sara, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38 (9), noviembre de 2005. PDF
- Strassen, Volker, Gaussian Elimination is not Optimal , Numer. Matemáticas. 13, pág. 354-356, 1969.
- Styan, George PH (1973), "Productos de Hadamard y análisis estadístico multivariante" (PDF) , Álgebra lineal y sus aplicaciones , 6 : 217-240, doi : 10.1016 / 0024-3795 (73) 90023-2
- Williams, Virginia Vassilevska (19 de mayo de 2012). "Multiplicar matrices más rápido que calderero-winograd" . Actas del 44º simposio de Teoría de la Computación - STOC '12 . ACM. págs. 887–898. CiteSeerX 10.1.1.297.2680 . doi : 10.1145 / 2213977.2214056 . ISBN 9781450312455. S2CID 14350287 .