Algoritmo di Strassen
# 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^n$ × $2^n$ 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}$ .
