Strassen -algoritm - Strassen algorithm

I linjär algebra är Strassen -algoritmen , uppkallad efter Volker Strassen , en algoritm för matrismultiplikation . Det är snabbare än standardmatrismultiplikationsalgoritmen för stora matriser, med en bättre asymptotisk komplexitet , även om den naiva algoritmen ofta är bättre för mindre matriser. Strassen -algoritmen är långsammare än de snabbast kända algoritmerna för extremt stora matriser, men sådana algoritmer är inte användbara i praktiken , eftersom de är mycket långsammare för matriser av praktisk storlek.

Strassens algoritm fungerar för alla ringar , till exempel plus/multiplicera, men inte alla semirings , till exempel min-plus eller boolsk algebra , där den naiva algoritmen fortfarande fungerar, och så kallad kombinatorisk matrismultiplikation .

Historia

Volker Strassen publicerade denna algoritm först 1969 och bevisade att den allmänna matrismultiplikationsalgoritmen inte var optimal. Den Strassen algoritmen är endast något bättre än så, men det har offentliggjorts resulterade i mycket mer forskning om matrismultiplikation som ledde till snabbare närmar, såsom Copper-Winograd algoritm . ${\ displaystyle n^{3}}$

Algoritm

Den vänstra kolumnen representerar 2x2 matrismultiplikation . Naiv matrismultiplikation kräver en multiplikation för varje "1" i den vänstra kolumnen. Var och en av de andra kolumnerna representerar en enda av de sju multiplikationerna i algoritmen, och summan av kolumnerna ger hela matrismultiplikationen till vänster.

Låt , vara två kvadratiska matriser över en ring , till exempel matriser vars poster är heltal eller reella tal. Vi vill beräkna matrisprodukten . I följande utläggning av algoritmen, kommer vi att anta att alla dessa matriser har storlekar som är potenser av två (dvs ), men detta är bara begrepps nödvändigt - om matriserna , inte är av typ vi kan tänka konceptuellt om fyllning de "saknade" raderna och kolumnerna med nollor för att erhålla matriser med storlekar på två krafter - även om verkliga implementeringar av algoritmen naturligtvis inte kommer att göra detta i praktiken. ${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle {\ mathcal {R}}}$${\ displaystyle C = AB}$${\ displaystyle A, \, B, \, C \ in \ operatorname {Matr} _ {2^{n} \ times 2^{n}} ({\ mathcal {R}})}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle 2^{n} \ times 2^{n}}$

Vi sedan dela , och i lika stora blockmatriser${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

${\ displaystyle A = {\ begin {bmatrix} A_ {11} & A_ {12} \\ A_ {21} & A_ {22} \ end {bmatrix}}, \ quad B = {\ begin {bmatrix} B_ {11} & B_ {12} \\ B_ {21} & B_ {22} \ end {bmatrix}}, \ quad C = {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ slutet {bmatrix}}, \ quad}$

med . Den naiva algoritmen skulle vara: ${\ displaystyle A_ {ij}, B_ {ij}, C_ {ij} \ in \ operatorname {Mat} _ {2^{n-1} \ gånger 2^{n-1}} ({\ mathcal {R} })}$

${\ displaystyle {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ end {bmatrix}} = {\ begin {bmatrix} A_ {11} B_ {11}+A_ {12} B_ {21} & A_ {11} B_ {12}+A_ {12} B_ {22} \\ A_ {21} B_ {11}+A_ {22} B_ {21} & A_ {21} B_ {12 }+A_ {22} B_ {22} \ end {bmatrix}}.}$

Med denna konstruktion har vi inte minskat antalet multiplikationer. Vi behöver fortfarande 8 multiplikationer av matrisblock för att beräkna matriserna, samma antal multiplikationer som vi behöver när vi använder standardmatrismultiplikation. ${\ displaystyle C_ {ij}}$

Strassen -algoritmen definierar istället nya matriser:

${\ displaystyle {\ begin {align} M_ {1} & = (A_ {11}+A_ {22}) (B_ {11}+B_ {22}); \\ M_ {2} & = (A_ {21 }+A_ {22}) B_ {11}; \\ M_ {3} & = A_ {11} (B_ {12} -B_ {22}); \\ M_ {4} & = A_ {22} (B_ {21} -B_ {11}); \\ M_ {5} & = (A_ {11}+A_ {12}) B_ {22}; \\ M_ {6} & = (A_ {21} -A_ { 11}) (B_ {11}+B_ {12}); \\ M_ {7} & = (A_ {12} -A_ {22}) (B_ {21}+B_ {22}), \\\ slut {Justerat}}}$

använder bara 7 multiplikationer (en för varje ) istället för 8. Vi kan nu uttrycka följande i termer av : ${\ displaystyle M_ {k}}$${\ displaystyle C_ {ij}}$${\ displaystyle M_ {k}}$

${\ displaystyle {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ end {bmatrix}} = {\ begin {bmatrix} M_ {1}+M_ {4}- M_ {5}+M_ {7} & M_ {3}+M_ {5} \\ M_ {2}+M_ {4} & M_ {1} -M_ {2}+M_ {3}+M_ {6} \ end {bmatrix}}.}$

Vi upprepar denna uppdelningsprocess rekursivt tills submatriserna urartar i antal (element i ringen ). Om, som nämnts ovan, den ursprungliga matrisen hade en storlek som inte var en effekt på 2, kommer den resulterande produkten att ha noll rader och kolumner precis som och , och dessa kommer sedan att avlägsnas vid denna tidpunkt för att få den (mindre) matrisen vi ville verkligen. ${\ displaystyle {\ mathcal {R}}}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

Praktiska implementeringar av Strassens algoritm går över till standardmetoder för matrismultiplikation för tillräckligt små undermatriser, för vilka dessa algoritmer är mer effektiva. Den specifika delningspunkt för vilken Strassens algoritm är mer effektiv beror på den specifika implementeringen och hårdvaran. Tidigare författare hade uppskattat att Strassens algoritm är snabbare för matriser med bredder från 32 till 128 för optimerade implementeringar. Det har dock observerats att denna delningspunkt har ökat under de senaste åren, och en studie från 2010 visade att även ett enda steg i Strassens algoritm ofta inte är fördelaktigt för nuvarande arkitekturer, jämfört med en mycket optimerad traditionell multiplikation, tills matrisstorleken överstiger 1000 eller mer, och även för matrisstorlekar på flera tusen är fördelen vanligtvis marginell i bästa fall (cirka 10% eller mindre). En nyare studie (2016) observerade fördelar för matriser så små som 512 och en fördel kring 20%.

Asymptotisk komplexitet

Konturen av algoritmen ovan visade att man kan komma undan med bara 7, istället för de traditionella 8, matris-matrismultiplikationerna för matrisens subblock. Å andra sidan måste man göra additioner och subtraktioner av block, även om detta inte oroar den totala komplexiteten: Att lägga till matriser av storlek kräver bara operationer medan multiplikation är väsentligt dyrare (traditionellt additions- eller multiplikationsoperationer). ${\ displaystyle N/2}$${\ displaystyle (N/2)^{2}}$${\ displaystyle 2 (N/2)^{3}}$

Frågan är då hur många operationer exakt man behöver för Strassens algoritmer, och hur detta kan jämföras med standardmatrismultiplikationen som tar ungefär (var ) aritmetiska operationer, dvs en asymptotisk komplexitet . ${\ displaystyle 2N^{3}}$${\ displaystyle N = 2^{n}}$${\ displaystyle \ Theta (N^{3})}$

Antalet tillägg och multiplikationer som krävs i Strassen -algoritmen kan beräknas enligt följande: låt vara antalet operationer för en matris. Sedan genom rekursiv tillämpning av Strassen -algoritmen ser vi att för en konstant beror det på antalet tillägg som utförs vid varje applikation av algoritmen. Därför , dvs den asymptotiska komplexiteten för att multiplicera storleksmatriser med Strassen -algoritmen är . Minskningen av antalet aritmetiska operationer kommer dock till priset av en något reducerad numerisk stabilitet , och algoritmen kräver också betydligt mer minne jämfört med den naiva algoritmen. Båda initialmatriserna måste ha sina dimensioner utökade till nästa effekt 2, vilket resulterar i lagring av upp till fyra gånger så många element, och de sju hjälpmatriserna innehåller var och en fjärdedel av elementen i de expanderade. ${\ displaystyle f (n)}$${\ displaystyle 2^{n} \ times 2^{n}}$${\ displaystyle f (n) = 7f (n-1)+l4^{n}}$${\ displaystyle l}$${\ displaystyle f (n) = (7+o (1))^{n}}$${\ displaystyle N = 2^{n}}$${\ displaystyle O ([7+o (1)]^{n}) = O (N^{\ log _ {2} 7+o (1)}) \ approx O (N^{2.8074})}$

Strassens algoritm måste jämföras med det "naiva" sättet att göra matrismultiplikationen som skulle kräva 8 istället för 7 multiplikationer av delblock. Detta skulle ge upphov till komplexiteten man förväntar sig från standardförfarandet: . Jämförelsen av dessa två algoritmer visar att Strassens algoritm asymptotiskt är snabbare: Det finns en storlek så att matriser som är större multipliceras mer effektivt med Strassens algoritm än det "traditionella" sättet. Det asymptotiska påståendet innebär dock inte att Strassens algoritm alltid är snabbare även för små matriser, och i praktiken är detta i själva verket inte fallet: För små matriser överstiger kostnaden för ytterligare tillägg av matrisblock besparingarna i antalet multiplikationer. Det finns också andra faktorer som inte fångas upp av analysen ovan, till exempel skillnaden i kostnad på dagens hårdvara mellan att ladda data från minne till processorer kontra kostnaden för att faktiskt utföra operationer på dessa data. Som en konsekvens av den här typen av överväganden används Strassens algoritm vanligtvis bara på "stora" matriser. Denna typ av effekt är ännu mer uttalad med alternativa algoritmer som den av Coppersmith och Winograd : Medan asymptotiskt ännu snabbare är överkorsningspunkten så stor att algoritmen vanligtvis inte används på matriser man möter i praktiken. ${\ displaystyle O (8^{\ log _ {2} n}) = O (N^{\ log _ {2} 8}) = O (N^{3})}$${\ displaystyle N _ {\ text {tröskel}}}$${\ displaystyle N _ {\ text {tröskel}}}$

Rang eller bilinjär komplexitet

Den bilinjära komplexiteten eller rangordningen för en bilinjär karta är ett viktigt koncept i den asymptotiska komplexiteten hos matrismultiplikation. Rangordningen av en bilinjär karta över ett fält F definieras som (något av missbruk av notation ) ${\ displaystyle \ phi: \ mathbf {A} \ times \ mathbf {B} \ rightarrow \ mathbf {C}}$

${\ displaystyle R (\ phi /\ mathbf {F}) = \ min \ vänster \ {r \ vänster | \ existerar f_ {i} \ i \ mathbf {A} ^{*}, g_ {i} \ in \ mathbf {B} ^{*}, w_ {i} \ in \ mathbf {C}, \ forall \ mathbf {a} \ in \ mathbf {A}, \ mathbf {b} \ in \ mathbf {B}, \ phi (\ mathbf {a}, \ mathbf {b}) = \ sum _ {i = 1}^{r} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ {i} \ höger. \ höger \}}$

Med andra ord, rankningen av en bilinjär karta är längden på dess kortaste bilinjära beräkning. Förekomsten av Strassens algoritm visar att graden av matrismultiplikation inte är mer än sju. För att se detta, låt oss uttrycka denna algoritm (vid sidan av standardalgoritmen) som en sådan bilinjär beräkning. När det gäller matriser består dubbla mellanslag A * och B * av kartor in i fältet F framkallade av en skalär dubbelpunktsprodukt (dvs i detta fall summan av alla poster i en Hadamard-produkt .) ${\ displaystyle 2 \ times 2}$

	Standardalgoritm				Strassen -algoritm
${\ displaystyle i}$	${\ displaystyle f_ {i} (\ mathbf {a})}$	${\ displaystyle g_ {i} (\ mathbf {b})}$	${\ displaystyle w_ {i}}$		${\ displaystyle f_ {i} (\ mathbf {a})}$	${\ displaystyle g_ {i} (\ mathbf {b})}$	${\ displaystyle w_ {i}}$
1	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}}$
2	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & -1 \ end {bmatrix}}}$
3	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & -1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 1 \ end {bmatrix}}}$
4	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} -1 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 1 & 0 \ end {bmatrix}}}$
5	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} -1 & 1 \\ 0 & 0 \ end {bmatrix}}}$
6	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} -1 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$
7	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & -1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$
8	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$
	${\ displaystyle \ mathbf {a} \ mathbf {b} = \ sum _ {i = 1}^{8} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ { i}}$				${\ displaystyle \ mathbf {a} \ mathbf {b} = \ sum _ {i = 1}^{7} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ { i}}$

Det kan visas att det totala antalet elementära multiplikationer som krävs för matrismultiplikation är tätt asymptotiskt bunden till rang , dvs , eller mer specifikt, eftersom konstant är kända, . En användbar egenskap hos rankningen är att den är submultiplicativ för tensorprodukter , och detta gör att man kan visa att matrismultiplikation inte kan uppnås med mer än elementära multiplikationer för någon . (Denna -faldiga tensorprodukt av matrismultiplikationskartan med sig själv -en tionde tensoreffekt -realiseras av det rekursiva steget i den visade algoritmen.) ${\ displaystyle L}$${\ displaystyle R}$${\ displaystyle L = \ Theta (R)}$${\ displaystyle R/2 \ leq L \ leq R}$${\ displaystyle 2^{n} \ times 2^{n} \ times 2^{n}}$${\ displaystyle 7n}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle 2 \ times 2 \ times 2}$${\ displaystyle n}$

Cache -beteende

Strassens algoritm är omedvetet om cachen . Analys av dess cache -beteende -algoritm har visat att den uppstår

${\ displaystyle \ Theta \ vänster (1+{\ frac {n^{2}} {b}}+{\ frac {n^{\ log _ {2} 7}} {b {\ sqrt {M}} }}\höger)}$

cache missar under dess körning, förutsatt en idealiserad cache av storlek (dvs med längderader ). ${\ displaystyle M}$${\ displaystyle M/b}$${\ displaystyle b}$

Hänsyn till genomförande

Beskrivningen ovan anger att matriserna är fyrkantiga, och storleken är en effekt på två, och att vaddering ska användas om det behövs. Denna begränsning gör att matriserna kan delas i hälften, rekursivt, tills gränsen för skalär multiplikation har uppnåtts. Begränsningen förenklar förklaringen och analysen av komplexitet, men är faktiskt inte nödvändig; och faktiskt, vaddering av matrisen enligt beskrivningen kommer att öka beräkningstiden och kan enkelt eliminera de ganska snäva tidsbesparingar som uppnås genom att använda metoden i första hand.

En bra implementering kommer att observera följande:

• Det är inte nödvändigt eller önskvärt att använda Strassen -algoritmen till gränsen för skalare. Jämfört med konventionell matrismultiplikation lägger algoritmen till en avsevärd arbetsbelastning i addition/subtraktioner; så under en viss storlek blir det bättre att använda konventionell multiplikation. Således behöver till exempel inte a vadderas till , eftersom det kan delas upp i matriser och konventionell multiplikation kan sedan användas på den nivån.${\ displaystyle O (n^{2})}$${\ displaystyle 1600 \ times 1600}$${\ displaystyle 2048 \ times 2048}$${\ displaystyle 25 \ times 25}$
• Metoden kan verkligen tillämpas på kvadratmatriser av vilken dimension som helst. Om dimensionen är jämn delas de i hälften enligt beskrivningen. Om dimensionen är udda tillämpas nollutfyllnad med en rad och en kolumn först. Sådan stoppning kan appliceras direkt och lätt, och de extra raderna och kolumnerna kastas när resultatet bildas. Anta till exempel att matriserna är . De kan delas upp så att den övre vänstra delen är och den nedre högra är . Varhelst operationerna kräver det är måtten på noll vadderade till först. Observera till exempel att produkten endast används i den nedre raden i utdata, så det krävs bara att den är hög på raderna. och därmed behöver den vänstra faktorn som används för att generera den bara vara rader höga; följaktligen finns det ingen anledning att lägga den summan till rader; det är bara nödvändigt att paddla till kolumner för att matcha .${\ displaystyle 199 \ times 199}$${\ displaystyle 100 \ times 100}$${\ displaystyle 99 \ times 99}$${\ displaystyle 99}$${\ displaystyle 100}$${\ displaystyle M_ {2}}$${\ displaystyle 99}$${\ displaystyle A_ {21}+A_ {22}}$${\ displaystyle 99}$${\ displaystyle 100}$${\ displaystyle A_ {22}}$${\ displaystyle 100}$${\ displaystyle A_ {21}}$

Dessutom finns det inget behov av att matriserna är fyrkantiga. Icke-kvadratiska matriser kan delas i hälften med samma metoder, vilket ger mindre icke-kvadratiska matriser. Om matriserna är tillräckligt icke-kvadratiska kommer det att vara värt att reducera den första operationen till mer fyrkantiga produkter, med hjälp av enkla metoder som i huvudsak är , till exempel: ${\ displaystyle O (n^{2})}$

• En produkt av storlek kan göras som 20 separata operationer, ordnade för att bilda resultatet;${\ displaystyle [2N \ gånger N] \ ast [N \ gånger 10N]}$${\ displaystyle [N \ gånger N] \ ast [N \ gånger N]}$
• En produkt av storlek kan göras som 10 separata operationer, summeras för att bilda resultatet.${\ displaystyle [N \ times 10N] \ ast [10N \ times N]}$${\ displaystyle [N \ gånger N] \ ast [N \ gånger N]}$

Dessa tekniker kommer att göra implementeringen mer komplicerad, jämfört med att helt enkelt stoppa till en kvadratkraft på två; Det är emellertid ett rimligt antagande att alla som genomför en implementering av Strassen, snarare än konventionell multiplikation, kommer att prioritera beräkningseffektiviteten högre än enkelheten i implementeringen.

I praktiken kan Strassens algoritm implementeras för att uppnå bättre prestanda än konventionell multiplikation även för små matriser, för matriser som inte alls är kvadratiska och utan att kräva arbetsyta bortom buffertar som redan behövs för en högpresterande konventionell multiplikation.

Se även

• Beräkningskomplexitet för matematiska operationer
• Eliminering av Gauss – Jordanien
• Coppersmith – Winograd -algoritm
• Z-ordnings matrisrepresentation
• Karatsuba -algoritm , för att multiplicera n -siffriga heltal i stället för i tid${\ displaystyle O (n^{\ log _ {2} 3})}$${\ displaystyle O (n^{2})}$
• Toom-Cook-algoritm , en snabbare generalisering av Karatsuba-algoritmen som tillåter rekursiv uppdelning och erövring i mer än 2 block åt gången
• Gauss komplexa multiplikationsalgoritm multiplicerar två komplexa tal med 3 riktiga multiplikationer istället för 4

Referenser

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer , andra upplagan. MIT Press och McGraw-Hill, 2001. ISBN  0-262-03293-7 . Kapitel 28: Avsnitt 28.2: Strassens algoritm för matrismultiplikation, s. 735–741.

externa länkar

• Weisstein, Eric W. "Strassens formler" . MathWorld .(inkluderar även formler för snabb matrisinversion )
• Tyler J. Earnest, Strassens algoritm om cellbredbandsmotorn