Hvilken algoritme er performant til matrixmultiplikation af 4×4 matricer af affine transformationer

Wikipedia viser fire algoritmer til matrixmultiplikation af to nxn-matricer .

Den klassiske, som en programmør ville skrive er O (n ³ ) og er angivet som “Schoolbook matrix multiplication”. Ja. O (n ³ ) er lidt af et hit. Lad os se på den næstbedste.

Strassen-algoritmen er O (n ^2.807 ). Denne ville fungere – den har nogle begrænsninger for den (såsom størrelsen er en styrke på to) og den har en advarsel i beskrivelsen:

Sammenlignet med konventionel matrixmultiplikation tilføjer algoritmen en betydelig O (n ² ) arbejdsbelastning i tillæg / subtraktioner; så under en bestemt størrelse vil det være bedre at bruge konventionel multiplikation.

For dem der er interesserede i denne algoritme og dens oprindelse, se på Hvordan kom Strassen op med sin matrixmultiplikationsmetode? kan være en god læsning. Det giver et antydning til kompleksiteten af den oprindelige O (n ² ) arbejdsbelastning, der tilføjes, og hvorfor dette ville være dyrere end bare at udføre den klassiske multiplikation.

Så det virkelig er O (n ² + n ^2.807 ) med den smule om, at lavere eksponent n ignoreres, når du skriver stor O. Det ser ud til, at hvis du arbejder på en dejlig 2048×2048 matrix, kan dette være nyttigt. For en 4×4-matrix vil den sandsynligvis finde den langsommere, da den overhead spiser al den anden gang.

Og så er der Coppersmith – Winograd algoritme , som er O (n ^2.373 ) med en hel del forbedringer. Den leveres også med en advarsel:

Coppersmith – Winograd-algoritmen bruges ofte som en byggesten i andre algoritmer for at bevise teoretiske tidsgrænser. I modsætning til Strassen-algoritmen bruges den imidlertid ikke i praksis, fordi den kun giver en fordel for matricer, der er så store, at de ikke kan behandles af moderne hardware.

Så det er bedre, når du arbejder på super store matricer, men igen, ikke nyttigt til en 4×4 matrix.

Dette afspejles igen i wikipedias side i Matrixmultiplikation: Sub-kubiske algoritmer , som får årsagen til ting, der kører hurtigere:

Algoritmer findes der pr ovide bedre løbetider end de ligetil. Den første, der blev opdaget, var Strassens algoritme, udtænkt af Volker Strassen i 1969 og ofte omtalt som “hurtig matrixmultiplikation”. Den er baseret på en måde at multiplicere to 2 × 2-matricer, som kun kræver 7 multiplikationer (i stedet for den sædvanlige 8) på bekostning af flere yderligere additions- og subtraktionsoperationer. Anvendelse af dette rekursivt giver en algoritme med en multiplikationsomkostning på O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Strassens algoritme er mere kompleks, og den numeriske stabilitet reduceres i forhold til den naive algoritme, men den er hurtigere i tilfælde hvor n> 100 eller deromkring og vises i flere biblioteker, såsom BLAS.

Og det kommer til kernen i, hvorfor algoritmerne er hurtigere – du handler noget numerisk stabilitet og nogle yderligere opsætninger. Denne ekstra opsætning til en 4×4-matrix er meget mere end omkostningerne ved at udføre mere multiplikation.

Og nu for at besvare dit spørgsmål:

Men er der nogle algoritmer, der er særligt effektive til matricer, der er så små?

Nej, der er ingen algoritmer, der er optimeret til 4×4 matrixmultiplikation, fordi O (n ³ ) en fungerer ganske rimeligt indtil du begynder at finde ud af, at du er villig til at tage et stort hit for overhead. For din specifikke situation kan der være noget overhead, som du kan pådrage dig at vide specifikke ting på forhånd om dine matrixer (som hvor meget nogle data vil blive genbrugt), men virkelig den nemmeste ting at gøre er at skrive god kode til O (n ³ ) løsning, lad kompilatoren håndtere det og profilere det senere for at se, om du faktisk har koden som det langsomme sted i matrixmultiplikationen.

Relateret til Math.SE: Mindst antal multiplikationer, der kræves for at invertere en 4×4-matrix

Ofte er enkle algoritmer den hurtigste for meget små sæt, fordi mere komplekse algoritmer normalt bruger en vis transformation, der tilføjer noget overhead. Jeg tror, at dit bedste valg ikke er på en mere effektiv algoritme (jeg tror, de fleste biblioteker bruger enkle metoder), men på en mere effektiv implementering, for eksempel en, der bruger SIMD-udvidelser (forudsat x86- eller amd64-kode) eller håndskrevet i samling . Hukommelseslayoutet skal også være gennemtænkt. Du skal være i stand til at finde nok ressourcer til dette.

Ved multiplikation med 4×4 måtter / måtter er algoritmiske forbedringer ofte ude . Den grundlæggende kubik-tid-kompleksitetsalgoritme har en tendens til at klare sig ganske godt, og alt mere avanceret end det er mere tilbøjelige til at nedbrydes snarere end at forbedre tiderne. Bare generelt er smarte algoritmer dårligt egnede, hvis der ikke er en “skalerbarhedsfaktor” involveret (f.eks. At forsøge at kviksortere et array, der altid har 6 elementer i modsætning til en simpel indsættelse eller boblesortering). ting som matrixtransposition her for at forbedre referencelokaliteten hjælper heller ikke faktisk referencelokalitet, når en hel matrix kan passe ind i en eller to cachelinjer. På denne form for miniatureskala, hvis du laver 4×4 mat / måttemultiplikation massevis, vil forbedringerne generelt komme fra optimering af instruktioner og hukommelse på mikroniveau, som korrekt cache-liniejustering.

Kommentarer

• Fantastisk svar! Jeg ‘ har aldrig hørt om SoA-akronymet (i det mindste på hollandsk er det et akronym for ‘ seksueel overdraagbare aandoening ‘ hvilket betyder ‘ seksuelt overført sygdom ‘ … men at ‘ s forhåbentlig ikke hvad du mener her). Teknikken virker klar, jeg ‘ er endda ganske overrasket over, at der er et navn til den. Hvad står SoA for?
• @ Ruben Structure of Arrays i modsætning til Arrays of Structures. SoAs kan også være PITAs – bedst gemt til dine mest kritiske stier. Her er ‘ et dejligt lille link, jeg fandt om emnet: stackoverflow.com/questions/17924705/…
• Du vil måske nævne C ++ 11 / C11 alignas .

Hvis du ved med sikkerhed, at du kun skal multiplicere 4×4 matricer, så behøver du slet ikke bekymre dig om en generel algoritme. Du kan bare tage to markører og bruge denne:

(Jeg vil kraftigt anbefale at oversætte dette på en eller anden måde).

Compileren ville så være optimalt placeret for at optimere denne kode (for at genbruge delsummer, omarrangere matematik osv.), da den kan se alt, der er ingen dynamiske sløjfer og ingen kontrolflow. ved hjælp af iboende egenskaber.