En álgebra lineal , el algoritmo de Strassen , llamado así por Volker Strassen , es un algoritmo para la multiplicación de matrices . Es más rápido que el algoritmo estándar de multiplicación de matrices y es útil en la práctica para matrices grandes, pero sería más lento que los algoritmos más rápidos conocidos para matrices extremadamente grandes.
El algoritmo de Strassen funciona para cualquier anillo , como más / multiplicar, pero no todos los semirings , como min-plus o álgebra booleana , donde el algoritmo ingenuo todavía funciona, y la denominada multiplicación de matrices combinatorias .
Historia
Volker Strassen publicó por primera vez este algoritmo en 1969 y demostró que el algoritmo general de multiplicación de matrices n 3 no era óptimo. [1] El algoritmo Strassen es solo un poco mejor que eso, pero su publicación resultó en mucha más investigación sobre la multiplicación de matrices que condujo a enfoques más rápidos, como el algoritmo Coppersmith-Winograd .
Algoritmo
Sean A , B dos matrices cuadradas sobre un anillo R , por ejemplo matrices cuyas entradas son enteros o números reales. Queremos calcular el producto matricial C como
En la siguiente exposición del algoritmo, asumiremos que todas estas matrices tienen tamaños que son potencias de dos (es decir, ), pero esto es solo conceptualmente necesario - si las matrices A , B no son de tipo 2 n × 2 n podemos pensar conceptualmente en llenar las filas y columnas "faltantes" con ceros para obtener matrices con tamaños de potencias de dos - - aunque las implementaciones reales del algoritmo, por supuesto, no harán esto en la práctica.
Luego dividimos A , B y C en matrices de bloques de igual tamaño
con
- .
El algoritmo ingenuo sería:
Con esta construcción no hemos reducido el número de multiplicaciones. Todavía necesitamos 8 multiplicaciones de bloques de matriz para calcular el matrices, el mismo número de multiplicaciones que necesitamos cuando usamos la multiplicación de matrices estándar.
El algoritmo de Strassen define en cambio nuevas matrices:
solo usando 7 multiplicaciones (una para cada ) en lugar de 8. Ahora podemos expresar el en términos de :
Recurrentemente iteramos este proceso de división hasta que las submatrices degeneran en números (elementos del anillo R ). Si, como se mencionó anteriormente, la matriz original tenía un tamaño que no era una potencia de 2, entonces el producto resultante tendrá cero filas y columnas como A y B , y luego se eliminarán en este punto para obtener el (menor ) matriz C que realmente queríamos.
Las implementaciones prácticas del algoritmo de Strassen cambian a métodos estándar de multiplicación de matrices para submatrices lo suficientemente pequeñas, para las cuales esos algoritmos son más eficientes. El punto de cruce particular para el que el algoritmo de Strassen es más eficiente depende de la implementación y el hardware específicos. Los autores anteriores habían estimado que el algoritmo de Strassen es más rápido para matrices con anchos de 32 a 128 para implementaciones optimizadas. [2] Sin embargo, se ha observado que este punto de cruce ha aumentado en los últimos años, y un estudio de 2010 encontró que incluso un solo paso del algoritmo de Strassen a menudo no es beneficioso en las arquitecturas actuales, en comparación con una multiplicación tradicional altamente optimizada, hasta los tamaños de matriz exceden 1000 o más, e incluso para tamaños de matriz de varios miles, el beneficio es típicamente marginal en el mejor de los casos (alrededor del 10% o menos). [3] Un estudio más reciente (2016) observó beneficios para matrices tan pequeñas como 512 y un beneficio de alrededor del 20%. [4]
Complejidad asintótica
El esquema del algoritmo anterior mostró que uno puede salirse con la suya con solo 7, en lugar de las tradicionales 8, multiplicaciones matriz-matriz para los sub-bloques de la matriz. Por otro lado, uno tiene que hacer sumas y restas de bloques, aunque esto no importa por la complejidad general: Sumar matrices de tamaño N / 2 requiere solo ( N / 2) 2 operaciones mientras que la multiplicación es sustancialmente más costosa (tradicionalmente 2 ( N / 2) 3 ) operaciones de suma o multiplicación).
La pregunta entonces es cuántas operaciones se necesitan exactamente para los algoritmos de Strassen, y cómo se compara esto con la multiplicación de matrices estándar que toma aproximadamente 2 N 3 (donde N = 2 n ) operaciones aritméticas, es decir, una complejidad asintótica Θ ( N 3 ) .
El número de sumas y multiplicaciones requeridas en el algoritmo de Strassen se puede calcular de la siguiente manera: sea f ( n ) el número de operaciones para una matriz de 2 n × 2 n . Luego, mediante la aplicación recursiva del algoritmo de Strassen, vemos que f ( n ) = 7 f ( n −1) + ℓ 4 n , para alguna constante ℓ que depende del número de adiciones realizadas en cada aplicación del algoritmo. Por tanto, f ( n ) = (7 + o (1)) n , es decir, la complejidad asintótica para multiplicar matrices de tamaño N = 2 n utilizando el algoritmo de Strassen es
- .
Sin embargo, la reducción en el número de operaciones aritméticas tiene el precio de una estabilidad numérica algo reducida , [5] y el algoritmo también requiere significativamente más memoria en comparación con el algoritmo ingenuo. Ambas matrices iniciales deben tener sus dimensiones expandidas a la siguiente potencia de 2, lo que resulta en almacenar hasta cuatro veces más elementos, y las siete matrices auxiliares contienen cada una una cuarta parte de los elementos en las expandidas.
El algoritmo de Strassen debe compararse con la forma "ingenua" de hacer la multiplicación de matrices que requeriría 8 en lugar de 7 multiplicaciones de subbloques. Esto entonces daría lugar a la complejidad que uno espera del enfoque estándar:
- .
La comparación de estos dos algoritmos muestra que , asintóticamente , el algoritmo de Strassen es más rápido: existe un umbral de tamaño N de modo que las matrices que son más grandes se multiplican de manera más eficiente con el algoritmo de Strassen que con la forma "tradicional". Sin embargo, el enunciado asintótico no implica que el algoritmo de Strassen sea siempre más rápido incluso para matrices pequeñas y, en la práctica, este no es el caso: para matrices pequeñas, el costo de las adiciones adicionales de bloques de matriz supera los ahorros en el número de matrices. multiplicaciones. También hay otros factores no capturados por el análisis anterior, como la diferencia de costo en el hardware actual entre cargar datos de la memoria en procesadores versus el costo de realizar operaciones con estos datos. Como consecuencia de este tipo de consideraciones, el algoritmo de Strassen generalmente solo se usa en matrices "grandes". Este tipo de efecto es aún más pronunciado con algoritmos alternativos como el de Coppersmith y Winograd : aunque asintóticamente incluso más rápido, el umbral del punto de cruce N es tan grande que el algoritmo no se usa generalmente en matrices que uno encuentra en la práctica.
Complejidad de rango o bilineal
La complejidad bilineal o rango de un mapa bilineal es un concepto importante en la complejidad asintótica de la multiplicación de matrices. El rango de un mapa bilinealsobre un campo F se define como (algo así como un abuso de notación )
En otras palabras, el rango de un mapa bilineal es la longitud de su cálculo bilineal más corto. [6] La existencia del algoritmo de Strassen muestra que el rango de la multiplicación de matrices 2 × 2 no es más de siete. Para ver esto, expresemos este algoritmo (junto con el algoritmo estándar) como un cálculo bilineal. En el caso de matrices, los espacios duales A * y B * consisten en mapas en el campo F inducidos por un producto escalar de doble punto (es decir, en este caso la suma de todas las entradas de un producto Hadamard ).
Algoritmo estándar | Algoritmo de Strassen | ||||||
I | f yo ( a ) | g yo ( b ) | w yo | f yo ( a ) | g yo ( b ) | w yo | |
1 | |||||||
2 | |||||||
3 | |||||||
4 | |||||||
5 | |||||||
6 | |||||||
7 | |||||||
8 | |||||||
Se puede demostrar que el número total de multiplicaciones elementales L requeridas para la multiplicación de matrices está estrechamente vinculado asintóticamente al rango R , es decir, o más específicamente, dado que las constantes son conocidas, Una propiedad útil del rango es que es submultiplicativo para los productos tensoriales , y esto permite mostrar que la multiplicación de matrices 2 n × 2 n × 2 n se puede lograr con no más de 7 n multiplicaciones elementales para cualquier n . (Este producto tensorial de n pliegues del mapa de multiplicación de matrices 2 × 2 × 2 consigo mismo, una potencia tensorial n- ésima, se realiza mediante el paso recursivo en el algoritmo que se muestra).
Comportamiento de la caché
El algoritmo de Strassen no tiene en cuenta la caché . El análisis de su algoritmo de comportamiento de caché ha demostrado que incurre en
fallos de caché durante su ejecución, asumiendo un caché idealizado de tamaño M (es decir, conlíneas de longitud b ). [7] : 13
Consideraciones de implementación
La descripción anterior establece que las matrices son cuadradas y el tamaño es una potencia de dos, y que se debe usar relleno si es necesario. Esta restricción permite que las matrices se dividan por la mitad, de forma recursiva, hasta que se alcance el límite de multiplicación escalar. La restricción simplifica la explicación y el análisis de la complejidad, pero en realidad no es necesaria; [8] y, de hecho, rellenar la matriz como se describe aumentará el tiempo de cálculo y puede eliminar fácilmente los ahorros de tiempo bastante estrechos obtenidos al utilizar el método en primer lugar.
Una buena implementación observará lo siguiente:
- No es necesario ni deseable utilizar el algoritmo de Strassen hasta el límite de los escalares. En comparación con la multiplicación de matrices convencional, el algoritmo agrega una considerablecarga de trabajo en sumas / restas; por lo que por debajo de cierto tamaño, será mejor utilizar la multiplicación convencional. Así, por ejemplo, un 1600x1600 no necesita rellenarse a 2048x2048, ya que podría subdividirse en matrices de 25x25 y luego se puede utilizar la multiplicación convencional en ese nivel.
- De hecho, el método se puede aplicar a matrices cuadradas de cualquier dimensión. [3] Si la dimensión es par, se dividen por la mitad como se describe. Si la dimensión es impar, primero se aplica el relleno de ceros por una fila y una columna. Dicho relleno se puede aplicar sobre la marcha y de manera perezosa, y las filas y columnas adicionales se descartan a medida que se forma el resultado. Por ejemplo, suponga que las matrices son 199x199. Se pueden dividir para que la parte superior izquierda sea 100x100 y la inferior derecha 99x99. Donde sea que las operaciones lo requieran, las dimensiones de 99 se rellenan con ceros a 100 primero. Tenga en cuenta, por ejemplo, que el productosolo se usa en la fila inferior de la salida, por lo que solo se requiere que tenga 99 filas de altura; y así el factor izquierdoutilizado para generarlo sólo necesita tener 99 filas de altura; en consecuencia, no es necesario rellenar esa suma a 100 filas; solo es necesario acolchar a 100 columnas para que coincida .
Además, no es necesario que las matrices sean cuadradas. Las matrices no cuadradas se pueden dividir por la mitad utilizando los mismos métodos, lo que produce matrices no cuadradas más pequeñas. Si las matrices son lo suficientemente no cuadradas, valdrá la pena reducir la operación inicial a productos más cuadrados, utilizando métodos simples que son esencialmente, por ejemplo:
- Un producto de tamaño [2 N x N ] * [ N x 10 N ] se puede hacer como 20 operaciones separadas [ N x N ] * [ N x N ], dispuestas para formar el resultado;
- Un producto de tamaño [ N x 10 N ] * [10 N x N ] se puede hacer como 10 operaciones separadas [ N x N ] * [ N x N ], sumadas para formar el resultado.
Estas técnicas harán que la implementación sea más complicada, en comparación con simplemente rellenar un cuadrado de potencia de dos; sin embargo, es una suposición razonable que cualquiera que emprenda una implementación de Strassen, en lugar de una multiplicación convencional, otorgará una mayor prioridad a la eficiencia computacional que a la simplicidad de la implementación.
En la práctica, el algoritmo de Strassen se puede implementar para lograr un mejor rendimiento que la multiplicación convencional incluso para matrices pequeñas, para matrices que no son del todo cuadradas y sin requerir espacio de trabajo más allá de los búferes que ya son necesarios para una multiplicación convencional de alto rendimiento. [4]
Ver también
- Complejidad computacional de operaciones matemáticas
- Eliminación Gauss-Jordan
- Algoritmo de calderero-Winograd
- Representación matricial de orden Z
- Algoritmo de Karatsuba , para multiplicar números enteros de n dígitos en en lugar de en hora
- Algoritmo de Toom-Cook , una generalización más rápida del algoritmo de Karatsuba que permite la descomposición recursiva de divide y vencerás en más de 2 bloques a la vez
- El algoritmo de multiplicación compleja de Gauss multiplica dos números complejos usando 3 multiplicaciones reales en lugar de 4
Referencias
- ^ Strassen, Volker (1969). "La eliminación gaussiana no es óptima". Numer. Matemáticas . 13 (4). doi : 10.1007 / BF02165411 . S2CID 121656251 . Parámetro desconocido
|[[]]=
ignorado ( ayuda ) - ^ Skiena, Steven S. (1998), "§8.2.3 Multiplicación de matrices", The Algorithm Design Manual , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-94860-7.
- ^ a b D'Alberto, Paolo; Nicolau, Alexandru (2005). Uso de la recursividad para impulsar el rendimiento de ATLAS (PDF) . Sexto Int'l Symp. en Computación de Alto Rendimiento.
- ^ a b Huang, Jianyu; Smith, Tyler; Henry, Greg; van de Geijn, Robert (2016). Algoritmo de Strassen recargado . Congreso Internacional de Computación, Redes, Almacenamiento y Análisis de Alto Rendimiento (SC'16).
- ^ Webb, Miller (1975). "Complejidad computacional y estabilidad numérica". SIAM J. Comput . 4 (2): 97–107. doi : 10.1137 / 0204009 .
- ^ Burgisser; Clausen; Shokrollahi (1997). Teoría de la complejidad algebraica . Springer-Verlag. ISBN 3-540-60582-7.
- ^ Frigo, M .; Leiserson, CE ; Prokop, H .; Ramachandran, S. (1999). Algoritmos ajenos a la caché (PDF) . Proc. IEEE Symp. sobre Fundamentos de las Ciencias de la Computación (FOCS). págs. 285-297.
- ^ Higham, Nicholas J. (1990). "Explotación de la multiplicación rápida de matrices dentro del nivel 3 BLAS" (PDF) . Transacciones ACM en software matemático . 16 (4): 352–368. doi : 10.1145 / 98267.98290 . hdl : 1813/6900 . S2CID 5715053 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capítulo 28: Sección 28.2: Algoritmo de Strassen para la multiplicación de matrices, págs. 735–741.
enlaces externos
- Weisstein, Eric W. "Fórmulas de Strassen" . MathWorld .(también incluye fórmulas para una rápida inversión de matrices )
- Tyler J. Earnest, algoritmo de Strassen en el motor de banda ancha celular