Algoritmo di Strassen per la moltiplicazione di matrici

Question

Qualcuno può spiegare l'algoritmo di strassen per la moltiplicazione di matrici in modo intuitivo? Ho passato (beh, ho cercato di passare attraverso) la spiegazione nel libro e nella wiki, ma non è possibile fare clic su al piano di sopra. Sarebbe utile anche qualsiasi link sul web che usi molto inglese piuttosto che notazioni formali, ecc. Ci sono delle analogie che potrebbero aiutarmi a costruire questo algoritmo da zero senza doverlo memorizzare?

Answer 1

Ho dato una rapida occhiata a Wikipedia e mi sembra che questo algoritmo sia una leggera riduzione del numero di moltiplicazioni richieste riorganizzando le equazioni.

Ecco un'analogia. Quante moltiplicazioni in x*x + 5*x + 6? Due, giusto? Quante moltiplicazioni in (x+2)(x+3)? Uno, giusto? Ma sono la stessa espressione!

Nota, non mi aspetto che questo fornisca una comprensione approfondita dell'algoritmo, solo un modo intuitivo in cui è possibile comprendere in che modo l'algoritmo può portare a un miglioramento della complessità di calcolo.

Answer 2

A mio parere ci sono 3 idee che è necessario per ottenere:

1. È possibile dividere una matrice in blocchi e operare sulla matrice risultante di blocchi come si farebbe su una matrice di numeri. In particolare è possibile moltiplicare due matrici di blocchi di questo tipo (ovviamente fino a quando il numero di righe di blocco in una corrisponde al numero di colonne di blocco nell'altra) e ottenere lo stesso risultato di quando si moltiplicano le matrici di numeri originali.

2. I blocchi necessari per esprimere il risultato della moltiplicazione della matrice di blocchi 2x2 hanno fattori comuni sufficienti per consentire il calcolo in un numero inferiore di moltiplicazioni rispetto alla formula originale. Questo è il trucco descritto in Tony's answer.

3. Ricorsione.

Algoritmo di Strassen è solo un'applicazione di cui sopra. Per comprendere l'analisi della sua complessità, è necessario leggere "Concrete Mathematics" di Ronald Graham, Donald Knuth e Oren Patashnik o un libro simile.

Answer 3

Consideriamo moltiplicazione di due matrici 2x2, come segue:

A B * E F = AE+BG AF+BH 
C D G H CE+DG CF+DH 

Il modo ovvio per calcolare il lato destro è solo per fare le 8 moltiplica e 4 integrazioni. Ma immaginate che i multipli siano molto più costosi delle aggiunte, quindi vogliamo ridurre il numero di moltiplicazioni se possibile. Strassen usa un trucco per calcolare il lato destro con una moltiplicazione in meno e molte più aggiunte (e alcune sottrazioni).

Ecco i 7 moltiplica:

M1 = (A + D) * (E + H) = AE + AH + DE + DH 
M2 = (A + B) * H = AH + BH 
M3 = (C + D) * E = CE + DE 
M4 = A * (F - H) = AF - AH 
M5 = D * (G - E) = DG - DE 
M6 = (C - A) * (E + F) = CE + CF - AE - AF 
M7 = (B - D) * (G + H) = BG + BH - DG - DH 

Quindi, per calcolare AE + BG, iniziare con M1 + M7 (che noi i termini AE e BG ottiene), quindi aggiungere/togliere alcuni degli altri Ms fino AE + BG è tutto ciò che ci rimane. Miracolosamente, le M sono scelte in modo che M1 + M7-M2 + M5 funzioni. Lo stesso con gli altri 3 risultati richiesti.

Ora realizziamo che questo funziona non solo per le matrici 2x2, ma per le matrici di qualsiasi dimensione (anche) in cui le A..H sono sottomatrici.