Který algoritmus je účinný pro maticové násobení matic 4×4 afinních transformací

Wikipedia uvádí čtyři algoritmy pro násobení matic dvou matic nxn .

Klasický, který by programátor psal, je O (n ³ ) a je uveden jako „Násobení matice učebnice“. Ano. O (n ³ ) je trochu hit. Podívejme se na další nejlepší.

Strassenův algoritmus je O (n ^2,807 ). Tenhle by fungoval – má na to určitá omezení (například velikost je mocninou dvou) a má v popisu upozornění:

Ve srovnání s konvenčním násobením matic přidává algoritmus značnou pracovní zátěž O (n ² ) při sčítání / odčítání; takže pod určitou velikostí bude lepší použít konvenční násobení.

Pro ty, kteří se zajímají o tento algoritmus a jeho původ, podívejte se na Jak Strassen přišel s metodou násobení matic? může být dobrým čtením. Poskytuje náznak složitosti tohoto počátečního pracovního zatížení O (n ² ), které je přidáno, a proč by to bylo dražší než pouhé klasické násobení.

Takže to opravdu je O (n ² + n ^2.807 ) s tím bitem o tom, že nižší exponent n bude při psaní velkého O. ignorován. Zdá se, že pokud pracují na pěkné matici 2048×2048, to by mohlo být užitečné. U matice 4×4 to pravděpodobně bude pomalejší, protože ta režie jí celou dobu.

A pak je tu Coppersmith – Winograd algoritmus , který je O (n ^2.373 ) s několika vylepšeními. Přichází také s upozorněním:

Algoritmus Coppersmith – Winograd se často používá jako stavební kámen v jiných algoritmech k prokázání teoretických časových hranic. Na rozdíl od Strassenova algoritmu se však v praxi nepoužívá, protože poskytuje výhodu pouze maticím tak velkým, že nemohou být zpracovány moderním hardwarem.

Takže je lepší, když pracujete na super velkých maticích, ale opět to není užitečné pro matici 4×4.

To se opět odráží na stránce wikipedie v Maticové násobení: Subkubické algoritmy , které vysvětlují, proč věci běží rychleji:

Existují algoritmy, které poskytují lepší provozní časy než ty přímé. První objevený byl Strassenův algoritmus, který navrhl Volker Strassen v roce 1969 a který se často označuje jako „rychlé násobení matic“. Je založen na způsobu násobení dvou matic 2 × 2, který vyžaduje pouze 7 násobení (místo obvyklých 8), na úkor několika dalších operací sčítání a odčítání. Použitím této rekurzivně získáte algoritmus s multiplikativní cenou O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Strassenův algoritmus je složitější a numerická stabilita je ve srovnání s naivním algoritmem snížena, ale je rychlejší v případech, kdy n> 100 nebo tak nějak a objevuje se v několika knihovnách, například BLAS.

A to se dostává k jádru toho, proč jsou algoritmy rychlejší – vy kompromisujete nějaká numerická stabilita a nějaké další nastavení. Toto další nastavení pro matici 4×4 je mnohem více než náklady na více násobení.

A nyní, abych odpověděl na vaši otázku:

Existují však některé algoritmy, které jsou obzvláště účinné pro matice, které jsou malé?

Ne, neexistují žádné algoritmy optimalizované pro násobení matic 4×4, protože O (n ³ ) funguje docela rozumně dokud nezjistíte, že jste ochotni přijmout velký zásah za režii. Pro vaši konkrétní situaci může existovat nějaká režie, kterou byste mohli znát předem, abyste věděli konkrétní věci předem o svých matricích (například kolik dat bude znovu použito), ale opravdu nejjednodušší je napsat dobrý kód pro O (n ³ ) řešení, nechte to zpracovat kompilátorem a profilujte jej později, abyste zjistili, zda ve skutečnosti máte kód jako pomalé místo v násobení matice.

Související v Math.SE: K převrácení matice 4×4 je vyžadován minimální počet násobení

Jednoduché algoritmy jsou často nejrychlejší pro velmi malé sady, protože složitější algoritmy obvykle používají nějakou transformaci, která přidává určité režijní náklady. Myslím, že vaše nejlepší sázka není na efektivnějším algoritmu (myslím, že většina knihoven používá přímé metody), ale na efektivnější implementaci, například pomocí rozšíření SIMD (za předpokladu kódu x86 nebo amd64), nebo ručně psaného v sestavě . Také rozložení paměti by mělo být dobře promyšlené. V tomto ohledu byste měli být schopni najít dostatek zdrojů.

Pro násobení mat / mat 4×4 jsou často algoritmická vylepšení nedostupná. . Algoritmus základní složitosti v kubickém čase má tendenci se dařit docela dobře a vše, co je v tomto ohledu lepší, spíše degraduje než zlepšuje časy. Obecně platí, že vymyšlené algoritmy jsou nevhodné, pokud se nejedná o faktor škálovatelnosti (např. Pokus o rychlé řazení pole, které vždy má 6 prvků, na rozdíl od jednoduchého vložení nebo třídění bublin). věci, jako je maticová transpozice, aby se zlepšila referenční poloha, také skutečně nepomáhají referenční lokalitě, když se celá matice vejde do jednoho nebo dvou řádků vyrovnávací paměti. Pokud na tomto druhu miniaturní stupnice hromadně děláte násobení mat / mat 4×4, vylepšení obvykle pocházejí z mikroúrovňových optimalizací instrukcí a paměti, jako je správné zarovnání řádku do mezipaměti.

Komentáře

• Skvělá odpověď! Nikdy jsem neslyšel o zkratce SoA (alespoň v holandštině je to zkratka pro ‚ seksueel overdraagbare aandoening ‚ což znamená ‚ pohlavně přenosná nemoc ‚ … ale to ‚ doufejme, že ne to, co máte na mysli zde). Tato technika se zdá být jasná, jsem ‚ m dokonce docela překvapen, že pro ni existuje název. Co znamená SoA?
• @Ruben Struktura polí na rozdíl od polí struktur. SoAs mohou být také PITA – nejlépe uložené pro vaše nejdůležitější cesty. Zde ‚ je pěkný malý odkaz, který jsem na toto téma našel: stackoverflow.com/questions/17924705/…
• Možná budete chtít zmínit C ++ 11 / C11 alignas .

Pokud víte jistě, že budete muset znásobit pouze 4×4 matice, nemusíte si vůbec dělat starosti s obecným algoritmem. Stačí vzít dva ukazatele a použít toto:

(Důrazně doporučuji tento překlad překládat nějakým automatizovaným způsobem).

Kompilátor by pak byl optimálně umístěný k optimalizaci tohoto kódu (k opětovnému použití částečných součtů, změně pořadí matematiky atd.), protože vidí všechno, neexistují žádné dynamické smyčky a žádný kontrolní tok.

Těžko si lze představit, že toto lze překonat bez pomocí vnitřních prvků.

Nemůžete přímo porovnávat asymptotickou složitost, pokud definujete n odlišně. Jste zvyklí porovnávat složitost algoritmů na plochých datových strukturách, jako jsou seznamy, kde n je definován jako celkový počet prvků v seznam, ale maticové algoritmy definují n pouze jako délku jedné strany .

Podle této definice n, něco tak jednoduchého, jako když se na každý prvek podíváte jednou, abyste jej mohli vytisknout, což byste normálně považovali za O (n), je O (n ² ) . Pokud definujete n jako celkový počet prvků v matici, tj. N = 16 pro matici 4×4, pak je naivní násobení matice pouze O (n ^1,5 ), což je docela dobré.

Nejlepším řešením je využít výhod paralelismu pomocí pokynů SIMD nebo GPU, než se snažit vylepšit algoritmus založený na mylném přesvědčení, že O (n ³ ) je tak špatné, jak by to bylo, kdyby n byly definovány srovnatelně s plochou datovou strukturou.