El Algoritmo de Schonhage-Strassen consiste en 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.
El método clásico requiere n²(2n-1) operaciones aritméticas para multiplicar dos matrices (n x n). Sorprendentemente Strassen (1969) publicó un método que solo requería 4.7n²·8¹ operaciones. Se ha realizado mucho trabajo para intentar reducir el exponente 2.81, actualmente el mejor tiempo conocido es O(n²·496) operaciones (Coppersmith y Wingrad, 1982). Hay todavía un largo camino por recorrer, pues la mejor cota inferior conocida es 2n²-¹.
En lo que es la multiplicación es una de las operaciones que debemos repetir varias veces en enteros grandes, por lo que no está de más comprobar que la multiplicación por el método estandar de dos enteros binarios de longitudes k y precisa un máximo k' suma de un bit(Operaciones bit), por lo tanto el producto de dos números enteros con a lo sumo r cifras decimales requiere a lo mas log² r operaciones. Es decir, es de orden O(log² r) y por lo tanto es una operación eficiente. Actualmente hay algoritmos de multiplicación mas rápidos, el más conocido es el método de Karatsuba (cuya descripción es completamente accesible) que permite multiplicar dos enteros de longitud binaria menor o igual que k en O(k¹·59) operaciones bit. El método más rápido se debe a Schonhage y Strassen y su complejidad temporal es O(k log log log k).
Utilizando el algoritmo de Strassen definimos las siguientes matrices:
M1=(A1.2 - A2,2).(B2,1 + B2,2)
M2=(A1,1 + A2,2).(B1,1 + B2,2)
M3=(A1,1 - A2,1).(B1,1 + B2,1)
M4=(A1,1 + A1,2).B2,2
M5=A1,1 .(B1,2 -B2,2)
M6=A2,2.(B2,1 - B1,1)
M7=(A2,1 + A2,2).B1,1
Biografía: http://www.algoritmia.net/articles.php?id=34
http://es.wikipedia.org/wiki/Algoritmo_de_Strassen
http://decsai.ugr.es/~castro/CA/node5.html
http://jair.lab.fi.uva.es/~fdelgado/cripto/resumen.pdf
El método clásico requiere n²(2n-1) operaciones aritméticas para multiplicar dos matrices (n x n). Sorprendentemente Strassen (1969) publicó un método que solo requería 4.7n²·8¹ operaciones. Se ha realizado mucho trabajo para intentar reducir el exponente 2.81, actualmente el mejor tiempo conocido es O(n²·496) operaciones (Coppersmith y Wingrad, 1982). Hay todavía un largo camino por recorrer, pues la mejor cota inferior conocida es 2n²-¹.
En lo que es la multiplicación es una de las operaciones que debemos repetir varias veces en enteros grandes, por lo que no está de más comprobar que la multiplicación por el método estandar de dos enteros binarios de longitudes k y precisa un máximo k' suma de un bit(Operaciones bit), por lo tanto el producto de dos números enteros con a lo sumo r cifras decimales requiere a lo mas log² r operaciones. Es decir, es de orden O(log² r) y por lo tanto es una operación eficiente. Actualmente hay algoritmos de multiplicación mas rápidos, el más conocido es el método de Karatsuba (cuya descripción es completamente accesible) que permite multiplicar dos enteros de longitud binaria menor o igual que k en O(k¹·59) operaciones bit. El método más rápido se debe a Schonhage y Strassen y su complejidad temporal es O(k log log log k).
Utilizando el algoritmo de Strassen definimos las siguientes matrices:
M1=(A1.2 - A2,2).(B2,1 + B2,2)
M2=(A1,1 + A2,2).(B1,1 + B2,2)
M3=(A1,1 - A2,1).(B1,1 + B2,1)
M4=(A1,1 + A1,2).B2,2
M5=A1,1 .(B1,2 -B2,2)
M6=A2,2.(B2,1 - B1,1)
M7=(A2,1 + A2,2).B1,1
Biografía: http://www.algoritmia.net/articles.php?id=34
http://es.wikipedia.org/wiki/Algoritmo_de_Strassen
http://decsai.ugr.es/~castro/CA/node5.html
http://jair.lab.fi.uva.es/~fdelgado/cripto/resumen.pdf
