Il famoso algoritmo di moltiplicazione di matrice di Strassen è un vero piacere per noi, in quanto riduce la complessità del tempo dal tradizionale O (n 3 ) a O (n 2.8 ).
Ma di tutte le risorse che ho attraversato, anche il libro di Cormen e Steven Skienna, chiaramente non dicono come pensava Strassen.
Qual è la motivazione dell'algoritmo di moltiplicazione delle matrici di Strassen? È un incidente fortunato o c'è qualcosa di più profondo?
Oltre a Strassen, nessuno è in grado di dirti come ha fatto Strassen la sua idea. Howeber¹, posso dirti, come potresti averlo trovato formula te stesso, a condizione che ti interessi algebrico teoria della geometria e della rappresentazione. Questo ti dà anche gli strumenti per mostrare che la formula di Strassen è buona come può, o più precisamente, che non esiste una formula che calcola il prodotto di due matrici 2 × 2 che utilizza meno di 7 moltiplicazioni .
Dato che sei interessato alle matrici presumo che tu conosca la linea di base algebra e sarà un po 'sfocato per i dettagli più avanzati.
Innanzitutto sia E l'insieme di tutte le mappe lineari da un piano a a aereo. Questo è fondamentalmente l'insieme di tutte le matrici 2 × 2, ma noi dimentichiamo su un particolare sistema di coordinate, perché, se ci fosse un migliore sistema di coordinate rispetto a quello "di default" di cui potremmo avere interesse utilizzandolo per la moltiplicazione della matrice. Denotiamo anche con E † il doppio spazio di E e di X = P (E⊗E † ⊗E †) lo spazio proiettivo associato al prodotto tensoriale E⊗E † ⊗E † .
Un elemento di X = P (E⊗E † ⊗E †) della forma speciale [c⊗α⊗β] può essere interpretato come un'operazione elementare su matrici, che, in alcuni sistemi di coordinate appropriati, legge un coefficiente di una matrice A e un coefficiente di una matrice B e scrive il prodotto di questi coefficienti in alcune matrici C . Un elemento generale di X è una combinazione di queste operazioni elementari, quindi il prodotto π di due matrici, inteso come una mappa da P (E) × P (E) a P (E), è un punto in X .
La solita formula del prodotto a matrice e la formula di Strassen possono essere espresso come combinazioni di queste operazioni lineari, quindi lasciatemi dire da W₁ l'insieme di queste operazioni elementari [c⊗α⊗β] e lasciatemi descrivere geometricamente le loro combinazioni.
Sia W₂ la varietà di secanti di W₁ in X. Si ottiene prendendo la (chiusura dell'unione) di tutte le linee che attraversano due punti (generici) di W₁ . Possiamo pensare ad esso come del set di tutti combinazioni di due operazioni di elemetary.
Sia W₃ la varietà di piani secanti di W₁ in X. Si ottiene prendendo la (chiusura dell'unione) di tutti gli aerei che attraversano tre punti (generici) di W₁ . Possiamo pensare ad esso come del set di tutti combinazioni di tre operazioni di elemetary.
Allo stesso modo, definiamo varietà secanti per indici maggiori. Nota che queste varietà crescono sempre di più, cioè W₁⊂W₂⊂W₃⊂ ⋯ la classica formula del prodotto a matrice mostra che il prodotto di le matrici è un punto di W₈ . In realtà
PROPOSITION (Strassen) - Il prodotto delle matrici π si trova in W₇.
Per quanto ne so, Strassen non ha messo le cose in questo modo, tuttavia questo è un punto di vista geometrico su questa domanda. Questo punto di vista è molto utile, perché consente anche di dimostrare che la formula di Strassen è il migliore, cioè, che π non giace in W₆ . Metodi geometrici sviluppato qui può anche essere usato per una più ampia gamma di problemi.
Spero di aver colto la tua curiosità. Puoi andare oltre leggendo questo articolo di Landsberg e Manivel:
¹ Non correggerò questo errore, perché ho preso un raffreddore.
Ho appena ricevuto l'incarico di fare questo per i compiti, e ho pensato di avere un'illuminazione epifanica: l'algoritmo di Strassen sacrifica la "larghezza" dei suoi componenti pre-sommatoria per utilizzare meno operazioni in cambio di " componenti "pre-sommatori" più profondi che possono ancora essere usati per estrarre la risposta finale. (Questo non è il modo migliore per dirlo, ma è difficile per me spiegarlo).
Userò l'esempio di moltiplicare due numeri complessi insieme per illustrare il bilancio di " operazioni contro componenti ":
Notatecheutilizziamo4moltiplicazioni,cherisultanoin4componentidelprodotto:
Sinotichei2componentifinalichevogliamo:lepartirealiequelleimmaginariedelnumerocomplesso,sonoinrealtàequazionilineari:sonosommediprodottiinscala.Quindiabbiamoachefarecondueoperazioniqui:addizioneemoltiplicazione.
Ilfattoècheinostri4componentidelprodottopossonorappresentareinostri2componentifinalisesemplicementeaggiungiamoosottraiinostricomponenti:
Mainostriultimi2componentipossonoessererappresentaticomesommediprodotti.Eccocosamièvenutoinmente:
Seriesciavedere,inrealtàabbiamosolobisognodi3distinticomponentidelprodottoperrealizzareinostriultimidue:
Maaspetta!Ciascunadelleletteremaiuscoleèdiperséunprodotto!Mailproblemaèchesappiamochepossiamogenerare(A+B+C+D)da(a+b)(c+d),cheèsolounamoltiplicazione.
Quindi,allafine,ilnostroalgoritmoèottimizzatoperutilizzaremeno,macomponenti"più grassi", in cui scambiamo la quantità di moltiplicazioni per più operazioni di somma.
Parte di ciò che abilita questa proprietà distributiva, che consente ad A (B + C) di essere equivalente a (AB + AC). Osserva come il primo può essere calcolato usando 1 add e 1 operazione multipla, mentre il secondo richiede 2 moltiplicazioni e 1 somma.
L'algoritmo di Strassen è un'estensione dell'ottimizzazione applicata ai prodotti a numero complesso, eccetto che ci sono più termini di prodotto target e possibili più componenti di prodotto che possiamo usare per ottenere quei termini. Per una matrice 2x2, l'algoritmo di Strassen trasforma un algoritmo che ha bisogno di 8 moltiplicazioni per uno che richiede 7 moltiplicazioni e sfrutta la proprietà distributiva per "unire" due moltiplicazioni in un'unica operazione, e invece toglie il nuovo nodo "più grasso" per estrarne una termine del prodotto o altro, ecc.
Un buon esempio: per ottenere (-1) e (2) e (5), puoi pensarci come (-1), (2), (5), oppure puoi pensarci come ( 2-3), (2), (2 + 3). Le seconde operazioni usano numeri meno distinti, però. Il problema è che il numero di numeri distinti equivale al numero di componenti del prodotto che è necessario calcolare per la moltiplicazione della matrice. Semplicemente ottimizziamo per questo per trovare una certa vista delle operazioni sottostanti che sfruttano gli output isomorfi usando una variazione diversa attraverso la proprietà distributiva.
Forse questo potrebbe essere collegato alla topologia in qualche modo? Questo è solo il modo in cui il mio laico lo capisce.
Modifica: ecco una foto delle mie note che ho disegnato nel processo di rendere la spiegazione del numero complesso:
Leggi altre domande sui tag algorithms matrix