Algoritmo de Strassen

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de noviembre de 2021; las comprobaciones requieren 20 ediciones .

El algoritmo de Strassen está diseñado para la multiplicación rápida de matrices . Fue desarrollado por Volker Strassen en 1969 y es una generalización del método de multiplicación de matrices de Karatsuba .

A diferencia del algoritmo de multiplicación de matrices tradicional (según la fórmula ) que se ejecuta en el tiempo , el algoritmo de Strassen multiplica las matrices en el tiempo , lo que proporciona una ganancia en matrices densas grandes. ${\displaystyle c_{ij}=\sum a_{ik}b_{kj))$ $\Theta (n^{{\log _{2}8)))=\Theta (n^{3})$ $\Theta (n^{{\log _{2}7)))=O(n^{{2.81)))$

A pesar de que el algoritmo de Strassen no es asintóticamente el más rápido de los algoritmos de multiplicación de matrices rápidas existentes, es más fácil de programar y más eficiente cuando se multiplican matrices relativamente pequeñas, por lo que es el más utilizado en la práctica.

Descripción del algoritmo

Si sumamos las mismas filas y columnas cero a las matrices , su producto se vuelve igual a la matriz con las mismas filas y columnas agregadas. Por lo tanto, solo se pueden considerar matrices de tamaño , y otros casos se pueden reducir a esto agregando ceros, que solo pueden duplicarse. $A$ $B$ $AB$ ${\displaystyle n=2^{k},\ k\in {\mathbb {N} ))$ $norte$

Sean matrices de tamaño . Se pueden representar como matrices de bloque de tamaño de -matrices: $A,B$ ${\ estilo de visualización 2^{k}\veces 2^{k))$ ${\ estilo de visualización (2 \ veces 2)}$ ${\ estilo de visualización (2 ^ {k-1} \ veces 2 ^ {k-1})}$

A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix)),\quad B={\begin{pmatrix}B_{11} &B_{12}\\B_{21}&B_{22}\end{matrix}}

Por el principio de la multiplicación de bloques , una matriz se expresa en términos de su producto $AB$

AB={\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{matrix}}\ ,

donde del lado derecho hay ocho multiplicaciones de matrices de tamaño . Dado que las matrices forman un anillo , entonces cualquier algoritmo para multiplicar matrices que use solo sumas, restas y multiplicaciones es adecuado para calcular el lado derecho. Strassen propuso el siguiente algoritmo con siete multiplicaciones: ${\ estilo de visualización 2^{k-1}\veces 2^{k-1}}$ ${\ estilo de visualización (2 \ veces 2)}$

{\begin{alineado}D&=(A_{11}+A_{22})(B_{11}+B_{22});\\D_{1}&=(A_{12}-A_{ 22})(B_{21}+B_{22});\\D_{2}&=(A_{21}-A_{11})(B_{11}+B_{12});\\H_{ 1}&=(A_{11}+A_{12})B_{22};\\H_{2}&=(A_{21}+A_{22})B_{11};\\V_{1} &=A_{22}(B_{21}-B_{11});\\V_{2}&=A_{11}(B_{12}-B_{22});\\\end{alineado}}

{\begin{alineado}AB&={\begin{pmatrix}D&0\\0&D\end{pmatrix}}+{\begin{pmatrix}D_{1}&0\\0&D_{2}\end{pmatrix} }+{\begin{pmatrix}-H_{1}&H_{1}\\H_{2}&-H_{2}\end{pmatrix}}+{\begin{pmatrix}V_{1}&V_{2} \\V_{1}&V_{2}\end{pmatrix}}\\&={\begin{pmatrix}D+D_{1}+V_{1}-H_{1}&V_{2}+H_{1 }\\V_{1}+H_{2}&D+D_{2}+V_{2}-H_{2}\end{pmatrix}}\ .\end{alineado}}

Cada multiplicación se puede hacer recursivamente usando el mismo procedimiento, y la suma se puede hacer de manera trivial agregando elementos. Luego, el tiempo de ejecución del algoritmo se estima a través de la relación recursiva : ${\ estilo de visualización (2^{k-1})^{2}}$ $Tennesse)$

T(n)=7T(n/2)+O(n^{2})=O(n^{\log _{2}7})\ .

Ejemplo de implementación

A continuación se muestra un ejemplo de implementación del algoritmo en Python usando la biblioteca NumPy para tomar submatrices rápidamente. La función principal es strassen_mul. Se supone que todas las matrices son cuadradas, representadas por type numpy.array, y su tamaño es una potencia de 2.

Para tamaños de matriz pequeños, la multiplicación directa es más rápida que el algoritmo de Strassen debido a la gran cantidad de adiciones en este último. El límite de tales tamaños depende de la proporción del tiempo de adición y multiplicación de elementos y, por lo tanto, puede variar según el entorno del hardware. En el código, la constante es responsable de su propósito TRIVIAL_MULTIPLICATION_BOUND.

desde itertools importar producto importar numpy como np def split_to_2x2_blocks ( matriz ): lista de retorno ( mapa ( fila lambda : np . hsplit ( fila , 2 ), np . vsplit ( matriz , 2 ) )) def strassen_mul_2x2 ( lb , rb ): d = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 1 ][ 1 ], rb [ 0 ][ 0 ] + rb [ 1 ][ 1 ]) d_1 = strassen_mul ( lb [ 0 ][ 1 ] - lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] + rb [ 1 ][ 1 ]) d_2 = strassen_mul ( lb [ 1 ][ 0 ] - lb [ 0 ][ 0 ], rb [ 0 ][ 0 ] + rb [ 0 ][ 1 ]) izquierda = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) derecha = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) arriba = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) abajo = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) return [[ d + d_1 + izquierda - arriba , derecha + arriba ], [ izquierda + abajo , d + d_2 + derecha - abajo ]] def trivial_mul ( izquierda , derecha ): altura , tamaño medio = izquierda . forma mid_size , right = right . formas resultado = np . ceros (( alto , ancho )) para fila , columna , medio en producto ( * mapa ( rango , [ alto , ancho , tamaño medio ])): resultado [ fila ][ columna ] += izquierda [ fila ][ medio ] * derecha [ medio ][ columna ] resultado devuelto TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( izquierda , derecha ): afirmar ( izquierda . forma == derecha . forma ) afirmar ( izquierda . forma [ 0 ] == izquierda . forma [ 1 ]) si queda _ forma [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : devuelve trivial_mul ( izquierda , derecha ) afirmar ( izquierda . forma [ 0 ] % 2 == 0 ) devuelve np . bloque ( strassen_mul_2x2 ( * mapa ( split_to_2x2_blocks , [ izquierda , derecha ]))) )

Mayor desarrollo

Strassen fue el primero en mostrar la posibilidad de multiplicar matrices de una forma más eficiente que la estándar. Después de la publicación de su trabajo en 1969, comenzó una búsqueda activa de un algoritmo más rápido. El algoritmo más asintóticamente rápido en la actualidad es el algoritmo Coppersmith-Winograd , que permite multiplicar matrices en operaciones [1] , propuesto en 1987 y mejorado en 2011 al nivel [1] . Este algoritmo no tiene interés práctico debido a la constante astronómicamente grande en la estimación de la complejidad aritmética. La cuestión de la tasa de limitación asintótica de la multiplicación de matrices no se ha resuelto. Existe la conjetura de Strassen de que para lo suficientemente grande existe un algoritmo para multiplicar dos matrices de tamaño en operaciones, donde un número positivo preasignado es arbitrariamente pequeño. Esta conjetura tiene un interés puramente teórico, ya que el tamaño de las matrices, para el cual es realmente pequeño, es aparentemente muy grande. ${{\rm {O}}}(n^{{2.376}})$ ${{\rm {O}}}(n^{{2.3727}})$ $norte$ $n\veces n$ ${{\rm {O}}}(n^{{2+\varepsilon}})$ $\varepsilon$ $\varepsilon$

La cuestión de construir el algoritmo práctico más rápido y estable para multiplicar matrices grandes también sigue sin resolverse.

Algoritmo de Winograd-Strassen

Hay una modificación del algoritmo de Strassen que requiere 7 multiplicaciones y 15 sumas (en lugar de 18 para el algoritmo de Strassen normal).

Las matrices se dividen en submatrices de bloque como se muestra arriba. ${\ estilo de visualización A, \, B, \, C}$

Los elementos intermedios se calculan $S_{1},\,\ldots,\,S_{8},\,P_{1},\,\ldots,\,P_{7},\,T_{1},\,T_{ 2}$

{\begin{alineado}S_{1}&=(A_{21}+A_{22});\\S_{2}&=(S_{1}-A_{11});\\S_ {3}&=(A_{11}-A_{21});\\S_{4}&=(A_{12}-S_{2});\\S_{5}&=(B_{12} -B_{11});\\S_{6}&=(B_{22}-S_{5});\\S_{7}&=(B_{22}-B_{12});\\S_ {8}&=(S_{6}-B_{21});\\P_{1}&=S_{2}S_{6};\\P_{2}&=A_{11}B_{11} ;\\P_{3}&=A_{12}B_{21};\\P_{4}&=S_{3}S_{7};\\P_{5}&=S_{1}S_{5 };\\P_{6}&=S_{4}B_{22};\\P_{7}&=A_{22}S_{8};\\T_{1}&=P_{1}+P_ {2};\\T_{2}&=T_{1}+P_{4}.\end{alineado}}

Los elementos de la matriz se calculan de la siguiente manera: $C$

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}}={\begin{pmatrix}P_{2}+P_{3}&T_ {1}+P_{5}+P_{6}\\T_{2}-P_{7}&T_{2}+P_{5}\end{matrix}}.

El estado actual de la cuestión

El algoritmo de Strassen es un algoritmo bilineal, sus coeficientes son las raíces del sistema cúbico de las ecuaciones de Brent . [2] Para la clase de algoritmos exactos <2x2x2> este es un problema mínimo, cuya solución permite reducir el número de multiplicaciones en el anillo de elementos de la matriz. [3] [4] El problema de encontrar nuevos algoritmos es que el sistema Brent es no lineal, el número de incógnitas y ecuaciones (estos números no coinciden) crece rápidamente con el tamaño de las matrices, y solo soluciones con un gran Se requiere una cantidad de ceros.

En 2013, tras superar parcialmente estos problemas, fue posible encontrar el primer algoritmo bilineal práctico para la multiplicación de matrices, que es asintóticamente más rápido que el algoritmo de Strassen. [5] Algoritmo de Smirnov <3x3x6; 40> multiplica una matriz de 3X3 por una matriz de 3x6 utilizando 40 multiplicaciones en lugar de 54. Su complejidad asintótica es . (La multiplicación de tensor del algoritmo por sí mismo con un cambio cíclico de argumentos conduce a un algoritmo para matrices cuadradas <54x54x54; 64000> con la misma complejidad). Para una aceleración real de la multiplicación, se requiere una optimización significativa: la eliminación de muchos cálculos duplicados en formas lineales. $O(n^{\log _{54}64000})=O(n^{2.78})$

Hoy (2022), este es asintóticamente el algoritmo bilineal práctico más rápido para un campo arbitrario de elementos de matriz.

El 5 de octubre de 2022, DeepMind, utilizando el algoritmo de red neuronal AlphaZero, encontró varios algoritmos nuevos para multiplicar matrices de varias dimensiones. Sin embargo, su velocidad para un campo arbitrario está lejos de la velocidad de los mejores algoritmos conocidos. Entonces, para matrices de 4X4, el algoritmo de Strassen requiere 49 multiplicaciones, y AlphaTensor encontró un algoritmo que requiere 47 multiplicaciones, pero solo funciona para el campo . [6] [7] $\mathbb{Z} _{2}$

Notas

↑ 1 2 Los matemáticos han superado la barrera de Coppersmith-Winograd . lenta.ru (12 de diciembre de 2011). Fecha de acceso: 12 de diciembre de 2011. Archivado desde el original el 5 de febrero de 2012. (indefinido)
↑ RPBrent. Algoritmos para multiplicaciones de matrices// Dpto. Informática Informe CS 157, Universidad de Stanford, 1970.
↑ Complejidad de la multiplicación de matrices. Reseña//Cibernético. recopilación. 1988. Edición. 25. Art. 139-236.
↑ Landsberg JM Geometría y la complejidad de la multiplicación de matrices // Bol. amer Matemáticas. soc. 2008. V.45. pág. 247-284.
↑ A. V. Smirnov, "Sobre la complejidad bilineal y algoritmos prácticos para la multiplicación de matrices", Zh. Vychisl. Matemáticas. y estera Fiz., 53:12 (2013), 1970–1984; computar Matemáticas. Matemáticas. Phys., 53:12 (2013), 1781–1795
↑ Descubriendo nuevos algoritmos con AlphaTensor . www.menteprofunda.com . Consultado: 6 de octubre de 2022.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Descubriendo algoritmos de multiplicación de matrices más rápidos con aprendizaje por refuerzo // Naturaleza . — 2022-10. — vol. 610 , edición. 7930 . — págs. 47–53 . — ISSN 1476-4687 . -doi : 10.1038/ s41586-022-05172-4 .

Literatura

Strassen V. La eliminación gaussiana no es óptima // Numer . Matemáticas / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, edición. 4.- Pág. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
Levitin A. V. Capítulo 4. Método de descomposición: Multiplicación de números enteros grandes y el algoritmo de multiplicación de matrices de Strassen // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 189-195. — 576 pág. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capítulo 28. Trabajando con Matrices // Algoritmos: Construcción y Análisis = Introducción a los Algoritmos. — 2ª edición. - M .: "Williams" , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .