Welk algoritme is performant voor matrixvermenigvuldiging van 4×4 matrices van affiene transformaties

Wikipedia somt vier algoritmen op voor matrixvermenigvuldiging van twee nxn-matrices .

De klassieke die een programmeur zou schrijven is O (n ³ ) en wordt vermeld als de “Schoolbook-matrixvermenigvuldiging”. Ja. O (n ³ ) is een beetje een hit. Laten we eens kijken naar de volgende beste.

Het Strassen-algoritme is O (n ^2.807 ). Deze zou werken – het heeft enkele beperkingen (zoals de grootte is een macht van twee) en het heeft een voorbehoud in de beschrijving:

Vergeleken met conventionele matrixvermenigvuldiging voegt het algoritme een aanzienlijke O (n ² ) werkbelasting toe aan optellen / aftrekken; dus onder een bepaalde grootte is het beter om conventionele vermenigvuldiging te gebruiken.

Voor degenen die geïnteresseerd zijn in dit algoritme en de oorsprong ervan, kijkend naar Hoe kwam Strassen met zijn methode voor matrixvermenigvuldiging? kan een goede lezing zijn. Het geeft een hint naar de complexiteit van die initiële O (n ² ) workload die wordt toegevoegd en waarom dit duurder zou zijn dan alleen de klassieke vermenigvuldiging.

Dus het is echt is O (n ² + n ^2.807 ) waarbij dat beetje over de lagere exponent n wordt genegeerd bij het uitschrijven van een grote O. Het lijkt erop dat als je werken aan een mooie 2048×2048 matrix, dit kan handig zijn. Voor een 4×4-matrix zal deze het waarschijnlijk langzamer vinden, omdat die overhead de hele andere tijd opeet.

En dan is er nog de Koperslager – Winograd algoritme dat is O (n ^2.373 ) met nogal wat verbeteringen. Het komt ook met een voorbehoud:

Het Coppersmith-Winograd-algoritme wordt vaak gebruikt als bouwsteen in andere algoritmen om theoretische tijdgrenzen te bewijzen. In tegenstelling tot het Strassen-algoritme wordt het in de praktijk echter niet gebruikt omdat het alleen een voordeel biedt voor matrices die zo groot zijn dat ze niet worden verwerkt door moderne hardware.

Dus het is beter als je aan supergrote matrices werkt, maar nogmaals, niet bruikbaar voor een 4×4-matrix.

Dit wordt opnieuw weerspiegeld in de Wikipedia-pagina in Matrixvermenigvuldiging: Subkubische algoritmen die het waarom van dingen die sneller gaan, bekijken:

Er bestaan algoritmen die pr ovide betere looptijden dan de eenvoudige. Het eerste dat werd ontdekt, was het algoritme van Strassen, bedacht door Volker Strassen in 1969 en vaak aangeduid als snelle matrixvermenigvuldiging. Het is gebaseerd op een manier om twee 2 × 2-matrices te vermenigvuldigen waarvoor slechts 7 vermenigvuldigingen nodig zijn (in plaats van de gebruikelijke 8), ten koste van verschillende extra optel- en aftrekbewerkingen. Door dit recursief toe te passen, ontstaat een algoritme met een vermenigvuldigende kost van O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Het algoritme van Strassen is complexer en de numerieke stabiliteit is verminderd in vergelijking met het naïeve algoritme, maar het is sneller in gevallen waarin n> 100 of zo en verschijnt in verschillende bibliotheken, zoals BLAS.

En dat komt tot de kern waarom de algoritmen sneller zijn – je ruilt wat numerieke stabiliteit en wat extra instellingen. Die extra setup voor een 4×4-matrix is veel meer dan de kosten van de meer vermenigvuldiging.

En nu, om uw vraag te beantwoorden:

Maar zijn er enkele algoritmen die bijzonder efficiënt zijn voor matrices die klein zijn?

Nee, er zijn geen algoritmen die zijn geoptimaliseerd voor 4×4 matrixvermenigvuldiging omdat de O (n ³ ) redelijk redelijk werkt totdat je begint te ontdekken dat je bereid bent een grote hit te nemen voor overhead. Voor uw specifieke situatie kan er enige overhead zijn die u zou kunnen oplopen als u van tevoren specifieke dingen over uw matrixen weet (zoals hoeveel gegevens worden hergebruikt), maar het gemakkelijkste is om goede code te schrijven voor de O (n ³ ) oplossing, laat de compiler het afhandelen en profileer het later om te zien of de code echt de langzame plek is in de matrixvermenigvuldiging.

Gerelateerd aan Math.SE: Minimaal aantal vermenigvuldigingen dat nodig is om een 4×4 matrix om te keren

Vaak zijn eenvoudige algoritmen het snelst voor zeer kleine sets, omdat complexere algoritmen meestal enige transformatie gebruiken die wat overhead toevoegt. Ik denk dat je beste gok niet is op een efficiënter algoritme (ik denk dat de meeste bibliotheken eenvoudige methoden gebruiken), maar op een efficiëntere implementatie, bijvoorbeeld een met SIMD-extensies (uitgaande van x86- of amd64-code) of met de hand geschreven in assembly . Ook moet de geheugenlay-out goed doordacht zijn. U zou hierover voldoende bronnen moeten kunnen vinden.

Voor 4×4-mat / mat-vermenigvuldiging zijn algoritmische verbeteringen vaak uit . Het elementaire kubieke-tijd-complexiteitsalgoritme heeft de neiging om het redelijk goed te doen, en alles wat mooier is dan dat, zal eerder verslechteren dan de tijden verbeteren. Gewoon in het algemeen zijn fraaie algoritmen niet geschikt als er geen “schaalbaarheidsfactor bij betrokken is (bijvoorbeeld: een array proberen te quicksorteren die altijd 6 elementen heeft in tegenstelling tot een simpele invoeging of bellen-sortering). zaken als matrixtranspositie hier om de referentielocatie te verbeteren, helpen ook niet echt de referentielocatie wanneer een volledige matrix in een of twee cache-regels past. Op dit soort miniatuurschaal, als je massaal 4×4 mat / mat vermenigvuldigt, zullen de verbeteringen over het algemeen afkomstig zijn van optimalisaties van instructies en geheugen op microniveau, zoals een juiste uitlijning van de cache-lijn.

Opmerkingen

• Geweldig antwoord! Ik ‘ heb nog nooit van het SoA-acroniem gehoord (althans, in het Nederlands is het een acroniem voor ‘ seksueel overdraagbare aandoening ‘ wat betekent ‘ seksueel overdraagbare aandoening ‘ … maar dat ‘ s hopelijk niet wat je hier bedoelt). De techniek lijkt duidelijk, ik ‘ ben zelfs nogal verrast dat er een naam voor is. Waar staat SoA voor?
• @Ruben Structuur van arrays in tegenstelling tot arrays van structuren. SoAs kunnen ook PITAs zijn – het best opgeslagen voor uw meest kritieke paden. Hier ‘ is een leuke kleine link die ik over het onderwerp heb gevonden: stackoverflow.com/questions/17924705/…
• Misschien wil je C ++ 11 / C11 alignas .

Als je zeker weet dat je alleen 4×4 hoeft te vermenigvuldigen matrices, dan hoeft u zich helemaal geen zorgen te maken over een algemeen algoritme. U kunt gewoon twee tips opnemen en deze gebruiken:

(ik zou sterk aanbevelen om dit op een geautomatiseerde manier te vertalen).

De compiler zou dan zijn optimaal gepositioneerd om deze code te optimaliseren (om gedeeltelijke sommen te hergebruiken, de wiskunde opnieuw te ordenen, enz.) omdat het alles kan zien, er geen dynamische loops zijn en geen controlestroom.

Moeilijk voor te stellen dat dit kan worden verslagen zonder intrinsiek gebruiken.

U kunt asymptotische complexiteit niet rechtstreeks vergelijken als u n anders definieert. Je bent gewend om de complexiteit van algoritmen te vergelijken op platte datastructuren zoals lijsten, waarbij n is gedefinieerd als het totale aantal elementen in de lijst, maar de matrixalgoritmen definiëren n als slechts de lengte van één zijde .

Door deze definitie van n, iets eenvoudigs als één keer naar elk element kijken om het af te drukken, wat je normaal zou beschouwen als O (n), is O (n ² ) . Als u n definieert als het totale aantal elementen in de matrix, dwz n = 16 voor een 4×4-matrix, dan is de naïeve matrixvermenigvuldiging alleen O (n ^1.5 ), wat best goed is.

Je kunt het beste profiteren van parallellisme door SIMD-instructies of een GPU te gebruiken, in plaats van te proberen het algoritme te verbeteren op basis van de verkeerde overtuiging dat O (n ³ ) is zo erg als het zou zijn als n vergelijkbaar zou zijn met een platte gegevensstructuur.