Hvilken algoritme som er effektiv for matriksmultiplikasjon av 4×4 matriser av affine transformasjoner

Wikipedia lister opp fire algoritmer for matrisemultiplikasjon av to nxn-matriser .

Den klassiske som en programmerer ville skrive er O (n ³ ) og er oppført som «Schoolbook matrix multiplication». Jepp. O (n ³ ) er litt av en hit. La oss se på den nest beste.

Strassen-algoritmen er O (n ^2.807 ). Denne vil fungere – den har noen begrensninger for den (for eksempel størrelsen er en styrke på to) og den har en advarsel i beskrivelsen:

Sammenlignet med konvensjonell matrisemultiplikasjon, legger algoritmen til en betydelig O (n ² ) arbeidsmengde i tillegg / subtraksjoner; så under en viss størrelse, vil det være bedre å bruke konvensjonell multiplikasjon.

For de som er interessert i denne algoritmen og dens opprinnelse, ser på Hvordan kom Strassen på matriksmultiplikasjonsmetoden? kan være en god lesning. Det gir et snev av kompleksiteten til den innledende O (n ² ) arbeidsbelastningen som legges til og hvorfor dette ville være dyrere enn bare å gjøre den klassiske multiplikasjonen.

Så det virkelig er O (n ² + n ^2.807 ) med den biten om at lavere eksponent n blir ignorert når du skriver ut stor O. Det ser ut til at hvis du jobber med en fin 2048×2048 matrise, kan dette være nyttig. For en 4×4-matrise vil den sannsynligvis finne den tregere når den overhead spiser opp hele den andre tiden.

Og så er det Coppersmith – Winograd algoritme , som er O (n ^2.373 ) med ganske mange forbedringer. Den kommer også med en advarsel:

Coppersmith – Winograd-algoritmen brukes ofte som en byggestein i andre algoritmer for å bevise teoretiske tidsgrenser. I motsetning til Strassen-algoritmen brukes den imidlertid ikke i praksis fordi den bare gir en fordel for matriser så store at de ikke kan behandles av moderne maskinvare.

Så, det er bedre når du jobber med superstore matriser, men igjen, ikke nyttig for en 4×4-matrise.

Dette gjenspeiles igjen på wikipedias side i Matrisemultiplikasjon: Underkubiske algoritmer som får årsaken til at ting går raskere:

Algoritmer eksisterer som pr ovide bedre kjøretider enn de rette. Den første som ble oppdaget var Strassens algoritme, utviklet av Volker Strassen i 1969 og ofte referert til som «rask matriksmultiplikasjon». Den er basert på en måte å multiplisere to 2 × 2-matriser som bare krever 7 multiplikasjoner (i stedet for den vanlige 8), på bekostning av flere tilleggs- og subtraksjonsoperasjoner. Å bruke dette rekursivt gir en algoritme med en multiplikasjonskostnad på O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Strassens algoritme er mer kompleks, og den numeriske stabiliteten er redusert sammenlignet med den naive algoritmen, men den er raskere i tilfeller der n> 100 eller så og vises i flere biblioteker, for eksempel BLAS.

Og det er kjernen i hvorfor algoritmene er raskere – du bytter ut noe numerisk stabilitet og noe tilleggsoppsett. Det ekstra oppsettet for en 4×4-matrise er mye mer enn kostnadene ved å gjøre mer multiplikasjon.

Og nå, for å svare på spørsmålet ditt:

Men er det noen algoritmer som er spesielt effektive for matriser som er så små?

Nei, det er ingen algoritmer som er optimalisert for 4×4 matriksmultiplikasjon fordi O (n ³ ) en fungerer ganske rimelig til du begynner å finne ut at du er villig til å ta en stor hit for overhead. For din spesifikke situasjon kan det være noe overhead som du kan pådra deg å vite spesifikke ting på forhånd om matriksene dine (som hvor mye noen data vil bli gjenbrukt), men egentlig er det enkleste å skrive god kode for O (n ³ ) løsning, la kompilatoren håndtere den, og profilere den senere for å se om du faktisk har koden som det sakte punktet i matrisemultiplikasjonen.

Relatert på Math.SE: Minimum antall multiplikasjoner som kreves for å invertere en 4×4-matrise

Ofte er enkle algoritmer den raskeste for veldig små sett, fordi mer komplekse algoritmer vanligvis bruker noe transformasjon som gir litt overhead. Jeg tror det beste alternativet ikke er på en mer effektiv algoritme (jeg tror de fleste biblioteker bruker enkle metoder), men på en mer effektiv implementering, for eksempel en som bruker SIMD-utvidelser (forutsatt x86- eller amd64-kode), eller håndskrevet i montering . Også minneoppsettet bør være gjennomtenkt. Du burde være i stand til å finne nok ressurser på dette.

For 4×4 matte / matte multiplikasjon er algoritmiske forbedringer ofte ute . Den grunnleggende kubikk-tid-kompleksitetsalgoritmen har en tendens til å klare seg ganske bra, og alt som er mer avancert enn det, er mer sannsynlig å degradere i stedet for å forbedre tidene. Bare generelt er fancy algoritmer lite egnet hvis det ikke er en skalerbarhetsfaktor involvert (for eksempel: prøver å kviksortere en matrise som alltid har 6 elementer i motsetning til en enkel innsetting eller boblesortering). ting som matrisetransposisjon her for å forbedre referanselokaliteten hjelper heller ikke faktisk referanselokalitet når en hel matrise kan passe inn i en eller to cachelinjer. På denne typen miniatyrskala, hvis du gjør multiplisering med 4×4 matte / matte i massevis, vil forbedringene generelt komme fra mikronivåoptimalisering av instruksjoner og minne, som riktig justering av cache-linjen.

Kommentarer

• Flott svar! Jeg ‘ har aldri hørt om SoA-akronymet (i det minste er det på nederlandsk et akronym for ‘ seksueel overdraagbare aandoening ‘ som betyr ‘ seksuelt overført sykdom ‘ … men at ‘ er forhåpentligvis ikke hva du mener her). Teknikken virker klar, jeg ‘ er til og med ganske overrasket over at det er et navn på den. Hva står SoA for?
• @ Ruben Structure of Arrays i motsetning til Arrays of Structures. SoAs kan også være PITAs – best lagret for dine mest kritiske veier. Her ‘ en fin liten lenke jeg fant om emnet: stackoverflow.com/questions/17924705/…
• Det kan være lurt å nevne C ++ 11 / C11 alignas .

Hvis du vet med sikkerhet at du bare trenger å multiplisere 4×4 matriser, så trenger du ikke å bekymre deg for en generell algoritme i det hele tatt. Du kan bare ta inn to pekere og bruke dette:

(Jeg vil på det sterkeste anbefale å oversette dette på en eller annen automatisk måte).

Kompilatoren vil da være optimalt posisjonert for å optimalisere denne koden (for å gjenbruke delsummer, omorganisere matematikken osv.) da den kan se alt, er det ingen dynamiske sløyfer og ingen kontrollflyt.

Vanskelig å forestille seg at dette kan slå uten bruker egenart.