Algoritmo de Strassen para la multiplicación de matrices

Question

¿Puede alguien explicar el algoritmo de strassen para la multiplicación de matrices de una manera intuitiva? He pasado (bueno, intenté revisar) la explicación en el libro y la wiki, pero no está haciendo clic arriba. Cualquier enlace en la web que use una gran cantidad de inglés en lugar de la notación formal, etc. sería útil, también. ¿Hay alguna analogía que pueda ayudarme a construir este algoritmo desde cero sin tener que memorizarlo?

Answer 1

Echa un vistazo rápido a la Wikipedia y me parece que este algoritmo es una ligera reducción en el número de multiplicaciones requeridas al reorganizar las ecuaciones.

Aquí hay una analogía. ¿Cuántas multiplicaciones en x*x + 5*x + 6? Dos, ¿verdad? ¿Cuántas multiplicaciones en (x+2)(x+3)? Uno, ¿verdad? ¡Pero son la misma expresión!

Nota, no espero que esto proporcione una comprensión profunda del algoritmo, solo una forma intuitiva en la que puede comprender cómo el algoritmo puede posiblemente conducir a una mejora en la complejidad del cálculo.

Answer 2

En mi opinión hay 3 ideas que usted necesita para obtener:

1. Se puede dividir una matriz en bloques y operar en la matriz resultante de los bloques que lo haría en una matriz de números. En particular, puede multiplicar dos matrices de bloques (por supuesto, siempre que el número de filas de bloques en una coincida con el número de columnas de bloques en la otra) y obtenga el mismo resultado que cuando multiplica las matrices originales de números.

2. Los bloques necesarios para expresar el resultado de la multiplicación de la matriz de bloques 2x2 tienen suficientes factores comunes para permitir su computación en menos multiplicaciones de lo que implica la fórmula original. Este es el truco descrito en Tony's answer.

3. Recursividad.

Algoritmo de Strassen es solo una aplicación de las anteriores. Para comprender el análisis de su complejidad, debe leer "Concrete Mathematics" por Ronald Graham, Donald Knuth y Oren Patashnik o un libro similar.

Answer 3

Considere la multiplicación de dos matrices 2x2, como sigue:

A B * E F = AE+BG AF+BH 
C D G H CE+DG CF+DH 

La manera obvia para calcular el lado derecho es sólo para hacer los 8 multiplica y 4 adiciones. Pero imagine que las multiplicaciones son mucho más costosas que las adiciones, por lo que queremos reducir el número de multiplicaciones si es posible. Strassen usa un truco para calcular el lado derecho con una multiplicación menos y muchas más adiciones (y algunas restas).

Éstos son los 7 multiplica:

M1 = (A + D) * (E + H) = AE + AH + DE + DH 
M2 = (A + B) * H = AH + BH 
M3 = (C + D) * E = CE + DE 
M4 = A * (F - H) = AF - AH 
M5 = D * (G - E) = DG - DE 
M6 = (C - A) * (E + F) = CE + CF - AE - AF 
M7 = (B - D) * (G + H) = BG + BH - DG - DH 

Así que para calcular AE + BG, comenzar con M1 + M7 (que nosotros los términos AE y BG pone), a continuación, añadir/restar algunos de los otros Sra hasta AE + BG es todo lo que nos queda. Milagrosamente, las M se eligen para que M1 + M7-M2 + M5 funcione. Lo mismo con los otros 3 resultados requeridos.

Ahora se da cuenta de que esto no funciona solo para matrices de 2x2, sino para matrices de cualquier tamaño (pares) donde las A..H son submatrices.