Algoritme de Schönhage-Strassen

L'Algoritme de Schonhage-Strassen és un algoritme que consistix en la multiplicació de matrius. És asintóticamente més ràpit que l'algoritme de multiplicació de matrius estàndar, pero més llent que l'algoritme més ràpit conegut, i és útil en la pràctica per a matrius grans.

Història

L'Algoritme de Schonhage-Strassen va ser el primer algoritme en baixar en temps d'eixecució de ε=1 , est va ser descobert en 1969 , per Volker Strassen d'ací el nom de l'algoritme. Este algoritme va conseguir alcançar ε=0,808 en el seu temps d'eixecució .

Des d'eixe moment molts matemàtics han intentat fer a este algoritme més ràpit per a la seua millora a nivell matemàtic i per a guanyar fama . Un gran bot va ser obtingut en 1981 per Schönhage que va conseguir ε=0,548 ,; Des de llavors l'evolució d'est és deguda principalment a Schönhage i a Strassen , ya que en les seues investigacions durant molts anys varen ser reduint este temps i donant un gran pas per a les matemàtiques.

Anàlisis

El método clàssic requerix n²(2n-1) operacions aritmètiques per a multiplicar dos matrius (n x n). Strassen (1969) va publicar un método que solament requeria $4.7 n^{2.81}$ operacions. S'ha realisat molt treball per a intentar reduir l'exponent 2,81, actualment el millor temps conegut és $O (n^{2.3737})$ operacions (Virginia Vassilovska Williams). Hi ha encara un llarc camí per recórrer, puix la millor cota inferior coneguda és $2 n^{2} - 1$ .

En lo que és la multiplicació és una de les operacions que devem repetir vàries voltes en sancers grans, per lo que no està de més comprovar que la multiplicació pel método estàndar de dos sancers binarios de llongituts k i precisa un màxim k' suma d'un bit(Operacions bit), per lo tant el producte de dos número entero en com a molt r sifres decimals requerix a lo més log² r operacions. És dir, és d'orde O(log² r) i per lo tant és una operació eficient. Actualment hi ha algoritmes de multiplicació més ràpits, el més conegut és el método de Karatsuba (la descripció del qual és completament accessible) que permet multiplicar dos sancers de llongitut binaria menor o igual que k en O(k¹·59) operacions bit. El método més ràpit es deu a Schonhage i Strassen i la seua complexitat temporal és O(k log log log k).

Bibliografia

https://martin-thoma.com/strassen-algorithm-in-python-java-cpp/

Este artícul conté una traducció derivada de «Algoritmo de Schönhage-Strassen» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.