Complessità di grande moltiplicazione di matrice [chiusa] - algoritmo, matematica, complessità temporale, moltiplicazione di matrice

Qual è la complessità temporale dell'algoritmo più veloce conosciuto oggi per moltiplicare le grandi matrici?

Che dire della complessità teorica ottimale del tempo che potrebbe essere raggiunta?

risposte:

Questa è un'area di ricerca attiva, quindi questa risposta potrebbe presto non essere aggiornata. :-)

Per quanto ne so, l'algoritmo di moltiplicazione della matrice più veloce attualmente viene eseguito nel tempo O (n^2.373), a causa di un risultato di Virginia Williams. L'algoritmo è in realtà una grande famiglia dialgoritmi che danno luogo a un complesso sistema di equazioni non lineari che danno il tempo complessivo vincolato, e in effetti ci sono persone che stanno lavorando in questo momento cercando di vedere come migliorare il limite trovando soluzioni migliori e migliori per quelle equazioni. Credo che questo algoritmo sia solo di interesse teorico, comunque.

Il Santo Graal della moltiplicazione della matrice sarebbe un O (n²) algoritmo di moltiplicazione della matrice di tempo e se esiste un tale algoritmo è ancora un problema aperto. Questo è il limite teorico, dal momento che una o (n²) L'algoritmo time -time non poteva nemmeno leggere tutte le voci delle matrici per moltiplicare.

Spero che questo ti aiuti!