Strassen

[Escribir el nombre de la compañía]
Algoritmo de Strassen
Multiplicación de matrices

[Escribir el nombre del autor]
27/08/2012




Algoritmo de Strassen
Volker Strassen publicó elalgoritmo 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, peroutiliza 155 sumas binarias en lugar de las 18 del algoritmo de Strassen), publicado en 2000 .
El el algoritmo de Strassen el cual consiste en dividir las matrices en cuatro partes iguales, y resolver elproducto original en base a operaciones como la suma ,resta y multiplicación sobre las partes
El algoritmo de Srassen tiene el siguiente tiempo de ejecución:

T(n) = {θ(n ^3) si n es pequeño y7T(n/2)+ θ (n ^2) si no lo es.

Esto resolviendo esta recurrencia con el teorema maestro resulta T(n) € θ(n^log7), si el tamaño n de la matriz es potencia de 2.Para las matrices cuyos n no sonpotencia de 2, es necesario completarlas con 0’s hasta llegar a una potencia de 2.

Ventajas
La solución tradicional en matrices 2x2, requiere de: 8 multiplicaciones y 4 sumas…
La solución de Strassenrequiere de:7 multiplicaciones y 18 sumas/restas. Aparentemente, no es significativo el beneficio. Pero ahorrar una multiplicación de matrices en el algoritmo de Strassen, a costa de más sumas orestas de matrices, tiene repercusiones significativas.
Además de que para lograr esto opta por resolverlo mediante divide y vencerás esto quiere decir que todos los problemas se dividen en subproblemas,donde los subproblemas en la medida de lo posible deben ser del mismo tamaño.
Codigo en Java del Algoritmo
public class Strassen {



public static double[][] elevar(double[][] A,...