Algoritmo de multiplicación de matrices

Debido a que la multiplicación de matrices es una operación tan central en muchos algoritmos numéricos , se ha invertido mucho trabajo en hacer que los algoritmos de multiplicación de matrices sean eficientes. Las aplicaciones de la multiplicación de matrices en problemas computacionales se encuentran en muchos campos, incluida la computación científica y el reconocimiento de patrones y en problemas aparentemente no relacionados, como contar los caminos a través de un gráfico . ^[1] Se han diseñado muchos algoritmos diferentes para multiplicar matrices en diferentes tipos de hardware, incluidos sistemas paralelos y distribuidos , donde el trabajo computacional se distribuye en múltiples procesadores (quizás en una red).

La aplicación directa de la definición matemática de multiplicación de matrices da como resultado un algoritmo que tarda un tiempo del orden de $n 3$ operaciones de campo en multiplicar dos matrices $n \times n$ sobre ese campo ( $Θ(n 3)$ en notación O grande ). Se conocen mejores límites asintóticos del tiempo necesario para multiplicar matrices desde el algoritmo de Strassen en la década de 1960, pero el tiempo óptimo (es decir, la complejidad computacional de la multiplicación de matrices ) sigue siendo desconocido. A partir de abril de 2024 ^[actualizar], el mejor límite anunciado para la complejidad asintótica de un algoritmo de multiplicación de matrices es el tiempo $O(n 2,371552)$ , dado por Williams , Xu, Xu y Zhou. ^[2]^[3] Esto mejora el límite de tiempo $O(n 2,3728596)$ , dado por Alman y Williams. ^[4]^[5] Sin embargo, este algoritmo es un algoritmo galáctico debido a las grandes constantes y no se puede realizar de manera práctica.

Algoritmo iterativo

La definición de multiplicación de matrices es que si $C = AB$ para una matriz $A de$ $n \times m$ y una matriz $B de$ $m$ $\times$ $p$ , entonces $C$ es una matriz $de n$ $\times$ $p$ con entradas

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.

A partir de esto, se puede construir un algoritmo simple que recorre los índices $i$ desde 1 hasta $n$ y $j$ desde 1 hasta $p$ , calculando lo anterior mediante un bucle anidado:

Entrada: matrices $A$ y $B$
Sea $C$ una nueva matriz del tamaño apropiado
Para i de 1 a n :
- Para j de 1 a p :
  - Sea $suma = 0$
  - Para k de 1 a m :
    - Conjunto $suma \leftarrow suma + A ik \times B kj$
  - Conjunto $C ij \leftarrow suma$
Devolver $C$

Este algoritmo toma un tiempo $Θ(nmp)$ (en notación asintótica ). ^[1] Una simplificación común para el propósito del análisis de algoritmos es asumir que las entradas son todas matrices cuadradas de tamaño $n \times n$ , en cuyo caso el tiempo de ejecución es $Θ(n 3)$ , es decir, cúbico en el tamaño de la dimensión. ^[6]

Comportamiento de la caché

Los tres bucles en la multiplicación iterativa de matrices se pueden intercambiar arbitrariamente entre sí sin que esto afecte la corrección o el tiempo de ejecución asintótico. Sin embargo, el orden puede tener un impacto considerable en el rendimiento práctico debido a los patrones de acceso a la memoria y al uso de la memoria caché del algoritmo; ^[1] el mejor orden también depende de si las matrices se almacenan en orden de fila principal, orden de columna principal o una combinación de ambos.

En particular, en el caso idealizado de un caché completamente asociativo que consta de $M$ bytes y $b$ bytes por línea de caché (es decir ,METRO/b⁠ líneas de caché), el algoritmo anterior no es óptimo para $A$ y $B$ almacenados en orden de fila principal. Cuando $n > ⁠ METRO / b ⁠$ , cada iteración del bucle interno (un barrido simultáneo a través de una fila de $A$ y una columna de $B$ ) incurre en un error de caché al acceder a un elemento de $B$ . Esto significa que el algoritmo incurre en $Θ(n 3)$ errores de caché en el peor de los casos. A partir de 2010^[actualizar], la velocidad de las memorias en comparación con la de los procesadores es tal que los errores de caché, en lugar de los cálculos reales, dominan el tiempo de ejecución para matrices considerables.^[7]

La variante óptima del algoritmo iterativo para $A$ y $B$ en disposición de filas principales es una versión en mosaico , donde la matriz se divide implícitamente en mosaicos cuadrados de tamaño $\sqrt M$ por $\sqrt M$ : ^[7]^[8]

Entrada: matrices $A$ y $B$
Sea $C$ una nueva matriz del tamaño apropiado
Elija un tamaño de mosaico $T = Θ(\sqrt M)$
Para I de 1 a n en pasos de T :
- Para J de 1 a p en pasos de T :
  - Para K de 1 a m en pasos de T :
    - Multiplicamos $A I : I + T, K : K + T$ y $B K : K + T, J : J + T$ por $C I : I + T, J : J + T$ , es decir:
    - Para i desde I hasta min( I + T , n ) :
      - Para $j$ desde $J$ hasta $min(J + T, p)$ :
        Sea $suma = 0$
        Para $k$ desde $K$ hasta $min(K + T, m)$ :
        Conjunto $suma \leftarrow suma + A ik \times B kj$
        Establecer $C ij \leftarrow C ij + suma$
Devolver $C$

En el modelo de caché idealizado, este algoritmo solo incurre en $Θ(⁠ número 3 / b\sqrtM )$ errores de caché; el divisor $b \sqrt M$ $equivale a varios órdenes de magnitud en las máquinas modernas ,$ de modo que los cálculos reales dominan el tiempo de ejecución, en lugar de los errores de caché.^[7]

Algoritmo de divide y vencerás

Una alternativa al algoritmo iterativo es el algoritmo de divide y vencerás para la multiplicación de matrices. Este se basa en la partición de bloques.

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},

que funciona para todas las matrices cuadradas cuyas dimensiones son potencias de dos, es decir, las formas son $2 n \times 2 n$ para algún $n$ . El producto matricial es ahora

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

que consiste en ocho multiplicaciones de pares de submatrices, seguidas de un paso de adición. El algoritmo divide y vencerás calcula las multiplicaciones más pequeñas de forma recursiva , utilizando la multiplicación escalar $c 11 = a 11 b 11$ como caso base.

La complejidad de este algoritmo en función de $n$ viene dada por la recurrencia ^[6]

T(1)=\Theta (1);

T(n)=8T(n/2)+\Theta (n^{2}),

teniendo en cuenta las ocho llamadas recursivas a matrices de tamaño $n /2$ y $Θ(n 2)$ para sumar los cuatro pares de matrices resultantes elemento por elemento. La aplicación del teorema maestro para recurrencias de divide y vencerás muestra que esta recursión tiene la solución $Θ(n 3)$ , la misma que el algoritmo iterativo. ^[6]

Matrices no cuadradas

Una variante de este algoritmo que funciona para matrices de formas arbitrarias y es más rápida en la práctica ^[7] divide las matrices en dos en lugar de cuatro submatrices, de la siguiente manera. ^[9] Dividir una matriz ahora significa dividirla en dos partes de igual tamaño, o lo más cercanas a tamaños iguales como sea posible en el caso de dimensiones impares.

Entradas: matrices $A$ de tamaño $n \times m$ , $B$ de tamaño $m \times p$ .
Caso base: si $max(n, m, p)$ está por debajo de cierto umbral, utilice una versión desenrollada del algoritmo iterativo.
Casos recursivos:

Si $max(n, m, p) = n$ , divide $A$ horizontalmente:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

De lo contrario, si $máx(n, m, p) = p$ , dividir $B$ verticalmente:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

De lo contrario, $máx(n, m, p) = m$ . Divida $A$ verticalmente y $B$ horizontalmente:

C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}

Comportamiento de la caché

La tasa de errores de caché de la multiplicación de matrices recursiva es la misma que la de una versión iterativa en mosaico , pero a diferencia de ese algoritmo, el algoritmo recursivo no tiene en cuenta la caché : ^[9] no se requiere ningún parámetro de ajuste para obtener un rendimiento óptimo de la caché, y se comporta bien en un entorno de multiprogramación donde los tamaños de caché son efectivamente dinámicos debido a que otros procesos ocupan espacio de caché. ^[7] (El algoritmo iterativo simple también no tiene en cuenta la caché, pero es mucho más lento en la práctica si el diseño de la matriz no está adaptado al algoritmo).

La cantidad de errores de caché que se producen con este algoritmo, en una máquina con $M$ líneas de caché ideal, cada una de tamaño $b$ bytes, está limitada por ^[9]^{: 13}

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

Algoritmos subcúbicos

Existen algoritmos que proporcionan mejores tiempos de ejecución que los sencillos. El primero en ser descubierto fue el algoritmo de Strassen , ideado por Volker Strassen en 1969 y a menudo denominado "multiplicación rápida de matrices". Se basa en una forma de multiplicar dos matrices $de 2 \times 2$ que requieren solo 7 multiplicaciones (en lugar de las 8 habituales), a expensas de varias operaciones de suma y resta adicionales. Al aplicar esto de forma recursiva, se obtiene un algoritmo con un coste multiplicativo de . El algoritmo de Strassen es más complejo y la estabilidad numérica se reduce en comparación con el algoritmo ingenuo, ^[10] pero es más rápido en los casos en los que $n$ $> 100$ o así ^[1] y aparece en varias bibliotecas, como BLAS . ^[11] Es muy útil para matrices grandes sobre dominios exactos como los campos finitos , donde la estabilidad numérica no es un problema. $O(n^{\log _{2}7})\approx O(n^{2.807})$

Dado que el algoritmo de Strassen se utiliza actualmente en software numérico práctico y sistemas de álgebra computacional, mejorar las constantes ocultas en la notación O grande tiene sus méritos. A continuación se incluye una tabla que compara aspectos clave de la versión mejorada basada en la multiplicación recursiva de matrices de bloques 2x2 mediante multiplicaciones de matrices de 7 bloques. Como es habitual, se indican las dimensiones de la matriz y se designa el tamaño de la memoria. $n$ $M$

Se sabe que un algoritmo similar al de Strassen con un paso de matriz de bloques 2x2 requiere al menos 7 multiplicaciones de matrices de bloques. En 1976, Probert ^[16] demostró que un algoritmo de este tipo requiere al menos 15 adiciones (incluidas las restas), sin embargo, una suposición oculta era que los bloques y la matriz de bloques 2x2 están representados en la misma base. Karstadt y Schwartz calcularon en diferentes bases y cambiaron 3 adiciones por transformaciones de base menos costosas. También demostraron que no se puede ir por debajo de 12 adiciones por paso utilizando diferentes bases. En un trabajo posterior, Beniamini et al. ^[17] aplicaron este truco de cambio de base a descomposiciones más generales que las matrices de bloques 2x2 y mejoraron la constante principal para sus tiempos de ejecución.

Es una pregunta abierta en la informática teórica hasta qué punto se puede mejorar el algoritmo de Strassen en términos de complejidad asintótica . El exponente de multiplicación de matrices , normalmente denotado como , es el número real más pequeño para el que cualquier matriz sobre un cuerpo se puede multiplicar entre sí mediante operaciones de cuerpo. La mejor cota actual de es , por Williams , Xu, Xu y Zhou. ^[2]^[4] Este algoritmo, como todos los demás algoritmos recientes en esta línea de investigación, es una generalización del algoritmo Coppersmith-Winograd, que fue propuesto por Don Coppersmith y Shmuel Winograd en 1990. ^[18] La idea conceptual de estos algoritmos es similar al algoritmo de Strassen: se idea una forma de multiplicar dos $k$ $\times$ $k$ -matrices con menos de $k$ $3$ multiplicaciones, y esta técnica se aplica de forma recursiva. Sin embargo, el coeficiente constante oculto por la notación Big O es tan grande que estos algoritmos solo valen la pena para matrices que son demasiado grandes para manejarlas en las computadoras actuales. ^[19]^[20] $\omega$ $n\times n$ $n^{\omega +o(1)}$ $\omega$ $\omega <2.371552$

El algoritmo de Freivalds es un algoritmo de Monte Carlo simple que , dadas las matrices $A$ , $B$ y $C$ , verifica en tiempo $Θ(n 2)$ si $AB = C.$

Tensor alfa

En 2022, DeepMind presentó AlphaTensor, una red neuronal que utilizó una analogía de juego de un solo jugador para inventar miles de algoritmos de multiplicación de matrices, incluidos algunos descubiertos previamente por humanos y otros que no. ^[21] Las operaciones se restringieron al campo fundamental no conmutativo (aritmética normal) y al campo finito $\mathbb {Z} /2\mathbb {Z}$ (aritmética mod 2). El mejor algoritmo "práctico" (descomposición explícita de bajo rango de un tensor de multiplicación de matrices) encontrado funcionó en O(n ^2.778 ). ^[22] Encontrar descomposiciones de bajo rango de tales tensores (y más allá) es NP-hard; la multiplicación óptima incluso para matrices 3x3 sigue siendo desconocida , incluso en el campo conmutativo. ^[22] En matrices 4x4, AlphaTensor descubrió inesperadamente una solución con 47 pasos de multiplicación, una mejora con respecto a los 49 requeridos con el algoritmo de Strassen de 1969, aunque restringida a la aritmética mod 2. De manera similar, AlphaTensor resolvió matrices de 5x5 con 96 pasos en lugar de los 98 de Strassen. Basándose en el sorprendente descubrimiento de que tales mejoras existen, otros investigadores pudieron encontrar rápidamente un algoritmo 4x4 independiente similar y ajustaron por separado el algoritmo 5x5 de 96 pasos de Deepmind a 95 pasos en aritmética módulo 2 y a 97 ^[23] en aritmética normal. ^[24] Algunos algoritmos nunca se habían descubierto antes, por ejemplo, (4, 5, 5) se mejoró de 80 a 76 en aritmética normal y módulo 2.

Algoritmos paralelos y distribuidos

Paralelismo de memoria compartida

El algoritmo de dividir y vencer esbozado anteriormente se puede paralelizar de dos maneras para multiprocesadores de memoria compartida . Estas se basan en el hecho de que las ocho multiplicaciones de matrices recursivas en

{\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

se pueden realizar independientemente una de la otra, al igual que las cuatro sumas (aunque el algoritmo necesita "unir" las multiplicaciones antes de realizar las sumas). Al explotar el paralelismo completo del problema, se obtiene un algoritmo que se puede expresar en pseudocódigo de estilo fork-join : ^[25]

Procedimiento $multiplicar(C, A, B)$ :

Caso base: si $n = 1$ , establezca $c 11 \leftarrow a 11 \times b 11$ (o multiplique una matriz de bloque pequeña).
De lo contrario, asigne espacio para una nueva matriz T de forma n × n , luego:
- Partición $A$ en $A 11$ , $A 12$ , $A 21$ , $A 22$ .
- Partición $B$ en $B 11$ , $B 12$ , $B 21$ , $B 22$ .
- Partición $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Partición $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- Ejecución paralela:
  - Tenedor $multiplicar(C 11, A 11, B 11)$ .
  - Tenedor $multiplicar(C 12, A 11, B 12)$ .
  - Tenedor $multiplicar(C 21, A 21, B 11)$ .
  - Tenedor $multiplicar(C 22, A 21, B 12)$ .
  - Tenedor $multiplicar(T 11, A 12, B 21)$ .
  - Multiplicar bifurcación $(T 12, A 12, B 22)$ .
  - Tenedor $multiplicar(T 21, A 22, B 21)$ .
  - Tenedor $multiplicar(T 22, A 22, B 22)$ .
- Unirse (esperar a que se completen las bifurcaciones paralelas).
- $añadir(C, T)$ .
- Desasignar $T$ .

El procedimiento $add(C, T)$ agrega $T$ a $C$ , elemento por elemento:

Caso base: si $n = 1$ , establezca $c 11 \leftarrow c 11 + t 11$ (o haga un bucle corto, quizás desenrollado).
De lo contrario:
- Partición $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Partición $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- En paralelo:
  - Horquilla $añadir(C 11, T 11)$ .
  - Horquilla $añadir(C 12, T 12)$ .
  - Horquilla $añadir(C 21, T 21)$ .
  - Horquilla $añadir(C 22, T 22)$ .
- Unirse .

Aquí, fork es una palabra clave que indica que un cálculo puede ejecutarse en paralelo con el resto de la llamada a la función, mientras que join espera a que se completen todos los cálculos "bifurcados" previamente. $La partición$ logra su objetivo únicamente mediante la manipulación del puntero.

Este algoritmo tiene una longitud de ruta crítica de $Θ(log 2 n)$ pasos, lo que significa que lleva ese tiempo en una máquina ideal con un número infinito de procesadores; por lo tanto, tiene una aceleración máxima posible de $Θ(n 3 /log 2 n)$ en cualquier computadora real. El algoritmo no es práctico debido al costo de comunicación inherente al movimiento de datos hacia y desde la matriz temporal $T$ , pero una variante más práctica logra una aceleración $de Θ(n 2)$ , sin usar una matriz temporal. ^[25]

Algoritmos distribuidos y que evitan la comunicación

En las arquitecturas modernas con memoria jerárquica, el costo de cargar y almacenar elementos de la matriz de entrada tiende a dominar el costo de la aritmética. En una sola máquina, esta es la cantidad de datos transferidos entre la RAM y la memoria caché, mientras que en una máquina multinodo con memoria distribuida es la cantidad transferida entre nodos; en ambos casos se denomina ancho de banda de comunicación . El algoritmo ingenuo que utiliza tres bucles anidados utiliza un ancho de banda de comunicación $de Ω(n 3)$ .

El algoritmo de Cannon , también conocido como algoritmo 2D , es un algoritmo que evita la comunicación y que divide cada matriz de entrada en una matriz de bloques cuyos elementos son submatrices de tamaño $\sqrt M /3$ por $\sqrt M /3$ , donde $M$ es el tamaño de la memoria rápida. ^[26] Luego, se utiliza el algoritmo ingenuo sobre las matrices de bloques, calculando productos de submatrices completamente en la memoria rápida. Esto reduce el ancho de banda de comunicación a $O (n 3 / \sqrt M)$ , que es asintóticamente óptimo (para algoritmos que realizan cálculos $Ω(n 3)$ ). ^[27]^[28]

En un entorno distribuido con $p$ procesadores dispuestos en una malla 2D de $\sqrt p$ por $\sqrt p$ , se puede asignar una submatriz del resultado a cada procesador, y el producto se puede calcular con cada procesador transmitiendo $O (n 2 / \sqrt p)$ palabras, lo que es asintóticamente óptimo suponiendo que cada nodo almacena los $O (n 2 / p)$ elementos mínimos. ^[28] Esto se puede mejorar con el algoritmo 3D, que organiza los procesadores en una malla de cubo 3D, asignando cada producto de dos submatrices de entrada a un solo procesador. Las submatrices de resultado se generan luego realizando una reducción sobre cada fila. ^[29] Este algoritmo transmite $O (n 2 / p 2/3)$ palabras por procesador, lo que es asintóticamente óptimo. ^[28] Sin embargo, esto requiere replicar cada elemento de la matriz de entrada $p 1/3$ veces, y por lo tanto requiere un factor de $p 1/3$ más memoria de la necesaria para almacenar las entradas. Este algoritmo se puede combinar con Strassen para reducir aún más el tiempo de ejecución. ^[29] Los algoritmos "2.5D" proporcionan un equilibrio continuo entre el uso de la memoria y el ancho de banda de comunicación. ^[30] En entornos informáticos distribuidos modernos como MapReduce , se han desarrollado algoritmos de multiplicación especializados. ^[31]

Algoritmos para mallas

Hay una variedad de algoritmos para la multiplicación en mallas . Para la multiplicación de dos n × n en una malla bidimensional estándar utilizando el algoritmo 2D de Cannon , uno puede completar la multiplicación en 3 n -2 pasos aunque esto se reduce a la mitad de este número para cálculos repetidos. ^[32] La matriz estándar es ineficiente porque los datos de las dos matrices no llegan simultáneamente y deben rellenarse con ceros.

El resultado es incluso más rápido en una malla de alambre cruzado de dos capas, donde solo se necesitan 2 n -1 pasos. ^[33] El rendimiento mejora aún más para los cálculos repetidos, lo que lleva a una eficiencia del 100%. ^[34] La matriz de malla de alambre cruzado puede verse como un caso especial de una estructura de procesamiento no plana (es decir, multicapa). ^[35]

Véase también

Referencias

^ abcd Skiena, Steven (2012). "Ordenamiento y búsqueda". Manual de diseño de algoritmos . Springer. págs. 45-46, 401-3. doi :10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
^ ab Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2024), Nuevos límites para la multiplicación de matrices: de alfa a omega , arXiv : 2307.07970
^ Duan, Ran; Wu, Hongxun; Zhou, Renfei (2022), Multiplicación de matrices más rápida mediante hash asimétrico , arXiv : 2210.10173
^ ab 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 (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 .
^ abc Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. págs. 75–79. ISBN 0-262-03384-4.
^ abcde Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Ingeniería de rendimiento de sistemas de software, lección 8". MIT OpenCourseWare . Instituto Tecnológico de Massachusetts . Consultado el 27 de enero de 2015 .
^ Lam, Monica S.; Rothberg, Edward E.; Wolf, Michael E. (1991). Rendimiento de la caché y optimizaciones de algoritmos bloqueados . ASPLOS91: 4.ª conferencia internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos. doi :10.1145/106972.106981. ISBN 978-0-89791-380-5.
^ abc Prokop, Harald (1999). Algoritmos ajenos a la caché (PDF) (Máster). MIT. hdl :1721.1/80568.
^ 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
^ 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.
^ Strassen, Volker (1969). "La eliminación gaussiana no es óptima". Numer. Math . 13 (4): 354–356. doi :10.1007/BF02165411. S2CID 121656251.
^ Winograd, Shmuel (1971). "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 .
^ Karstadt, Elaye; Schwartz, Oded (julio de 2017). "Multiplicación de matrices, un poco más rápida". Actas del 29.° Simposio ACM sobre paralelismo en algoritmos y arquitecturas . SPAA '17. págs. 101–110. doi :10.1145/3087556.3087579.
^ Schwartz, Oded; Vaknin, Noa (2023). "Juego de Pebbling y base alternativa para la multiplicación de matrices de alto rendimiento". Revista SIAM de informática científica . págs. C277–C303. doi :10.1137/22M1502719.
^ Probert, Robert L. (1976). "Sobre la complejidad aditiva de la multiplicación de matrices". SIAM J. Comput . 5 (2): 187–203. doi :10.1137/0205016.
^ Beniamini, Gal; Cheng, Nathan; Holtz, Olga; Karstadt, Elaye; Schwartz, Oded (2020). "Esparcimiento de los operadores de algoritmos de multiplicación rápida de matrices". arXiv : 2008.03759 [cs.DS].
^ 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
^ 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 , recuperado 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.
^ 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 de 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.
^ "Descubrimiento de nuevos algoritmos con AlphaTensor". www.deepmind.com . 5 de octubre de 2022 . Consultado el 1 de noviembre de 2022 .
^ ab Fawzi, Alhussein; Balog, Matej; Huang, Aja; Hubert, Thomas; Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; R. Ruiz, Francisco J.; Schrittwieser, Julian; Swirszcz, Grzegorz; Silver, David; Hassabis, Demis; Kohli, Pushmeet (octubre de 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. ISSN 1476-4687. PMC 9534758 . PMID 36198780.
^ Kauers, Manuel; Moosbauer, Jakob (2 de diciembre de 2022). "Gráficos invertidos para la multiplicación de matrices". arXiv : 2212.01175 [cs.SC].
^ Brubaker, Ben (23 de noviembre de 2022). «La IA revela nuevas posibilidades en la multiplicación de matrices». Quanta Magazine . Consultado el 26 de noviembre de 2022 .
^ ab Randall, Keith H. (1998). Cilk: Computación multiproceso eficiente (PDF) (Ph.D.). Instituto Tecnológico de Massachusetts. págs. 54–57. hdl :1721.1/47519.
^ Cannon, Lynn Elliot (14 de julio de 1969). Una computadora celular para implementar el algoritmo de filtro de Kalman (Ph.D.). Universidad Estatal de Montana.
^ Hong, JW; Kung, HT (1981). "Complejidad de E/S: el juego de las piedras rojas y azules" (PDF) . Actas del decimotercer simposio anual de la ACM sobre teoría de la computación - STOC '81 . págs. 326–333. doi :10.1145/800076.802486. S2CID 8410593. Archivado (PDF) desde el original el 15 de diciembre de 2019.
^ abc Irony, Dror; Toledo, Sivan; Tiskin, Alexander (septiembre de 2004). "Límites inferiores de comunicación para la multiplicación de matrices con memoria distribuida". J. Parallel Distrib. Comput . 64 (9): 1017–26. CiteSeerX 10.1.1.20.7034 . doi :10.1016/j.jpdc.2004.03.021.
^ ab Agarwal, RC; Balle, SM; Gustavson, FG; Joshi, M.; Palkar, P. (septiembre de 1995). "Un enfoque tridimensional para la multiplicación de matrices paralelas". IBM J. Res. Dev . 39 (5): 575–582. CiteSeerX 10.1.1.44.3404 . doi :10.1147/rd.395.0575.
^ Solomonik, Edgar; Demmel, James (2011). "Algoritmos de multiplicación de matrices paralelas 2.5D y factorización LU para comunicación óptima" (PDF) . Actas de la 17.ª Conferencia Internacional sobre Procesamiento Paralelo . Vol. Parte II. págs. 90–109. doi :10.1007/978-3-642-23397-5_10. ISBN 978-3-642-23397-5.
^ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF) . arXiv : 1304.1467 . Código Bibliográfico :2013arXiv1304.1467B . Consultado el 12 de julio de 2014 .
^ Bae, SE; Shinn, T.-W.; Takaoka, T. (2014). "Un algoritmo paralelo más rápido para la multiplicación de matrices en una matriz de malla". Procedia Computer Science . 29 : 2230–40. doi : 10.1016/j.procs.2014.05.208 .
^ Kak, S (1988). "Una matriz de malla de dos capas para la multiplicación de matrices". Computación paralela . 6 (3): 383–5. CiteSeerX 10.1.1.88.8527 . doi :10.1016/0167-8191(88)90078-6.
^ Kak, S. (2014). "Eficiencia de la multiplicación de matrices en la matriz de malla de alambres cruzados". arXiv : 1411.3273 [cs.DC].
^ Kak, S (1988). "Computación en matriz multicapa". Ciencias de la información . 45 (3): 347–365. CiteSeerX 10.1.1.90.4753 . doi :10.1016/0020-0255(88)90010-2.

Lectura adicional

Buttari, Alfredo; Langou, Julien; Kurzak, Jakub; Dongarra, Jack (2009). "Una clase de algoritmos de álgebra lineal en mosaico paralelo para arquitecturas multinúcleo". Computación paralela . 35 : 38–53. arXiv : 0709.1272 . doi :10.1016/j.parco.2008.10.002. S2CID 955.
Goto, Kazushige; van de Geijn, Robert A. (2008). "Anatomía de la multiplicación de matrices de alto rendimiento". ACM Transactions on Mathematical Software . 34 (3): 1–25. CiteSeerX 10.1.1.140.3583 . doi :10.1145/1356052.1356053. S2CID 9359223.
Van Zee, Field G.; van de Geijn, Robert A. (2015). "BLIS: un marco para instanciar rápidamente la funcionalidad de BLAS". ACM Transactions on Mathematical Software . 41 (3): 1–33. doi :10.1145/2764454. S2CID 1242360.
Cómo optimizar GEMM