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 entre múltiples procesadores (quizás a través de una red).

La aplicación directa de la definición matemática de multiplicación de matrices da un algoritmo que toma tiempo del orden de $n 3$ operaciones de campo para multiplicar dos $n \times n$ matrices sobre ese campo ( $Θ (n 3)$ en notación O grande ). Desde el algoritmo de Strassen en la década de 1960 se conocen mejores límites asintóticos en el tiempo necesario para multiplicar matrices , pero el tiempo óptimo (es decir, la complejidad computacional de la multiplicación de matrices ) sigue siendo desconocido. En abril de 2024 ^[actualizar], el límite mejor anunciado sobre 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 en la 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$ de 1 a $n$ y $j$ de 1 a $p$ , calculando lo anterior usando 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$
Volver $C$

Este algoritmo requiere 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 todas las entradas son 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 caché

Los tres bucles en la multiplicación iterativa de matrices se pueden intercambiar arbitrariamente entre sí sin afectar 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 caché del algoritmo; ^[1] qué orden es mejor 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 ideal de una caché totalmente asociativa que consta de $M$ bytes y $b$ bytes por línea de caché (es decir,METRO/blíneas de caché), el algoritmo anterior es subó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 una pérdida 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 comparada con la de los procesadores es tal que las pérdidas de caché, en lugar de los cálculos reales, dominan el tiempo de ejecución para matrices importantes. ^[7]

La variante óptima del algoritmo iterativo para $A$ y $B$ en diseño de fila principal 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 :
    - Multiplica $A I : I + T, K : K + T$ y $B K : K + T, J : J + T$ en $C I : I + T, J : J + T$ , es decir:
    - Para i de I a min( I + T , n ) :
      - Para $j$ de $J$ a $min(J + T, p)$ :
        Sea $suma = 0$
        Para $k$ de $K$ a $min(K + T, m)$ :
        Conjunto $suma \leftarrow suma + A ik \times B kj$
        Conjunto $C ij \leftarrow C ij + suma$
Volver $C$

En el modelo de caché idealizado, este algoritmo incurre sólo $en Θ(norte 3 / segundo \sqrt M)$ errores de caché; el divisor $b \sqrt M$ asciende 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. Esto se basa en la partición del bloque.

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{pmatriz}},

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 de la matriz ahora es

{\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 consta de ocho multiplicaciones de pares de submatrices, seguidas de un paso de suma. 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 por elementos. La aplicación del teorema maestro para las recurrencias de divide y vencerás muestra que esta recursividad tiene la solución $Θ(n 3)$ , igual 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 cerca posible de tamaños iguales 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 algún umbral, utilice una versión desenrollada del algoritmo iterativo.
Casos recursivos:

Si $max(n, m, p) = n$ , divida $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 $max(n, m, p) = p$ , divida $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 caché

La tasa de pérdida de caché de la multiplicación recursiva de matrices 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 el caché : ^[9] no se requiere ningún parámetro de ajuste para obtener un rendimiento óptimo del 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 en caché. ^[7] (El algoritmo iterativo simple tampoco tiene en cuenta la memoria caché, pero en la práctica es mucho más lento si el diseño de la matriz no se adapta al algoritmo).

El número de errores de caché incurridos por 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 al que a menudo se hace referencia como "multiplicación rápida de matrices". Se basa en una forma de multiplicar dos matrices $de 2 \times 2$ que requiere sólo 7 multiplicaciones (en lugar de las 8 habituales), a expensas de varias operaciones adicionales de suma y resta. La aplicación de esto de forma recursiva da un algoritmo con un costo 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$ aproximadamente ^[1] y aparece en varias bibliotecas, como BLAS . ^[11] Es muy útil para matrices grandes en dominios exactos, como 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 en realidad en software numérico práctico y sistemas de álgebra informática, mejorar las constantes ocultas en la notación O grande tiene sus ventajas. A continuación se muestra una tabla que compara los aspectos clave de la versión mejorada basada en la multiplicación recursiva de matrices de bloques de 2x2 mediante multiplicaciones de matrices de 7 bloques. Como es habitual, indica las dimensiones de la matriz y designa el tamaño de la memoria. $n$ $M$

Se sabe que un algoritmo tipo Strassen con un paso de matriz de bloques de 2x2 requiere al menos 7 multiplicaciones de matrices de bloques. En 1976, Probert ^[15] demostró que dicho algoritmo requiere al menos 15 sumas (incluidas las restas), sin embargo, una suposición oculta era que los bloques y la matriz de bloques de 2x2 están representados en la misma base. Karstadt y Schwartz calcularon en bases diferentes e intercambiaron 3 adiciones por transformaciones de bases menos costosas. También demostraron que no se pueden bajar de 12 adiciones por paso usando diferentes bases. En trabajos posteriores Beniamini et el. ^[16] aplicaron este truco de cambio de base a descomposiciones más generales que las matrices de bloques de 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 , generalmente denominado , es el número real más pequeño por el cual cualquier matriz sobre un campo se puede multiplicar mediante operaciones de campo. El mejor vinculado actualmente es , de 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. ^[17] La idea conceptual de estos Los algoritmos son similares 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 O grande es tan grande que estos algoritmos sólo valen la pena para matrices que son demasiado grandes para manejarlas en las computadoras actuales. ^[18]^[19] $\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.$

AlfaTensor

En 2022, DeepMind presentó AlphaTensor, una red neuronal que utilizaba una analogía de juego para un solo jugador para inventar miles de algoritmos de multiplicación de matrices, incluidos algunos descubiertos previamente por humanos y otros que no. ^[20] Las operaciones se restringieron al campo terrestre 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 se ejecutó en O (n ^2,778 ). ^[21] Encontrar descomposiciones de bajo rango de tales tensores (y más allá) es NP-difícil; La multiplicación óptima incluso para matrices de 3x3 sigue siendo desconocida , incluso en el campo conmutativo. ^[21] 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 restringido a la aritmética mod 2. De manera similar, AlphaTensor resolvió matrices de 5x5 con 96 en lugar de los 98 pasos de Strassen. Basándose en el sorprendente descubrimiento de que existen tales mejoras, otros investigadores pudieron encontrar rápidamente un algoritmo 4x4 independiente similar y modificaron por separado el algoritmo 5x5 de 96 pasos de Deepmind hasta 95 pasos en aritmética mod 2 y 97 ^[22] en aritmética normal. ^[23] Algunos algoritmos nunca se habían descubierto antes, por ejemplo (4, 5, 5) se mejoraron de 80 a 76 en aritmética normal y mod 2.

Algoritmos paralelos y distribuidos.

Paralelismo de memoria compartida

El algoritmo de divide y vencerás esbozado anteriormente se puede paralelizar de dos maneras para multiprocesadores de memoria compartida . Estos 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 uno del otro, al igual que las cuatro sumas (aunque el algoritmo necesita "unir" las multiplicaciones antes de hacer las sumas). Explotando todo el paralelismo del problema, se obtiene un algoritmo que puede expresarse en pseudocódigo estilo fork-join : ^[24]

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ño).
De lo contrario, asigne espacio para una nueva matriz T de forma n × n , entonces:
- Divida $A$ en $A 11$ , $A 12$ , $A 21$ , $A 22$ .
- Divida $B$ en $B 11$ , $B 12$ , $B 21$ , $B 22$ .
- Divida $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Divida $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- Ejecución paralela:
  - Multiplicación de bifurcación $(C 11, A 11, B 11)$ .
  - Multiplicación de horquilla $(C 12, A 11, B 12)$ .
  - Multiplicación de bifurcación $(C 21, A 21, B 11)$ .
  - Multiplicación de horquilla $(C 22, A 21, B 12)$ .
  - Multiplicación de horquilla $(T 11, A 12, B 21)$ .
  - Multiplicación de horquilla $(T 12, A 12, B 22)$ .
  - Multiplicación de bifurcación $(T 21, A 22, B 21)$ .
  - Multiplicación de horquilla $(T 22, A 22, B 22)$ .
- Únete (espera a que se completen las bifurcaciones paralelas).
- $agregar(C, T)$ .
- Desasignar $T$ .

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

Caso base: si $n = 1$ , establezca $c 11 \leftarrow c 11 + t 11$ (o haga un bucle corto, quizás desenrollado).
De lo contrario:
- Divida $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Divida $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- En paralelo:
  - Agregar horquilla $(C 11, T 11)$ .
  - Añadir horquilla $(C 12, T 12)$ .
  - Añadir horquilla $(C 21, T 21)$ .
  - Añadir horquilla $(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 previamente "bifurcados". $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 esa misma cantidad de 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 mover datos hacia y desde la matriz temporal $T$ , pero una variante más práctica logra una aceleración $Θ(n 2)$ , sin utilizar una matriz temporal. ^[24]

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 el caché, mientras que en una máquina de múltiples nodos con memoria distribuida es la cantidad transferida entre nodos; en cualquier caso se llama ancho de banda de comunicación . El algoritmo ingenuo que utiliza tres bucles anidados utiliza un ancho de banda de comunicación $Ω (n 3)$ .

El algoritmo de Cannon , también conocido como algoritmo 2D , es un algoritmo que evita la comunicación y 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. ^[25] El algoritmo ingenuo se utiliza luego sobre las matrices de bloques, calculando productos de submatrices completamente en 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álculo $Ω (n 3)$ ). ^[26]^[27]

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 cual es asintóticamente óptimo asumiendo que cada nodo almacena el mínimo de elementos $O (n 2 / p)$ . ^[27] Esto se puede mejorar mediante el algoritmo 3D, que organiza los procesadores en una malla cúbica 3D, asignando cada producto de dos submatrices de entrada a un solo procesador. Luego, las submatrices resultantes se generan realizando una reducción en cada fila. ^[28] Este algoritmo transmite $O (n 2 / p 2/3)$ palabras por procesador, lo cual es asintóticamente óptimo. ^[27] Sin embargo, esto requiere replicar cada elemento de la matriz de entrada $p 1/3$ veces, por lo que requiere un factor de $p 1/3$ más de 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. ^[28] Los algoritmos "2.5D" proporcionan un equilibrio continuo entre el uso de memoria y el ancho de banda de comunicación. ^[29] En entornos informáticos distribuidos modernos como MapReduce , se han desarrollado algoritmos de multiplicación especializados. ^[30]

Algoritmos para mallas

Existe una variedad de algoritmos para la multiplicación sobre mallas . Para la multiplicación de dos n × n en una malla bidimensional estándar utilizando el algoritmo de 2D Cannon , se 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. ^[31] 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 aún más rápido en una malla de alambre cruzado de dos capas, donde solo se necesitan 2 n -1 pasos. ^[32] El rendimiento mejora aún más para cálculos repetidos que conducen a una eficiencia del 100%. ^[33] La matriz de malla cruzada puede verse como un caso especial de una estructura de procesamiento no plana (es decir, multicapa). ^[34]

Ver también

Referencias

^ abcd Skiena, Steven (2012). "Clasificación y búsqueda". El manual de diseño de algoritmos . Saltador. 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, corrió; 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 al objetivo mítico". Revista Quanta . Consultado el 1 de abril de 2021 .
^ a b C 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 del rendimiento de sistemas de software, Clase 8". MIT OpenCourseWare . Instituto de Tecnología de Massachusetts . Consultado el 27 de enero de 2015 .
^ Lam, Mónica S.; Rothberg, Edward E.; Lobo, Michael E. (1991). "El rendimiento de la caché y las optimizaciones de los algoritmos bloqueados" . ASPLOS91: 4ta Conferencia Internacional sobre Soporte de Arquitectura 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 al caché (PDF) (Maestría). 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
^ Prensa, William H.; Flannery, Brian P.; Teukolsky, Saúl 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.
^ Strassen, Volker (1969). "La eliminación gaussiana no es óptima". Número. Matemáticas . 13 (4): 354–356. doi :10.1007/BF02165411. S2CID 121656251.
^ Winogrado, 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ápido". Actas del 29º Simposio ACM sobre paralelismo en algoritmos y arquitecturas . ESPAA '17. págs. 101-110. doi :10.1145/3087556.3087579.
^ Probert, Robert L. (1976). "Sobre la complejidad aditiva de la multiplicación de matrices". SIAM J. Computación . 5 (2): 187–203. doi :10.1137/0205016.
^ Beniamini, Gal; Cheng, Nathan; Holtz, Olga; Karstadt, Elaye; Schwartz, Oded (2020). "Reducir los operadores de algoritmos de multiplicación rápida de matrices". arXiv : 2008.03759 [cs.DS].
^ 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
^ Iliopoulos, Costas S. (1989), "Límites de complejidad del 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 5 de marzo de 2014 , consultado el 16 de enero de 2015. El algoritmo Coppersmith-Winograd es no es práctico, debido a la gran constante oculta 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 probar una de las conjeturas, demostrando así que $ω$ $= 2$ , la corona Es poco probable que el enfoque de producto sea aplicable a los grandes problemas matriciales que surgen en la práctica. [...] las matrices de entrada deben ser astronómicamente grandes para que la diferencia en el tiempo sea evidente.
^ "Descubriendo algoritmos novedosos 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, Alejandro; R. Ruiz, Francisco J.; Schrittwieser, Julián; Swirszcz, Grzegorz; Plata, David; Hassabis, Demis; Kohli, Pushmeet (octubre de 2022). "Descubriendo algoritmos de multiplicación de matrices más rápidos con aprendizaje por refuerzo". Naturaleza . 610 (7930): 47–53. Código Bib :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). "Invertir gráficos para 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". Revista Quanta . Consultado el 26 de noviembre de 2022 .
^ ab Randall, Keith H. (1998). Cilk: Computación multiproceso eficiente (PDF) (Ph.D.). Instituto de Tecnología 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 los guijarros rojo-azul" (PDF) . Actas del decimotercer simposio anual de ACM sobre teoría de la informática - 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 Ironía, Dror; Toledo, Siván; Tiskin, Alexander (septiembre de 2004). "Límites inferiores de comunicación para la multiplicación de matrices de memoria distribuida". J. Distribución paralela. Computación . 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. Desarrollo . 39 (5): 575–582. CiteSeerX 10.1.1.44.3404 . doi :10.1147/rd.395.0575.
^ Salomonik, Edgar; Demmel, James (2011). "Algoritmos de factorización LU y multiplicación de matrices 2,5D paralelas óptimas para la comunicación" (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). "Dimensión cuadrada de matriz independiente utilizando MapReduce" (PDF) . arXiv : 1304.1467 . Código Bib : 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 Ciencias de la Computación . 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 cruzada". arXiv : 1411.3273 [cs.DC].
^ Kak, S (1988). "Computación de matrices multicapa". Ciencias de la Información . 45 (3): 347–365. CiteSeerX 10.1.1.90.4753 . doi :10.1016/0020-0255(88)90010-2.

Otras lecturas

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.
Ir a, Kazushige; van de Geijn, Robert A. (2008). "Anatomía de la multiplicación de matrices de alto rendimiento". Transacciones ACM sobre software matemático . 34 (3): 1–25. CiteSeerX 10.1.1.140.3583 . doi :10.1145/1356052.1356053. S2CID 9359223.
Van Zee, Campo G.; van de Geijn, Robert A. (2015). "BLIS: un marco para crear rápidamente instancias de la funcionalidad BLAS". Transacciones ACM sobre software matemático . 41 (3): 1–33. doi :10.1145/2764454. S2CID 1242360.
Cómo optimizar GEMM