Algoritmo de Schönhage-Strassen
# Algoritmo de Schönhage-Strassen

El Algoritmo de Schonhage-Strassen es un algoritmo que 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.

## Historia

El Algoritmo de Schonhage-Strassen fue el primer algoritmo en bajar en tiempo de ejecución de ε=1 , este fue descubierto en 1969 , por Volker Strassen de aquí el nombre del algoritmo. Este algoritmo logró alcanzar ε=0,808 en su tiempo de ejecución .

Desde ese momento muchos matemáticos han intentado hacer a este algoritmo más rápido para su mejora a nivel matemático y para ganar fama . Un gran salto fue obtenido en 1981 por Schönhage que logró ε=0,548 ,; Desde entonces la evolución de este es debida principalmente a Schönhage y a Strassen , ya que con sus investigaciones durante muchos años fueron reduciendo este tiempo y dando un gran paso para las matemáticas.

## Análisis

El método clásico requiere n²(2n-1) operaciones aritméticas para multiplicar dos matrices (n x n). Strassen (1969) publicó un método que solo requería $4.7n^{2.81}$ operaciones. Se ha realizado mucho trabajo para intentar reducir el exponente 2,81, actualmente el mejor tiempo conocido es $O(n^{2.3737})$ operaciones (Virginia Vassilovska Williams). Hay todavía un largo camino por recorrer, pues la mejor cota inferior conocida es $2n^{2}-1$.

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 estándar 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 más 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 más 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).

## Algoritmo

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

## Algoritmo en C

Ya que todos estos procesos son de una complejidad alta , habría que realizarlos en un computador. Por lo tanto habría que hacerlo con un lenguaje de programación como puede ser C, Java, Python... En este caso nos centramos en C++ por lo que el algoritmo es el siguiente:

void strassen ( vector < vector < int > > Y Un ,

unsigned int nextPowerOfTwo ( int n ); void strassenR ( vector < vector < int > > Y Un ,

void suma ( vectorial < vector < int > > Y Un ,

vacío de resta ( vector < vector < int > > Y Un ,

void printMatrix ( vector < vector < int > > matriz , int n ); vacío de lectura ( cadena de nombre de archivo , vector < vector < int > > Y Un , vector < vector < int > > y B );

void ikjalgorithm ( vector < vector < int > > A ,

void strassenR ( vector < vector < int > > Y Un ,

unsigned int nextPowerOfTwo ( int n ) {

void strassen ( vector < vector < int > > Y Un ,

void suma ( vectorial < vector < int > > Y Un ,

vacío de resta ( vector < vector < int > > Y Un ,

int getMatrixSize ( string nombre ) {

vacío de lectura ( cadena de nombre de archivo , vector < vector < int > > Y Un , vector < vector < int > > y B ) {

anulará printMatrix ( vector < vector < int > > matriz , int n ) {

int principal ( int argc , char * argv) {

## Bibliografí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 Archivado el 29 de mayo de 2014 en Wayback Machine.
* https://web.archive.org/web/20100921151810/http://jair.lab.fi.uva.es/~fdelgado/cripto/resumen.pdf
* https://martin-thoma.com/strassen-algorithm-in-python-java-cpp/
* Datos: Q1938391
