Algoritmo de multiplicación de matrices

Debido a que la multiplicación de matrices es una operación tan fundamental en muchos algoritmos numéricos , se ha invertido mucho esfuerzo 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, incluyendo la computación científica y el reconocimiento de patrones , y en problemas aparentemente no relacionados, como el conteo de caminos a través de un grafo . ^{[ 1 ]} Se han diseñado muchos algoritmos diferentes para multiplicar matrices en diferentes tipos de hardware, incluyendo 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 como$ $resultado$ un algoritmo que requiere un tiempo del orden de $n³$ operaciones de campo para multiplicar dos matrices $n \times n$ sobre ese campo ( $Θ(n³)$ en notación O grande ). Se conocen mejores cotas asintóticas para el tiempo requerido 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 septiembre de 2025 , la mejor cota para la complejidad asintótica de un algoritmo de multiplicación de matrices es $O(n 2.371339)$ tiempo, dada por Alman, Duan, Williams , Xu, Xu y Zhou. ^{[ 2 ]} 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$ 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 desde 1 hasta n :
- Para j desde 1 hasta p :
  - Sea $suma = 0$
  - Para k desde 1 hasta m :
    - Suma de conjuntos $\leftarrow suma + A ik \times B kj$
  - Conjunto $C ij \leftarrow suma$
Regresar $C$

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

Comportamiento de la caché

Los tres bucles en la multiplicación iterativa de matrices pueden intercambiarse arbitrariamente entre sí sin afectar la corrección ni 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 el uso de la caché del algoritmo; ^{[ 1 ]} el orden óptimo también depende de si las matrices se almacenan en orden de filas, en orden de columnas o una combinación de ambos.

En particular, en el caso idealizado de una caché totalmente asociativa que consta de $M$ bytes y $b$ bytes por línea de caché (es decir , M / b líneas de caché), el algoritmo anterior es subóptimo para $A$ y $B$ almacenados en orden de filas. Cuando $n > M / b,$ cada iteración del bucle interno (un recorrido simultáneo por una fila de $A$ y una columna de $B ) incurre en un fallo$ $de$ caché al acceder a un elemento de $B.$ Esto significa que el algoritmo incurre en $Θ(n³)$ fallos de caché en el peor de los casos. $A$ partir de 2010La velocidad de las memorias en comparación con la de los procesadores es tal que los fallos de caché, en lugar de los cálculos reales, dominan el tiempo de ejecución para matrices de gran tamaño. ^{[ 4 ]}

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$ : ^{[ 4 ]}^{[ 5 ]}

Entrada: matrices $A$ y $B$
Sea $C$ una nueva matriz del tamaño apropiado.
Elige un tamaño de baldosa $T = Θ(\sqrt M)$
Para I desde 1 hasta n en pasos de T :
- Para J desde 1 hasta p en pasos de T :
  - Para K desde 1 hasta m en pasos de T :
    - Multiplicar $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)$ :
        Suma de conjuntos $\leftarrow suma + A ik \times B kj$
        Conjunto $C ij \leftarrow C ij + suma$
Regresar $C$

En el modelo de caché idealizado, este algoritmo solo incurre en $Θ(⁠ n 3 / b \sqrt M ⁠)$ fallos de caché; el divisor $b \sqrt M$ asciende a varios órdenes de magnitud en las máquinas modernas, por lo que los cálculos reales dominan el tiempo de ejecución, en lugar de los fallos de caché. ^{[ 4 ]}

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 en 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 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 su caso base.

La complejidad de este algoritmo en función de $n$ viene dada por la recurrencia ^{[ 3 ].}

T(1)=\Theta (1);

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

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

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 ^{[ 4 ]} divide las matrices en dos en lugar de cuatro submatrices, como sigue. ^{[ 6 ]} Dividir una matriz ahora significa dividirla en dos partes de igual tamaño, o de tamaños lo más cercanos posible a la igualdad 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 desplegada 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 $max(n, m, p) = p$ , divide $B$ verticalmente:

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

De lo contrario, $max(n, m, p) = m$ . Dividir $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 fallos de caché de la multiplicación recursiva de matrices es la misma que la de una versión iterativa segmentada , pero a diferencia de ese algoritmo, el algoritmo recursivo es independiente de la caché : ^{[ 6 ]} 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é. ^{[ 4 ]} (El algoritmo iterativo simple también es independiente de la caché, pero es mucho más lento en la práctica si la disposición de la matriz no se adapta al algoritmo).

El número de fallos 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á acotado por ^{[ 6 ]}^{: 13}

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

Algoritmos subcúbicos

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

Existen algoritmos que ofrecen mejores tiempos de ejecución que los algoritmos directos. 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×2 que requiere solo 7 multiplicaciones (en lugar de las 8 habituales), a costa de varias operaciones adicionales de suma y resta . Aplicando esto recursivamente se obtiene un algoritmo con un coste multiplicativo de $O(n^{\log _{2}7})\approx O(n^{2.807})$ El algoritmo de Strassen es más complejo y su estabilidad numérica se reduce en comparación con el algoritmo ingenuo, ^{[ 7 ]} pero es más rápido en casos donde $n > 100$ aproximadamente ^{[ 1 ]} 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.

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

Se sabe que un algoritmo tipo Strassen con un paso de matriz de bloques de 2×2 requiere al menos 7 multiplicaciones de matrices de bloques. En 1976, Probert ^{[ 13 ]} demostró que dicho algoritmo requiere al menos 15 sumas (incluidas las restas); sin embargo, una suposición implícita era que los bloques y la matriz de bloques de 2×2 están representados en la misma base. Karstadt y Schwartz calcularon en bases diferentes y cambiaron 3 sumas por transformaciones de base menos costosas. También demostraron que no se puede ir por debajo de 12 sumas por paso usando bases diferentes. En trabajos posteriores, Beniamini et al. ^{[ 14 ]} aplicaron este truco de cambio de base a descomposiciones más generales que las matrices de bloques de 2×2 y mejoraron la constante principal para sus tiempos de ejecución.

En la informática teórica, sigue siendo una cuestión abierta hasta qué punto se puede mejorar el algoritmo de Strassen en términos de complejidad asintótica . El exponente de la multiplicación de matrices , que se suele denotar $\omega$ es el número real más pequeño para el cual cualquier $n\times n$ Las matrices sobre un campo se pueden multiplicar entre sí usando $n^{\omega +o(1)}$ operaciones de campo. El mejor límite actual en $\omega$ es $\omega <2.371339$ , por Alman, Duan, Williams , Xu, Xu y Zhou. ^{[ 2 ]} 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 dado por Don Coppersmith y Shmuel Winograd en 1990. ^{[ 15 ]} La idea conceptual de estos algoritmos es similar al algoritmo de Strassen: se diseña una forma de multiplicar dos matrices $k \times k$ con menos de $k 3$ multiplicaciones, y esta técnica se aplica recursivamente. 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 manejar en las computadoras actuales. ^{[ 16 ]}^{[ 17 ]} Victor Pan propuso los llamados algoritmos factibles de multiplicación de matrices subcúbicas con un exponente ligeramente superior a 2,77, pero a cambio con un coeficiente constante oculto mucho menor. ^{[ 18 ]}

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

AlphaTensor

En 2022, DeepMind presentó AlphaTensor, una red neuronal que utilizó una analogía de juego para un solo jugador para inventar miles de algoritmos de multiplicación de matrices, incluyendo algunos previamente descubiertos por humanos y otros que no lo habían sido. ^{[ 19 ]} Las operaciones se restringieron al campo base no conmutativo (aritmética normal) y al campo finito. $\mathbb {Z} /2\mathbb {Z}$ (aritmética módulo 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 ). ^{[ 20 ]} Encontrar descomposiciones de bajo rango de tales tensores (y más allá) es NP-difícil; la multiplicación óptima incluso para matrices de 3×3 sigue siendo desconocida , incluso en el campo conmutativo. ^{[ 20 ]} En matrices de 4×4, 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 módulo 2. De manera similar, AlphaTensor resolvió matrices de 5×5 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 4×4 independiente similar y ajustaron por separado el algoritmo 5×5 de 96 pasos de Deepmind a 95 pasos en aritmética módulo 2 y a 97 ^{[ 21 ]} en aritmética normal. ^{[ 22 ]} Algunos algoritmos eran completamente nuevos: por ejemplo, (4, 5, 5) se mejoró a 76 pasos desde una base de 80 tanto en aritmética normal como en aritmética módulo 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 recursivas de matrices 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}}

pueden realizarse independientemente unas de otras, al igual que las cuatro sumas (aunque el algoritmo necesita "unir" las multiplicaciones antes de realizar las sumas). Aprovechando el paralelismo total del problema, se obtiene un algoritmo que puede expresarse en pseudocódigo de estilo fork-join : ^[²³^]

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

Caso base: si $n = 1$ , establezca $c 11 \leftarrow a 11 \times b 11$ (o multiplique una matriz de bloques pequeños).
De lo contrario, asigne espacio para una nueva matriz T de forma n × n , y luego:
- Dividir $A$ en $A 11$ , $A 12$ , $A 21$ , $A 22$ .
- Dividir $B$ en $B 11$ , $B 12$ , $B 21$ , $B 22$ .
- Dividir $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Dividir $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- Ejecución en paralelo:
  - Fork $multiply(C 11, A 11, B 11)$ .
  - Fork $multiply(C 12, A 11, B 12)$ .
  - Fork $multiply(C 21, A 21, B 11)$ .
  - Fork $multiply(C 22, A 21, B 12)$ .
  - Fork $multiply(T 11, A 12, B 21)$ .
  - Fork $multiply(T 12, A 12, B 22)$ .
  - Fork $multiply(T 21, A 22, B 21)$ .
  - Fork $multiply(T 22, A 22, B 22)$ .
- Unirse (esperar a que finalicen las bifurcaciones paralelas).
- $agregar(C, T)$ .
- Desasignar $T.$

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

Caso base: si $n = 1$ , establecer $c 11 \leftarrow c 11 + t 11$ (o hacer un bucle corto, tal vez desenrollado).
De lo contrario:
- Dividir $C$ en $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Dividir $T$ en $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- En paralelo:
  - Fork $add(C 11, T 11)$ .
  - Fork $add(C 12, T 12)$ .
  - Fork $add(C 21, T 21)$ .
  - Fork $add(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 finalicen todos los cálculos previamente "bifurcados". $`partition`$ logra su objetivo únicamente mediante la manipulación de punteros.

Este algoritmo tiene una longitud $de$ ruta crítica de $Θ(log₂n) pasos$ , lo que significa que tarda 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³ / log₂n) en$ cualquier ordenador real. El algoritmo no es práctico debido al coste 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²),$ sin utilizar una matriz temporal. ^{[ 23 ]}

Algoritmos distribuidos y que evitan la comunicación

En las arquitecturas modernas con memoria jerárquica, el costo de cargar y almacenar los elementos de la matriz de entrada tiende a predominar sobre el costo de la aritmética. En una sola máquina, esto se refiere a la cantidad de datos transferidos entre la RAM y la caché, mientras que en una máquina multinodo con memoria distribuida se refiere a 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³)$ .

El algoritmo de Cannon , también conocido como algoritmo 2D , es un algoritmo que evita la comunicación y que particiona cada matriz de entrada en una matriz de bloques cuyos elementos son submatrices de tamaño $\sqrt M /3$ × $\sqrt M /3$ , donde $M$ es el tamaño de la memoria rápida. ^{[ 24 ]} El algoritmo ingenuo se utiliza luego 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)$ ). ^{[ 25 ]}^{[ 26 ]}

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 suponiendo que cada nodo almacena el mínimo de $O (n 2 / p)$ elementos. ^{[ 26 ]} Esto se puede mejorar con el algoritmo 3D, que dispone los procesadores en una malla cúbica 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. ^{[ 27 ]} Este algoritmo transmite $O (n 2 / p 2/3)$ palabras por procesador, lo cual es asintóticamente óptimo. ^{[ 26 ]} 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 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. ^{[ 27 ]} Los algoritmos "2.5D" proporcionan un equilibrio continuo entre el uso de memoria y el ancho de banda de comunicación. ^{[ 28 ]} En entornos de computación distribuida modernos como MapReduce , se han desarrollado algoritmos de multiplicación especializados. ^{[ 29 ]}

Algoritmos para mallas

Existen diversos algoritmos para la multiplicación en mallas . Para la multiplicación de dos matrices n × n en una malla bidimensional estándar utilizando el algoritmo de Cannon 2D , se puede completar la multiplicación en 3n - 2 pasos, aunque este número se reduce a la mitad para cálculos repetidos. ^{[ 30 ]} 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. ^{[ 31 ]} El rendimiento mejora aún más para cálculos repetidos que conducen a una eficiencia del 100 %. ^{[ 32 ]} La matriz de malla de alambre cruzado puede considerarse un caso especial de una estructura de procesamiento no planar (es decir, multicapa). ^{[ 33 ]}

En una malla 3D con n ³ elementos de procesamiento, se pueden multiplicar dos matrices en ${\mathcal {O}}(\log n)$ utilizando el algoritmo DNS. ^{[ 34 ]}

Véase también

Referencias

1 2 3 4 Skiena, Steven (2012). "Clasificación 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.
1 2 Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2025). "Mayor asimetría produce una multiplicación de matrices más rápida" . Actas del Simposio Anual ACM-SIAM de 2025 sobre Algoritmos Discretos (SODA) . SIAM. págs. 2005–2039 . doi : 10.1137/1.9781611978322.63 .
^ 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 a 79. ISBN 0-262-03384-4.
1 2 3 4 5 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. Archivado del original el 7 de octubre de 2019. Recuperado el 27 de enero de 2015 .
↑ Lam, Monica S .; Rothberg, Edward E.; Wolf, Michael E. (1991). El rendimiento de la caché y las optimizaciones de los algoritmos bloqueados . ASPLOS91: 4.ª 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.
1 2 3 Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (Maestría). MIT. hdl : 1721.1/80568 . Archivado del original (PDF) el 22-11-2023 . Recuperado el 28-01-2015 .
↑ 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). Numerical Recipes: The Art of Scientific Computing (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 .
↑ Comunicación privada con Probert, Robert L (1976). "Sobre la complejidad aditiva de la multiplicación de matrices" . SIAM Journal on Computing . 5 (2): 187– 203. doi : 10.1137/0205016 .
↑ 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" . SIAM Journal on Scientific Computing . pp. 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). "Esparcificación de los operadores de algoritmos rápidos de multiplicación 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 para algoritmos que computan 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 del original (PDF) el 5 de marzo de 2014 , recuperado el 16 de enero de 2015. El algoritmo de 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 de tiempo sea evidente.
↑ Laderman, Julian; Pan, Victor; Sha, Xuan-He (1992), "Sobre algoritmos prácticos para la multiplicación acelerada de matrices", Álgebra lineal y sus aplicaciones , 162–164 : 557–588 , doi : 10.1016/0024-3795(92)90393-O
↑ "Descubriendo nuevos algoritmos con AlphaTensor" . www.deepmind.com . 5 de octubre de 2022. Consultado el 1 de noviembre de 2022 .
1 2 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. Bibcode : 2022Natur.610...47F . doi : 10.1038/s41586-022-05172-4 . ISSN 1476-4687 . PMC 9534758 . PMID 36198780 .
↑ Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "Flip Graphs for Matrix Multiplication". 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 .
1 2 Randall, Keith H. (1998). Cilk: Computación multihilo eficiente (PDF) (Ph.D.). Instituto Tecnológico de Massachusetts. pp. 54– 57. hdl : 1721.1/47519 . Archivado del original (PDF) el 06-11-2020 . Recuperado el 16-01-2015 .
↑ Cannon, Lynn Elliot (14 de julio de 1969). Una computadora celular para implementar el algoritmo del filtro de Kalman (Tesis doctoral). Universidad Estatal de Montana.
↑ Hong, JW; Kung, HT (1981). "Complejidad de E/S: El juego de la piedra roja y azul" ( 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) del original el 15 de diciembre de 2019.
1 2 3 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (septiembre de 2004). "Límites inferiores de comunicación para la multiplicación de matrices en memoria distribuida". J. Parallel Distrib. Comput . 64 (9): 1017– 26. CiteSeerX 10.1.1.20.7034 . doi : 10.1016/j.jpdc.2004.03.021 .
1 2 Agarwal, RC; Balle, SM; Gustavson, FG; Joshi, M.; Palkar, P. (septiembre de 1995). "Un enfoque tridimensional para la multiplicación paralela de matrices". 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 2.5D y factorización LU en paralelo con 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 . Bibcode : 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 interconectada". arXiv : 1411.3273 [ cs.DC ].
↑ Kak, S (1988). "Computación de matrices multicapa". Information Sciences . 45 (3): 347– 365. CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .
↑ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981). "Algoritmos paralelos de matrices y grafos". SIAM Journal on Computing . 10 (4): 657– 675. doi : 10.1137/0210049 .

Lecturas adicionales

Buttari, Alfredo; Langou, Julien; Kurzak, Jakub; Dongarra, Jack (2009). "Una clase de algoritmos de álgebra lineal en mosaico paralelos 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 BLAS". ACM Transactions on Mathematical Software . 41 (3): 1– 33. doi : 10.1145/2764454 . S2CID 1242360 .
Cómo optimizar GEMM

[skiena-1] 1 2 3 4 Skiena, Steven (2012). "Clasificación 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.

[alman2025-2] 1 2 Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2025). "Mayor asimetría produce una multiplicación de matrices más rápida" . Actas del Simposio Anual ACM-SIAM de 2025 sobre Algoritmos Discretos (SODA) . SIAM. págs. 2005–2039 . doi : 10.1137/1.9781611978322.63 .

[clrs-3] 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 a 79. ISBN 0-262-03384-4.

[ocw-4] 1 2 3 4 5 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. Archivado del original el 7 de octubre de 2019. Recuperado el 27 de enero de 2015 .

[5] Lam, Monica S .; Rothberg, Edward E.; Wolf, Michael E. (1991). El rendimiento de la caché y las optimizaciones de los algoritmos bloqueados . ASPLOS91: 4.ª 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.

[prokop-6] 1 2 3 Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (Maestría). MIT. hdl : 1721.1/80568 . Archivado del original (PDF) el 22-11-2023 . Recuperado el 28-01-2015 .

[7] 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

[8] Press, William H.; Flannery, Brian P.; Teukolsky, Saul A .; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Cambridge University Press . p . 108. ISBN 978-0-521-88068-8.

[9] Strassen, Volker (1969). "La eliminación gaussiana no es óptima". Numer. Math . 13 (4): 354– 356. doi : 10.1007/BF02165411 . S2CID 121656251 .

[10] Comunicación privada con Probert, Robert L (1976). "Sobre la complejidad aditiva de la multiplicación de matrices" . SIAM Journal on Computing . 5 (2): 187– 203. doi : 10.1137/0205016 .

[11] 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 .

[12] Schwartz, Oded; Vaknin, Noa (2023). "Juego de pebbling y base alternativa para la multiplicación de matrices de alto rendimiento" . SIAM Journal on Scientific Computing . pp. C277– C303. doi : 10.1137/22M1502719 .

[13] 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 .

[14] Beniamini, Gal; Cheng, Nathan; Holtz, Olga ; Karstadt, Elaye; Schwartz, Oded (2020). "Esparcificación de los operadores de algoritmos rápidos de multiplicación de matrices". arXiv : 2008.03759 [ cs.DS ].

[coppersmith-15] 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

[16] Iliopoulos, Costas S. (1989), "Límites de complejidad en el peor de los casos para algoritmos que computan 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 del original (PDF) el 5 de marzo de 2014 , recuperado el 16 de enero de 2015. El algoritmo de 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-17] 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 de tiempo sea evidente.

[18] Laderman, Julian; Pan, Victor; Sha, Xuan-He (1992), "Sobre algoritmos prácticos para la multiplicación acelerada de matrices", Álgebra lineal y sus aplicaciones , 162–164 : 557–588 , doi : 10.1016/0024-3795(92)90393-O

[19] "Descubriendo nuevos algoritmos con AlphaTensor" . www.deepmind.com . 5 de octubre de 2022. Consultado el 1 de noviembre de 2022 .

[alphatensor-20] 1 2 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. Bibcode : 2022Natur.610...47F . doi : 10.1038/s41586-022-05172-4 . ISSN 1476-4687 . PMC 9534758 . PMID 36198780 .

[21] Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "Flip Graphs for Matrix Multiplication". arXiv : 2212.01175 [ cs.SC ].

[22] 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 .

[cilk-23] 1 2 Randall, Keith H. (1998). Cilk: Computación multihilo eficiente (PDF) (Ph.D.). Instituto Tecnológico de Massachusetts. pp. 54– 57. hdl : 1721.1/47519 . Archivado del original (PDF) el 06-11-2020 . Recuperado el 16-01-2015 .

[24] Cannon, Lynn Elliot (14 de julio de 1969). Una computadora celular para implementar el algoritmo del filtro de Kalman (Tesis doctoral). Universidad Estatal de Montana.

[25] Hong, JW; Kung, HT (1981). "Complejidad de E/S: El juego de la piedra roja y azul" ( 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) del original el 15 de diciembre de 2019.

[irony-26] 1 2 3 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (septiembre de 2004). "Límites inferiores de comunicación para la multiplicación de matrices en memoria distribuida". J. Parallel Distrib. Comput . 64 (9): 1017– 26. CiteSeerX 10.1.1.20.7034 . doi : 10.1016/j.jpdc.2004.03.021 .

[Agarwal-27] 1 2 Agarwal, RC; Balle, SM; Gustavson, FG; Joshi, M.; Palkar, P. (septiembre de 1995). "Un enfoque tridimensional para la multiplicación paralela de matrices". IBM J. Res. Dev . 39 (5): 575– 582. CiteSeerX 10.1.1.44.3404 . doi : 10.1147/rd.395.0575 .

[28] Solomonik, Edgar; Demmel, James (2011). «Algoritmos de multiplicación de matrices 2.5D y factorización LU en paralelo con 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.

[29] Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF) . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . Consultado el 12 de julio de 2014 .

[30] 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 .

[31] 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 .

[32] Kak, S. (2014). "Eficiencia de la multiplicación de matrices en la matriz de malla interconectada". arXiv : 1411.3273 [ cs.DC ].

[33] Kak, S (1988). "Computación de matrices multicapa". Information Sciences . 45 (3): 347– 365. CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .

[34] Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981). "Algoritmos paralelos de matrices y grafos". SIAM Journal on Computing . 10 (4): 657– 675. doi : 10.1137/0210049 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

Algoritmo iterativo

Comportamiento de la caché

Algoritmo de divide y vencerás

Matrices no cuadradas

Comportamiento de la caché

Algoritmos subcúbicos

AlphaTensor

Algoritmos paralelos y distribuidos

Paralelismo de memoria compartida

Algoritmos distribuidos y que evitan la comunicación

Algoritmos para mallas

Véase también

Referencias

Lecturas adicionales

Articulos relacionados