Algorisme de Strassen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Strassen_algorithm.svg/402px-Strassen_algorithm.svg.png)
En àlgebra lineal, l'algorisme de Strassen, que rep el nom de Volker Strassen, és un algorisme per a la multiplicació de matrius.[1] É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.[2]
Volker Strassen va publicar per primera vegada aquest algorisme el 1969 i així va demostrar que el L'algorisme general de multiplicació de matrius no era òptim.[3] 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 | ||||||
1 | |||||||
2 | |||||||
3 | |||||||
4 | |||||||
5 | |||||||
6 | |||||||
7 | |||||||
8 | |||||||
Sumar matrius de mida només requereix operacions, mentre que la multiplicació és substancialment més cara (tradicionalment 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: sigui el nombre d'operacions per a a matriu. Aleshores, mitjançant l'aplicació recursiva de l'algorisme de Strassen, ho veiem , per alguna constant que depèn del nombre d'addicions realitzades a cada aplicació de l'algorisme. Per tant , és a dir, la complexitat asimptòtica per multiplicar matrius de mida utilitzant l'algorisme de Strassen és . La reducció del nombre d'operacions aritmètiques, però, té el preu d'una estabilitat numèrica una mica reduïda,[4] 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.