Algoritmo di Strassen

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

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

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 2ⁿ × 2ⁿ 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 C_i,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 C_i,j in termini di M_k. Secondo la definizione di M_k possiamo eliminare un prodotto di matrici e ridurre il numero di moltiplicazioni a 7 (una moltiplicazione per ogni M_k) ed esprimere le C_i,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

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.8074}$ .

Bibliografia

• Strassen, Volker (1969): Gaussian Elimination is not Optimal, Numer. Math. 13, pp. 354-356

Collegamenti esterni

• (EN) Strassen's Formula in MathWorld
• (EN) Analysis of Strassen Algorithm by Thomas Visnius