Algoritmo di Strassen

Da Wikipedia, l'enciclopedia libera.

In matematica, e più particolarmente in algebra lineare, per algoritmo di Strassen si intende un algoritmo (dovuto al matematico tedesco Volker Strassen) finalizzato al calcolo del prodotto di due matrici. Esso è decisamente meno intuitivo del procedimento che si basa sulla formula di definizione del prodotto fra matrici (che chiameremo procedimento standard), ma ha un ordine di complessità minore.

Storia[modifica | modifica wikitesto]

Volker Strassen ha proposto l'algoritmo che porta il suo nome nel 1969. Si tratta di un algoritmo che rispetto allo standard risulta un po' più veloce, ma è sensibilmente più complesso da implementare e richiede più memoria. Tutto questo fa sì che esso sia ben poco utilizzato nelle applicazioni di interesse pratico. Accade però che Strassen è stato il primo a far notare che l'algoritmo di Gauss non costituisce un procedimento ottimale e suoi scritti in proposito hanno avviato la ricerca di algoritmi ancora più veloci (come ad es l'algoritmo di Coppersmith - Winograd) e in genere la ricerca di algoritmi che si allontanano dai più intuitivi.

Algoritmo[modifica | modifica wikitesto]

Siano A e B due matrici quadrate dello stesso aspetto su un campo K. Vogliamo calcolare la matrice prodotto C

\mathbf{C} := \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in \mathbb{K}^{2^n \times
2^n}

Se le matrici A e B non hanno aspetto della forma 2n × 2n riempiamo le righe e le colonne che mancano al raggiungimento del suddetto aspetto con zeri.

Decomponiamo A, B e C in sottomatrici con estensioni dimezzate


\mathbf{A} =:
\begin{pmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
\end{pmatrix}
\mbox { , }
\mathbf{B} =:
\begin{pmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
\end{pmatrix}
\mbox { , }
\mathbf{C} =:
\begin{pmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
\end{pmatrix}

con

\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in \mathbb{K}^{2^{n-1} \times 2^{n-1}} .

Per le sottomatrici si trova

\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}
\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}
\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}
\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}

Con questa costruzione non abbiamo ridotto il numero di moltiplicazioni. Abbiamo ancora bisogno di 8 moltiplicazioni per calcolare le matrici Ci,j, abbiamo bisogno dello stesso numero di moltiplicazioni qualora usiamo il procedimento standard di moltiplicazione.

L'innovazione consiste nel definire nuove matrici

\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})
\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}
\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})
\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})
\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}
\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})
\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})

e nell'usare queste per esprimere Ci,j in termini di Mk. Secondo la definizione di Mk possiamo eliminare un prodotto di matrici e ridurre il numero di moltiplicazioni a 7 (una moltiplicazione per ogni Mk) ed esprimere le Ci,j come

\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}
\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}
\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}
\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}

Si può iterare questo processo di dimezzamento delle dimensioni n-volte finché le sottomatrici si riducono a semplici numeri.

Complessità computazionale[modifica | modifica wikitesto]

Il prodotto di due matrici n × n effettuato implementando semplicemente la definizione richiede

n^3 = n^{\log_{2}8} moltiplicazioni di elementi nel campo K. Si possono trascurare le addizioni poiché esse si effettuano molto più velocemente delle moltiplicazioni.

Con l'algoritmo di Strassen il numero delle moltiplicazioni si riduce a

n^{\log_{2}7} \approx n^{2.807} .

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica