algorithm - programacion - Algoritmo de Strassen para la multiplicación de matrices

optimizar multiplicacion 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

Considere multiplicar dos matrices de 2x2, de la siguiente manera:

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

La forma obvia de calcular el lado correcto es solo hacer 8 multiplicaciones 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).

Aquí están las 7 multiplicaciones:

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

Entonces, para calcular AE + BG, comience con M1 + M7 (que nos da los términos AE y BG), luego sume / reste algunas de las otras M hasta que AE + BG sea 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 comprenda que esto funciona no solo para matrices de 2x2, sino también para matrices de cualquier tamaño (par) donde las A..H son submatrices.

Answer 2

Eché un vistazo rápido a la Wikipedia y me parece que este algoritmo es una pequeña 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!

Tenga en cuenta que 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 conducir posiblemente a una mejora en la complejidad del cálculo.

Answer 3

En mi opinión, hay 3 ideas que debes obtener:

1. Puede dividir una matriz en bloques y operar en la matriz resultante de bloques como 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 que permiten calcularlos en menos multiplicaciones de lo que implica la fórmula original. Este es el truco descrito en la respuesta de Tony .

3. Recursion

El algoritmo Strassen es solo una aplicación de lo anterior. Para entender el análisis de su complejidad, debe leer " Concrete Mathematics " por Ronald Graham, Donald Knuth y Oren Patashnik o un libro similar.