# Algorisme de Strassen

En àlgebra lineal, l'algorisme de Strassen, que rep el nom de Volker Strassen, és un algorisme per a la multiplicació de matrius. És més ràpid que l'algorisme de multiplicació de matrius estàndard per a matrius grans, amb una complexitat asimptòtica millor, tot i que l'algorisme ingenu és sovint millor per a matrius més petites. L'algorisme de Strassen és més lent que els algorismes coneguts més ràpids per a matrius extremadament grans, però aquests algorismes galàctics no són útils a la pràctica, ja que són molt més lents per a matrius de mida pràctica. Per a matrius petites existeixen algorismes encara més ràpids.
L'algorisme de Strassen funciona per a qualsevol anell, com ara més/multiplicar, però no tots els semianells, com ara min-plus o àlgebra booleana, on l'algorisme ingenu encara funciona, i l'anomenada multiplicació de matrius combinatòria.
Volker Strassen va publicar per primera vegada aquest algorisme el 1969 i així va demostrar que el $n^{3}$ L'algorisme general de multiplicació de matrius no era òptim. La publicació de l'algoritme de Strassen va donar lloc a més investigacions sobre la multiplicació de matrius que van conduir tant a límits inferiors asimptòticament com a límits superiors computacionals millorats.
| | Standard algorithm | Standard algorithm | Standard algorithm | Strassen algorithm | Strassen algorithm | Strassen algorithm |
| $i$ | $f_{i}(\mathbf {a} )$ | $g_{i}(\mathbf {b} )$ | $w_{i}$ | $f_{i}(\mathbf {a} )$ | $g_{i}(\mathbf {b} )$ | $w_{i}$ |
| 1 | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$ | ${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}1&0\\0&1\end{bmatrix}}$ |
| 2 | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$ | ${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\1&-1\end{bmatrix}}$ |
| 3 | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&1\\0&1\end{bmatrix}}$ |
| 4 | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}1&0\\1&0\end{bmatrix}}$ |
| 5 | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$ | ${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}-1&1\\0&0\end{bmatrix}}$ |
| 6 | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$ | ${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$ |
| 7 | ${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$ | ${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$ |
| 8 | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$ | ${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$ | | | |
| | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ | $\mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$ |
Sumar matrius de mida $N/2$ només requereix $(N/2)^{2}$ operacions, mentre que la multiplicació és substancialment més cara (tradicionalment $2(N/2)^{3}$ operacions de suma o multiplicació).El nombre d'addicions i multiplicacions requerides en l'algorisme de Strassen es pot calcular de la següent manera: $f(n)$ sigui el nombre d'operacions per a a $2^{n}\times 2^{n}$ matriu. Aleshores, mitjançant l'aplicació recursiva de l'algorisme de Strassen, ho veiem $f(n)=7f(n-1)+l4^{n}$, per alguna constant $l$ que depèn del nombre d'addicions realitzades a cada aplicació de l'algorisme. Per tant, $f(n)=(7+o(1))^{n}$, és a dir, la complexitat asimptòtica per multiplicar matrius de mida $N=2^{n}$ utilitzant l'algorisme de Strassen és $O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})$. La reducció del nombre d'operacions aritmètiques, però, té el preu d'una estabilitat numèrica una mica reduïda, i l'algoritme també requereix molt més memòria en comparació amb l'algorisme ingenu.

## Referències

* ↑ «Strassen’s Matrix Multiplication Algorithm | Implementation» (en anglès). https://www.geeksforgeeks.org,+07-06-2018.+[Consulta: 2 gener 2023].
* ↑ «Strassen’s Matrix Multiplication algorithm» (en anglès). https://iq.opengenus.org,+13-10-2018.+[Consulta: 2 gener 2023].
* ↑ Strassen, Volker Numer. Math., 13, 4, 1969, pàg. 354–356. DOI: 10.1007/BF02165411.
* ↑ Webb, Miller SIAM J. Comput., 4, 2, 1975, pàg. 97–107. DOI: 10.1137/0204009.