title: Algoritmo di Strassen
text: # 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}$ .
  