Algoritmo de Strassen

En la disciplina matemática del álgebra lineal, el algoritmo de Strassen, llamado así por Volker Strassen, es un algoritmo usado para la multiplicación de matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes.

Historia

Volker Strassen publicó el algoritmo de Strassen en 1969. Pese a que su algoritmo es sólo ligeramente más rápido que el algoritmo estándar para la multiplicación de matrices, fue el primero en señalar que el enfoque estándar no es óptimo. Su artículo comenzó la búsqueda de algoritmos aún más rápidos, como el complejo algoritmo de Coppersmith–Winograd de Shmuel Winograd en 1910 (que utiliza 20 multiplicaciones binarias, pero utiliza 155 sumas binarias en lugar de las 18 del algoritmo de Strassen), publicado en 2000 .

Algoritmo

Sean A, B dos matrices cuadradas sobre un anillo R. Queremos calcular la matriz C como producto

$\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in R^{2^n \times 2^n}$

Si las matrices A, B no son de tipo 2ⁿ x 2ⁿ habrá que rellenar lo que falta de filas y columnas con ceros.

Partimos A, B y C en matrices de igual tamaño de bloque

$\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}$

Con

$\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in R^{2^{n-1} \times 2^{n-1}}$

Entonces

$\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}$

$\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}$

Con esta construcción, no hemos reducido el número de multiplicaciones. Todavía tenemos 8 multiplicaciones para calcular la matriz C_{i, j} , que es el mismo número de multiplicaciones que se necesitan cuando se usa el método estándar de multiplicación de matrices.

Ahora viene la parte importante. Definimos las matrices de nuevo

$\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})$

$\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}$

$\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})$

$\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})$

$\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}$

$\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})$

$\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$

que luego se utilizan para expresar C_{i, j} en términos de M_k. Debido a nuestra definición de la M_k podemos eliminar una multiplicación de matrices y reducir el número de multiplicaciones a 7 (una multiplicación por cada M_k) y expresar C_{i, j} como

$\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}$

$\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}$

$\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}$

$\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$

Iteramos n-veces el proceso de división hasta que las submatrices degeneran en números (elementos del anillo R).

Las implementaciones prácticas del algoritmo de Strassen, permiten cambiar a métodos estándar de multiplicación de matrices para submatrices lo suficientemente pequeñas, para las cuales son más eficientes. El punto a partir del cual el algoritmo de Strassen es más eficiente depende de la implementación específica y del hardware. Se ha estimado que el algoritmo de Strassen es más rápido para matrices con anchura desde 32 a 128 para implementaciones optimizadas,^[1] y 60.000 o más para implementaciones básicas.^[2]

Análisis numérico

La multiplicación de matrices estándar requiere aproximadamente 2N³ (donde N = 2ⁿ)operaciones aritméticas (sumas y multiplicaciones); la complejidad asintótica es O(N³).

El número de sumas y multiplicaciones requeridas en el algoritmo de Strassen puede ser calculado como sigue: sea f(n) el número de operaciones para una matriz de $2^n \times 2^n$. Entonces por aplicación recursiva del algoritmo de Strassen, vemos que f(n) = 7f(n − 1) + l4ⁿ, para alguna constante l que depende del número de sumas realizadas en cada aplicación del algoritmo. Por lo tanto f(n) = (7 + o(1))ⁿ,esto es, la complejidad asintótica para multiplicar matrices de tamaño N = 2ⁿ usando el algoritmo de Strassen es

$O((7+o(1))^n) = O(N^{\log_{2}7+o(1)}) \approx O(N^{2.807})$.

La reducción en el número de operaciones aritméticas se obtiene a cambio de reducir un tanto la estabilidad numérica.

Referencias

1. ↑ Skiena, Steven S. (1998), «§8.2.3 Multiplicación de matrices», El manual de diseño de algoritmos, Berlín, Nueva York: Springer-Verlag, ISBN 978-0-387-94860-7 .
2. ↑ Kakaradov, Boyko (2004), «Multiplicación de matrices ultra-rápida: Un análisis empirico de algoritmos de vector altamente optimizados», Stanford Undergraduate Research Journal 3: 33–36, http://surj.stanford.edu/2004/pdfs/kakaradov.pdf .

• Strassen, Volker, La eliminación gaussiana no es óptima, Numer. Math. 13, p. 354-356, 1969
• 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 multiplicación de matrices, pp.735–741.

Enlaces externos

• Formulas para multiplicación de matrices más rápida e inversión en MathWorld
• Tyler J. Earnest, Algoritmo de Strassen en el microprocesador Cell