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
![{\displaystyle \mathbf {C} :=\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in \mathbb {K} ^{2^{n}\times 2^{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f07e71c9acaf3626ba5de32bb89c770b2437be0c)
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
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35d70cbfe431c39021ac9a52f0dbcdb966ca849d)
con
.
Per le sottomatrici si trova
![{\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d91fa79d27697a5c6551698c1a83a3d5837c57b)
![{\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a08bea24eec9422cda82e6e04af1d96fc6822038)
![{\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7adffe97db091ce8ba231352b3721bbe261985ca)
![{\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b40ed74cf54465d8e54d09b8492e50689928313)
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
![{\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e9e6268d824de7ad5010a32a1921452b264f7ee)
![{\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d40beeba8019e378fa0ed4b6e549c44a140a9ec)
![{\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45e8e9679d33f2c66e24bd812e1e554f95bb1571)
![{\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c12df2bb70f8f09f33f1ca4b8c2d577d5850a2ee)
![{\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/715adfa757b74b3ad6b4eea545c24762e4079161)
![{\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30107b9c9c99494bf75f23e84b505e5921cee46e)
![{\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e93ef1c265be8be96209dde36230d56e139fc72)
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
![{\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26875b8ca1815e2c322c798faeecabe1d7836798)
![{\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e71779a8ecc64f3e1268485cf389a05cdd3e6bf8)
![{\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5853fa11f016df7eee4eb2a7ceb6137d3b3296de)
![{\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7d7d4ee9e67e0c23f1a522787d4829072542dbb)
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
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
.
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
Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica