Algoritmo de Strassen

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 2010 (que utiliza 20 multiplicaciones binarias, pero utiliza 155 sumas binarias en lugar de las 18 del algoritmo de Strassen), publicado en 2000 .

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

${\displaystyle \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

${\displaystyle \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

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

Entonces

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

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

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

${\displaystyle \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

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

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

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

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

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

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

${\displaystyle \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

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

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

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

${\displaystyle \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]

La multiplicación de matrices estándar requiere aproximadamente ${\displaystyle 2N^{3}}$ (donde ${\displaystyle N=2^{n}}$)operaciones aritméticas (sumas y multiplicaciones); la complejidad asintótica es ${\displaystyle O(N^{3})}$.

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

${\displaystyle 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.

• 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.

• Weisstein, Eric W. «Fórmulas para multiplicación de matrices más rápida e inversión». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
• Tyler J. Earnest, Algoritmo de Strassen en el microprocesador Cell