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.

La columna de l'esquerra visualitza els càlculs necessaris per determinar el resultat d'una multiplicació matricial 2x2. La multiplicació de matrius naïf requereix una multiplicació per cada "1" de la columna de l'esquerra. Cadascuna de les altres columnes (M1-M7) representa una única de les 7 multiplicacions de l'algorisme de Strassen. La suma de les columnes M1-M7 dóna el mateix resultat que la multiplicació matricial completa a l'esquerra.

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				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}^{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.