Algoritme de Strassen

En la disciplina matemàtica del àlgebra llineal, l'algoritme de Strassen, cridat aixina per Volker Strassen, és un algoritme usat per a la multiplicació de matrius. És asintóticamente més ràpit que l'algoritme de multiplicació de matrius estàndar, pero més llent que l'algoritme més ràpit conegut, i és útil en la pràctica per a matrius grans.

Història

Volker Strassen va publicar l'algoritme de Strassen en 1969. Pese a que el seu algoritme és només llaugerament més ràpit que l'algoritme estàndar per a la multiplicació de matrius, va anar el primer en senyalar que l'enfocament estàndar no és òptim. El seu artícul va començar la busca d'algoritmes encara més ràpits, com el complex algoritme de Coppersmith–Winograd de Shmuel Winograd en 2010 (que utilisa 20 multiplicacions binarias, pero utilisa 155 sumes binarias en lloc de les 18 de l'algoritme de Strassen), publicat en 2000 .

Algoritme

Sean A, B dos matrius quadrades sobre un anell R. Volem calcular la matriu C com a producte

$𝐂=𝐀𝐁𝐀,𝐁,𝐂\in R^{2^n\times 2^n}$

Si les matrius A, B no són de tipo 2ⁿ x 2ⁿ caldrà reblir lo que falta de files i columnes en zeros.

Partim A, B i C en matrius d'igual tamany de bloc

$𝐀=\left[\begin{array}{cc}{𝐀}_{1,1}& {𝐀}_{1,2}\\ {𝐀}_{2,1}& {𝐀}_{2,2}\end{array}\right]\text{ , }𝐁=\left[\begin{array}{cc}{𝐁}_{1,1}& {𝐁}_{1,2}\\ {𝐁}_{2,1}& {𝐁}_{2,2}\end{array}\right]\text{ , }𝐂=\left[\begin{array}{cc}{𝐂}_{1,1}& {𝐂}_{1,2}\\ {𝐂}_{2,1}& {𝐂}_{2,2}\end{array}\right]$

En

${𝐀}_{i,j},{𝐁}_{i,j},{𝐂}_{i,j}\in R^{2^{n-1}\times 2^{n-1}}$

Llavors

${𝐂}_{1,1}={𝐀}_{1,1}{𝐁}_{1,1}+{𝐀}_{1,2}{𝐁}_{2,1}$

${𝐂}_{1,2}={𝐀}_{1,1}{𝐁}_{1,2}+{𝐀}_{1,2}{𝐁}_{2,2}$

${𝐂}_{2,1}={𝐀}_{2,1}{𝐁}_{1,1}+{𝐀}_{2,2}{𝐁}_{2,1}$

${𝐂}_{2,2}={𝐀}_{2,1}{𝐁}_{1,2}+{𝐀}_{2,2}{𝐁}_{2,2}$

En esta construcció, no hem reduït el número de multiplicacions. Encara tenim 8 multiplicacions per a calcular la matriu C_{i, j} , que és el mateix número de multiplicacions que es necessiten quan s'usa el método estàndar de multiplicació de matrius.

Ara ve la part important. Definim les matrius de nou

${𝐌}_1:=({𝐀}_{1,1}+{𝐀}_{2,2})({𝐁}_{1,1}+{𝐁}_{2,2})$

${𝐌}_2:=({𝐀}_{2,1}+{𝐀}_{2,2}){𝐁}_{1,1}$

${𝐌}_3:={𝐀}_{1,1}({𝐁}_{1,2}-{𝐁}_{2,2})$

${𝐌}_4:={𝐀}_{2,2}({𝐁}_{2,1}-{𝐁}_{1,1})$

${𝐌}_5:=({𝐀}_{1,1}+{𝐀}_{1,2}){𝐁}_{2,2}$

${𝐌}_6:=({𝐀}_{2,1}-{𝐀}_{1,1})({𝐁}_{1,1}+{𝐁}_{1,2})$

${𝐌}_7:=({𝐀}_{1,2}-{𝐀}_{2,2})({𝐁}_{2,1}+{𝐁}_{2,2})$

que després s'utilisen per a expressar C_{i, j} en térmens de M_k. Per la nostra definició de la M_k podem eliminar una multiplicació de matrius i reduir el número de multiplicacions a 7 (una multiplicació per cada M_k) i expressar C_{i, j} com

${𝐂}_{1,1}={𝐌}_1+{𝐌}_4-{𝐌}_5+{𝐌}_7$

${𝐂}_{1,2}={𝐌}_3+{𝐌}_5$

${𝐂}_{2,1}={𝐌}_2+{𝐌}_4$

${𝐂}_{2,2}={𝐌}_1-{𝐌}_2+{𝐌}_3+{𝐌}_6$

Iteramos n-voltes el procés de divisió fins que les submatrices degeneran en números (elements de l'anelle R).

Les implementacions pràctiques de l'algoritme de Strassen, permeten canviar a métodos estàndar de multiplicació de matrius per a submatrices lo suficientment menudes, per a les quals són més eficients. El punt a partir del com l'algoritme de Strassen és més eficient depén de l'implementació específica i del hardware. S'ha estimat que l'algoritme de Strassen és més ràpit per a matrius en esgambi des de 32 a 128 per a implementacions optimisades, i 60.000 o més per a implementacions bàsiques.

Referències

• Strassen, Volker, L'eliminació gaussiana no és òptima, Numer. Math. 13, p. 354-356, 1969
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, i Clifford Stein. Introducció als algoritmes, Segona edició. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítul 28: Secció 28.2: Algoritme de Strassen per a multiplicació de matrius, pp.735–741.