Vilken algoritm som fungerar för matrixmultiplikation av 4×4-matriser med affina transformationer

Wikipedia listar fyra algoritmer för matrismultiplikation av två nxn-matriser .

Den klassiska som en programmerare skulle skriva är O (n ³ ) och listas som ”Schoolbook matrix multiplication”. Japp. O (n ³ ) är lite av en träff. Låt oss titta på den näst bästa.

Strassen-algoritmen är O (n ^2.807 ). Den här skulle fungera – den har vissa begränsningar för den (som storleken är en kraft på två) och den har en förbehåll i beskrivningen:

Jämfört med konventionell matrixmultiplikation adderar algoritmen en betydande O (n ² ) arbetsbelastning i tillägg / subtraktion; så under en viss storlek är det bättre att använda konventionell multiplikation.

För dem som är intresserade av denna algoritm och dess ursprung, tittar på Hur kom Strassen fram med sin matrixmultiplikationsmetod? kan vara en bra läsning. Det ger en ledtråd till komplexiteten i den ursprungliga O (n ² ) arbetsbelastningen som läggs till och varför detta skulle vara dyrare än att bara göra den klassiska multiplikationen.

Så det verkligen är O (n ² + n ^2.807 ) med den biten om att lägre exponent n ignoreras när du skriver ut stor O. Det verkar som om du arbetar på en fin 2048×2048 matris, det här kan vara användbart. För en 4×4-matris kommer den förmodligen att hitta den långsammare eftersom den övre kostnaden äter upp hela tiden.

Och sedan finns det Coppersmith – Winograd algoritm som är O (n ^2.373 ) med en hel del förbättringar. Den kommer också med en varning:

Algoritmen Coppersmith – Winograd används ofta som en byggsten i andra algoritmer för att bevisa teoretiska tidsgränser. Till skillnad från Strassen-algoritmen används den inte i praktiken eftersom den bara ger en fördel för matriser så stora att de inte kan bearbetas av modern hårdvara.

Så det är bättre när du arbetar på superstora matriser, men igen, inte användbart för en 4×4-matris.

Detta återspeglas återigen på wikipedias sida i Matrixmultiplikation: Sub-kubiska algoritmer som får varför saker går snabbare:

Algoritmer finns som pr ovide bättre körtider än de enkla. Den första som upptäcktes var Strassens algoritm, utformad av Volker Strassen 1969 och ofta kallad ”snabbmatrismultiplikation”. Den bygger på ett sätt att multiplicera två 2 × 2-matriser som bara kräver 7 multiplikationer (istället för den vanliga 8), på bekostnad av flera ytterligare additions- och subtraktionsoperationer. Att använda detta rekursivt ger en algoritm med en multiplikationskostnad av O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Strassens algoritm är mer komplex och den numeriska stabiliteten minskar jämfört med den naiva algoritmen, men den är snabbare i fall där n> 100 eller så och visas i flera bibliotek, till exempel BLAS.

Och det är kärnan i varför algoritmerna är snabbare – du byter ut viss numerisk stabilitet och en del ytterligare inställningar. Den extra installationen för en 4×4-matris är mycket mer än kostnaden för att göra mer multiplikation.

Och nu, för att svara på din fråga:

Men finns det några algoritmer som är särskilt effektiva för små matriser?

Nej, det finns inga algoritmer som är optimerade för 4×4 matrismultiplikation eftersom O (n ³ ) en fungerar ganska rimligt tills du börjar upptäcka att du är villig att ta en stor hit för overhead. För din specifika situation kan det finnas några omkostnader som du kan ådra dig att veta specifika saker i förväg om dina matriser (som hur mycket en del data kommer att återanvändas), men det enklaste är att skriva bra kod för O (n ³ ) -lösning, låt kompilatorn hantera den och profilera den senare för att se om du faktiskt har koden som den långsamma platsen i matrixmultiplikationen.

Relaterat på Math.SE: Minsta antal multiplikationer som krävs för att invertera en 4×4-matris

Ofta är enkla algoritmer de snabbaste för mycket små uppsättningar, eftersom mer komplexa algoritmer vanligtvis använder någon transformation som ger lite overhead. Jag tror att din bästa satsning inte är på en mer effektiv algoritm (jag tror att de flesta bibliotek använder enkla metoder), utan på en mer effektiv implementering, till exempel en som använder SIMD-tillägg (förutsatt x86- eller amd64-kod), eller handskriven i montering . Minneslayouten bör också vara väl genomtänkt. Du borde kunna hitta tillräckligt med resurser om detta.

För multiplikation av matta / matta med 4×4 är algoritmiska förbättringar ofta ute . Den grundläggande kubik-tid-komplexitetsalgoritmen tenderar att klara sig ganska bra, och allt snyggare än det är mer benägna att försämras snarare än att förbättra tiderna. Bara i allmänhet är snygga algoritmer olämpliga om det inte är någon skalbarhetsfaktor inblandad (t.ex. att försöka kvicksortera en matris som alltid har 6 element i motsats till en enkel insättning eller bubblasortering). saker som matrisöverföring här för att förbättra referensplatsen hjälper inte heller referensplatsen när en hel matris kan passa in i en eller två cachelinjer. I denna typ av miniatyrskala, om du gör 4×4 matta / matta-multiplikation i massor, kommer förbättringarna i allmänhet från mikronivåoptimeringar av instruktioner och minne, som korrekt cache-line-inriktning. / h3>

• Bra svar! Jag ’ har aldrig hört talas om SoA-förkortningen (åtminstone på nederländska är det en förkortning för ’ seksueel overdraagbare aandoening ’ vilket betyder ’ sexuellt överförbar sjukdom ’ … men att ’ är förhoppningsvis inte vad du menar här). Tekniken verkar tydlig, jag ’ är till och med ganska förvånad över att det finns ett namn på den. Vad står SoA för?
• @ Ruben Structure of Arrays i motsats till Arrays of Structures. SoAs kan också vara PITAs – bäst sparas för dina mest kritiska vägar. Här ’ en trevlig liten länk som jag hittade om ämnet: stackoverflow.com/questions/17924705/…
• Du kanske vill nämna C ++ 11 / C11 alignas .

Om du vet med säkerhet att du bara behöver multiplicera 4×4 matriser behöver du inte alls oroa dig för en allmän algoritm. Du kan bara ta in två pekare och använda den här:

(Jag rekommenderar starkt att du översätter detta på ett automatiserat sätt).

Kompilatorn skulle då vara optimalt placerad för att optimera den här koden (för att återanvända partiella summor, ordna matematiken osv.) eftersom den kan se allt, det finns inga dynamiska slingor och inget kontrollflöde. med hjälp av inneboende.