Kíváncsi lennék, mi a jó, performáns algoritmus a 4×4-es mátrixok mátrixszorzásához. Néhány affin transzformációt valósítok meg, és tisztában vagyok vele, hogy a hatékony mátrixszorzásnak számos algoritmusa létezik, például Strassen. De vannak olyan algoritmusok, amelyek különösen hatékonyak az ilyen kicsi mátrixok esetében? A legtöbb olyan forrás, amelyre pillantást vetettem, aszimptotikusan a leghatékonyabbak.
Megjegyzések
Válasz
A Wikipedia négy algoritmust sorol fel a két nxn mátrix mátrixszorzásához .
A klasszikus, amelyet egy programozó írna, O (n 3 ), és az “Iskolai könyv mátrix szorzása” néven szerepel. Igen. Az O (n 3 ) kissé eltalált. Nézzük meg a következő legjobbat.
A Strassen algoritmus O (n 2.807 ). Ez működne – van néhány korlátozása (például a méret kettő hatványa), és a leírásban szerepel egy figyelmeztetés:
A hagyományos mátrixszorzathoz képest az algoritmus jelentős O (n 2 ) terhelést ad hozzá összeadás / kivonás mellett; így egy bizonyos méret alatt jobb lesz a hagyományos szorzást használni.
Azok számára, akiket érdekel ez az algoritmus és annak eredete, a Hogyan találta Strassen a mátrixszorzási módszerét? jó olvasmány lehet. Tippet ad a hozzáadott kezdeti O (n 2 ) terhelés összetettségére, és miért lenne ez drágább, mint csak a klasszikus szorzást végezni.
Tehát valóban O (n 2 + n 2.807 ), azzal a bittel, hogy az alacsonyabb kitevő n t figyelmen kívül hagyják a nagy O írásakor. Úgy tűnik, hogy ha egy szép 2048×2048 mátrixon dolgoznak, ez hasznos lehet. Egy 4×4-es mátrix esetében valószínűleg lassabban fog működni, mivel a rezsi máskor megeszi.
És akkor ott van a Coppersmith – Winograd algoritmus , amely O (n 2.373 ), jó néhány bit fejlesztéssel. Ez egy figyelmeztetést is tartalmaz:
A Coppersmith – Winograd algoritmust más algoritmusokban gyakran használják építőelemként az elméleti időhatárok bizonyítására. A Strassen algoritmustól eltérően azonban a gyakorlatban nem használják, mert csak akkora előnyt jelent, ha olyan nagy mátrixok vannak, hogy nem tudnak modern hardverrel kell feldolgozni.
Tehát jobb, ha szuper nagy mátrixokon dolgozunk, de megint nem hasznos 4×4-es mátrixoknál.
Ezt ismét tükrözi a wikipédia oldala a mátrixszorzásban: Alkocka algoritmusok , amelyek a gyorsabban futó dolgok miértjéhez értenek:
Algoritmusok léteznek, amelyek pr jobb futási időket mutatnak be, mint az egyenesek. Elsőként a Strassen-féle algoritmust fedezték fel, amelyet Volker Strassen dolgozott ki 1969-ben, és amelyet gyakran “gyors mátrixszorzásnak” neveznek. Két 2 × 2-mátrix szorzásának módján alapszik, amely csak 7 szorzást igényel (a a szokásos 8), több további összeadási és kivonási művelet rovására. Ennek rekurzív alkalmazása algoritmust eredményez, amelynek O-szorzata multiplikatív (n log 2 7 ) ≈ O (n 2.807 ). Strassen algoritmusa összetettebb, és a numerikus stabilitás csökken a naiv algoritmushoz képest, de gyorsabb azokban az esetekben, amikor n> 100 vagy több, és több könyvtárban is megjelenik, például a BLAS-ban.
És ez eljut ahhoz a lényegig, hogy miért gyorsabbak az algoritmusok – kereskedik némi numerikus stabilitás és további beállítás. Ez a 4×4-es mátrix további beállítása sokkal több, mint a nagyobb szorzás elvégzésének költsége.
És most válaszoljon a kérdésére:
De vannak olyan algoritmusok, amelyek különösen hatékonyak az ilyen kicsi mátrixok esetén?
Nem, nincsenek algoritmusok, amelyek 4×4-es mátrix szorzásra lettek optimalizálva, mert az O (n 3 ) meglehetősen ésszerűen működik amíg el nem kezded találni, hogy hajlandó vagy egy nagy találatot elérni a rezsiért. A saját helyzetének függvényében előfordulhat olyan általános költség, amelyet előzőleg tudhat meg bizonyos dolgokról a mátrixairól (például, hogy bizonyos adatokat mennyire fognak újrafelhasználni), de a legkönnyebb dolog jó kódot írni az O (n 3 ) megoldást, hagyja, hogy a fordító kezelje, és később profilolja, hogy valóban a kód a mátrix szorzásának lassú foltja-e.
Kapcsolódó a Math.SE oldalon: A 4×4-es mátrix megfordításához minimálisan szükséges szorzások száma
Válasz
Gyakran az egyszerű algoritmusok a leggyorsabbak a nagyon kicsi halmazoknál, mivel a bonyolultabb algoritmusok általában valamilyen transzformációt alkalmaznak, amely némi rezsit ad. Úgy gondolom, hogy a legjobb fogadás nem egy hatékonyabb algoritmusra vonatkozik (azt hiszem, a legtöbb könyvtár egyszerű módszereket használ), hanem egy hatékonyabb megvalósításra, például egy SIMD kiterjesztéseket használó (x86 vagy amd64 kódot feltételező) vagy kézzel írt összeállításban . A memória elrendezését is jól át kell gondolni. Ehhez elegendő erőforrást kell találnia.
Válasz
A 4×4-es mat / mat matricák szorzásához az algoritmikus fejlesztések gyakran nem állnak rendelkezésre . Az alapvető köbös idők komplexitású algoritmus általában elég jól megy, és bármi, ami ennél jóval kedvezőbb, az inkább lebont, mint javítja az időket. Általánosságban elmondható, hogy a divatos algoritmusok nem megfelelőek, ha nincsenek benne skálázhatósági tényezők (például: megpróbálunk olyan tömböt sorba rendezni, amelynek mindig 6 eleme van, szemben az egyszerű beszúrással vagy buborék-rendezéssel). Az olyan dolgok, mint például a mátrix átültetése a referencia lokalitásának javítása érdekében, szintén nem segítik a referencia helyét, ha egy teljes mátrix elfér egy vagy két gyorsítótár sorban. Ebben a fajta miniatűr skálán, ha tömegesen 4×4-es szőnyeget / szőnyeget szorzol, a fejlesztések általában az utasítások és a memória mikroszintű optimalizálásából származnak, például a gyorsítótár-sor megfelelő igazításából.
Megjegyzések
- Remek válasz!
még soha nem hallottam a SoA rövidítésről (legalábbis hollandul ez egy rövidítés a ‘ seksueel overdraagbare aandoening ‘ ami ‘ nemi úton terjedő betegség ‘ … de ‘ s remélhetőleg nem arra gondolsz itt). A technika egyértelműnek tűnik, én ‘ még eléggé meglepődtem, hogy van ennek neve. Mit jelent a SoA?
alignas . Válasz
Ha pontosan tudja, hogy csak 4×4-et kell szoroznia mátrixok, akkor egyáltalán nem kell aggódnia egy általános algoritmus miatt. Csak két mutatót vehet be, és ezt használhatja:
(nagyon ajánlom ennek fordítását bizonyos automatizált módon).
A fordító ekkor optimális helyzetben van ennek a kódnak az optimalizálásához (részösszegek újrafelhasználásához, a matematika átrendezéséhez stb.), mivel mindent lát, nincsenek dinamikus hurkok és nincs vezérlési folyamat.
Nehéz elképzelni, hogy ez megverhető anélkül az intrinsics használatával.
Válasz
Nem lehet közvetlenül összehasonlítani az aszimptotikus összetettséget, ha a n -et másképp definiálja. Hozzászokott az algoritmusok bonyolultságának összehasonlításához olyan lapos adatszerkezeteken, mint például a listák, ahol n az elemek összes száma a listát, de a mátrix algoritmusok úgy definiálják, hogy a n csak egy oldal hosszának feleljen meg.
A n, ami olyan egyszerű, mint az egyes elemek egyszeri megnézése a kinyomtatás céljából, amit általában O (n) -nek gondolna, az O (n 2 ) . Ha a n -t definiálja a mátrix összes elemének számaként, azaz n = 16 egy 4×4-es mátrix esetében, akkor a naiv mátrix szorzása csak O (n 1,5 ), ami nagyon jó.
A legjobb megoldás a párhuzamosság előnyeinek kihasználása a SIMD utasítások vagy a GPU használatával, ahelyett, hogy megpróbálnád javítani az algoritmust azon a téves vélekedésen alapulva, hogy O (n 3 ) olyan rossz, mint ha a n lapos adatstruktúrához hasonlóan lenne meghatározva.
0 0 0 1. Ezért elkerülheti a szorzást ezzel a sorral.