…and the Oscar for the result of the year goes to… (2011 ed.)

…Andrew Stothers e Virginia Vassilevska Williams per il nuovo upper bound sul prodotto tra matrici n*n1.

Il risultato conquista il titolo di algoritmo2 più veloce per eseguire il prodotto tra matrici n*n, che dal 1987 era detenuto dall’algoritmo di WinogradCoppersmith.

Indichiamo con O(n^w) la complessità del prodotto tra matrici quadrate di dimensione n. I principali risultati sul tale problema sono sintetizzati dalla seguente timeline:

  1. Il classico prodotto riga x colonna viene eseguito con w = 3.
  2. 1969. Strassen pubblica un algoritmo Divide&Conquer per il quale w = 2.808. [paper]
  3. 1981. Winograd e Coppersmith (CW) con il loro algoritmo superano quota 2.5 e riescono ad ottenere w < 2.496.
  4. 1987. CW raffinano il loro algoritmo e ottengono il risultato che resterà imbattuto fino al 2011. w < 2.376. [paper]
  5. 2010-2011. Andrew Stothers nel giugno 2010 e Virginia Vassilevska Williams nel novembre del 2011 ottengono separatamente il risultato w < 2.3727.[phd Thesis of  Stothers][VW paper]

Come, probabilmente, sarà noto sia l’algoritmo di CW che quello di SW, sono difficilmente implementabili e sebbene teoricamente migliori rispetto all’algoritmo classico e a quello di Strassen, all’atto pratico hanno attualmente scarsa applicabilità.

A chi andrà l’Oscar “for the result of the year in TCS” nel 2012?

[1] Matrice: una matrice è tabella di elementi ordinati per riga e colonna.

Struttura Matrice (Fonte: Wikipedia)

 

 

 

 

 

 

[2] Algoritmo: il termine algoritmo deriva dal nome del matematico persiano Muhammad ibn Musa al-Khwarizmi, che per primo ne introdusse il concetto. Citando Donald E. Knuth un algoritmo è una sequenza di passi da compiere, partendo da un insieme di dati di input per generare un risultato in output: finita (rispetto al numero di passi), limitata (rispetto al tempo di esecuzione) e non ambigua.

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: