Mikä algoritmi on suorituskykyinen affiniaalimuunnosten 4×4-matriisien matriisikertoimelle

Wikipedia listaa neljä algoritmia kahden nxn-matriisin matriisikertomukselle .

Klassinen, jonka ohjelmoija kirjoittaa, on O (n ³ ) ja se on lueteltu ”koulukirjan matriisikertona”. Jep. O (n ³ ) on vähän osuma. Katsotaan seuraavaksi parasta.

Strassen-algoritmi on O (n ^2.807 ). Tämä toimisi – sillä on sille joitain rajoituksia (kuten koko on kahden teho) ja kuvauksessa on varoitus:

Verrattuna tavanomaiseen matriisikertomukseen algoritmi lisää huomattavan O (n ² ) -kuormituksen lisäysten / vähennysten lisäksi; Joten tietyn koon alapuolella on parempi käyttää tavanomaista kertolaskua.

Niille, jotka ovat kiinnostuneita tästä algoritmista ja sen alkuperästä, katsovat Kuinka Strassen keksi matriisikertomenetelmänsä? voi olla hyvä luku. Se antaa vihjeen lisätyn alkuperäisen O (n ² ) -kuormituksen monimutkaisuudesta ja siitä, miksi se olisi kalliimpaa kuin vain perinteisen kertolasku.

Joten se todella on O (n ² + n ^2.807 ), sillä pienempi eksponentti n jätetään huomiotta kirjoitettaessa isoa O: ta. Vaikuttaa siltä, että jos työskentelevät mukavan 2048×2048-matriisin kanssa, tämä voi olla hyödyllistä. 4×4-matriisin kohdalla se todennäköisesti löytää sen hitaammin, kun yläpuoli syö koko toisen ajan.

Ja sitten siellä on Coppersmith – Winograd algoritmi , joka on O (n ^2.373 ) ja melko vähän parannuksia. Siinä on myös varoitus:

Coppersmith – Winograd-algoritmia käytetään usein rakennuspalikkana muissa algoritmeissa teoreettisten aikarajojen osoittamiseksi. Toisin kuin Strassen-algoritmi, sitä ei kuitenkaan käytetä käytännössä, koska se tarjoaa edun vain niin suurille matriiseille, etteivät ne voi käsitellä nykyaikaisella laitteistolla.

Joten, se on parempi, kun työskentelet erittäin suurten matriisien parissa, mutta se ei taaskaan ole hyödyllinen 4×4-matriisille.

Tämä näkyy jälleen wikipedian sivulla Matriisikertaus: Alikuutioiset algoritmit , joka saa selville miksi asiat käyvät nopeammin:

On olemassa algoritmeja, joiden mukaan pr ylittää paremmat ajoajat kuin suorat. Ensimmäisenä löydettiin Strassenin algoritmi, jonka Volker Strassen suunnitteli vuonna 1969 ja jota kutsutaan usein nimellä ”nopea matriisin kertolasku”. Se perustuu kahden 2 × 2-matriisin kertomistapaan, joka vaatii vain 7 kertolaskua (eikä tavallinen 8) useiden lisä- ja vähennysoperaatioiden kustannuksella. Tämän rekursiivisella soveltamisella saadaan algoritmi, jonka O-kertomuskerroin (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Strassenin algoritmi on monimutkaisempi ja numeerinen vakaus pienenee verrattuna naiiviin algoritmiin, mutta se on nopeampaa tapauksissa, joissa n> 100 tai niin ja esiintyy useissa kirjastoissa, kuten BLAS.

Ja siitä tulee ydin miksi algoritmit ovat nopeampia – vaihdat jonkin verran numeerista vakautta ja joitain lisäasetuksia. Tämä 4×4-matriisin lisäasetus on paljon enemmän kuin kustannukset, joita saadaan suuremman kertolaskun suorittamisesta.

Ja nyt, vastaamaan kysymykseesi:

Mutta onko olemassa joitain algoritmeja, jotka ovat erityisen tehokkaita pienille matriiseille?

Ei, ei ole algoritmeja, jotka olisi optimoitu 4×4-matriisikertoja varten, koska O (n ³ ) toimii melko kohtuullisesti kunnes alat huomata olevasi valmis ottamaan iso osuman yleiskustannuksiin. Erityistilanteessasi saattaa olla jonkin verran ylimääräisiä kustannuksia, joita saatat tuntea tietyistä matriiseista etukäteen (kuten kuinka paljon tietoja käytetään uudelleen), mutta todella helpoin asia on kirjoittaa hyvä koodi O: lle (n ³ ) -ratkaisu, anna kääntäjän hoitaa se ja profiloida se myöhemmin nähdäksesi, onko koodi tosiasiassa matriisin kertomisen hidas kohta.

Liittyy Math.SE: hen: 4×4-matriisin kääntämiseen vaadittava vähimmäismäärä kertoja

Yksinkertaiset algoritmit ovat nopeimpia hyvin pienille joukkoille, koska monimutkaisemmissa algoritmeissa käytetään yleensä jonkinlaista muunnosta, joka lisää jonkin verran yleiskustannuksia. Mielestäni paras panoksesi ei ole tehokkaammasta algoritmista (mielestäni useimmat kirjastot käyttävät yksinkertaisia menetelmiä), mutta tehokkaammasta toteutuksesta, esimerkiksi SIMD-laajennuksia käyttävästä (olettaen x86- tai amd64-koodi) tai käsin kirjoitetusta kokoonpanossa . Myös muistin asettelun tulisi olla hyvin harkittu. Sinun pitäisi pystyä löytämään tarpeeksi resursseja tähän.

4×4-matto / matto-kertolaskujen tapauksessa algoritmiset parannukset ovat usein poissa käytöstä . Kuutio-ajan monimutkaisuuden perusalgoritmilla on taipumus menestyä melko hyvin, ja mikä tahansa mielikuvituksellisempi hajoaa todennäköisemmin kuin parantaa aikoja. Yleisesti ottaen hienot algoritmit eivät sovi, jos niihin ei liity skaalautuvuustekijää (esim. Yritetään pikalajitella matriisi, jossa aina on 6 elementtiä yksinkertaisen lisäys- tai kuplalajittelun sijaan). esimerkiksi matriisitransponointi referenssipaikan parantamiseksi eivät myöskään auta viitekohdetta, kun koko matriisi mahtuu yhteen tai kahteen välimuistilinjaan. Jos teet tällaisessa pienoiskoossa, 4×4-maton / maton kertomista massaan, parannukset tulevat yleensä ohjeiden ja muistin mikrotason optimoinnista, kuten oikea välimuistirivien kohdistus.

Kommentit

• Hyvä vastaus! En ole ’ koskaan kuullut SoA-lyhenteestä (ainakin hollanniksi se on lyhenne sanoista ’ seksueel overdraagbare aandoening ’ mikä tarkoittaa ’ sukupuoliteitse tarttuvaa tautia ’ … mutta ’ toivottavasti ei sitä, mitä tarkoitat täällä). Tekniikka näyttää selvältä, olen jopa yllättynyt siitä, että sille on oma nimi,

Jos tiedät varmasti, että sinun tarvitsee vain kertoa 4×4 matriiseja, sinun ei tarvitse huolehtia yleisestä algoritmista. Voit vain ottaa kaksi osoitinta ja käyttää tätä:

(Suosittelen vahvasti tämän kääntämistä automatisoidulla tavalla).

Tällöin kääntäjä olisi optimaalisesti sijoitettu tämän koodin optimointiin (osittaisten summien uudelleenkäyttöön, matematiikan järjestämiseen jne.), koska se näkee kaiken, ei ole dynaamisia silmukoita eikä ohjausvirtaa.

On vaikea kuvitella, että tämä voidaan voittaa ilman sisäisten ominaisuuksien avulla.