Care algoritm este performant pentru multiplicarea matricială a matricilor 4×4 ale transformărilor afine

Wikipedia listează patru algoritmi pentru multiplicarea matricei a două matrice nxn .

Clasicul pe care un programator l-ar scrie este O (n ³ ) și este listat ca „Înmulțirea matricei manualului școlar”. Da. O (n ³ ) este un pic de succes. Să ne uităm la următorul cel mai bun.

Algoritmul Strassen este O (n ^2.807 ). Acesta ar funcționa – are anumite restricții (cum ar fi dimensiunea este o putere de două) și are o avertizare în descriere:

Comparativ cu înmulțirea matricii convenționale, algoritmul adaugă o cantitate considerabilă de lucru O (n ² ) în plus / scăderi; deci sub o anumită dimensiune, va fi mai bine să folosiți multiplicarea convențională.

Pentru cei care sunt interesați de acest algoritm și originile sale, uitându-se la Cum a venit Strassen cu metoda sa de multiplicare a matricei? poate fi o lectură bună. Oferă un indiciu asupra complexității volumului de lucru inițial O (n ² ) adăugat și de ce acest lucru ar fi mai scump decât simpla multiplicare clasică.

Deci, într-adevăr este O (n ² + n ^2.807 ), cu acel bit despre exponent inferior n ignorat atunci când scrieți O. mare. Se pare că dacă lucrează la o matrice frumoasă 2048×2048, acest lucru ar putea fi util. Pentru o matrice 4×4, probabil că o va găsi mai lentă, deoarece acea cheltuială mănâncă tot timpul.

Și apoi există Coppersmith – Winograd algoritm care este O (n ^2.373 ) cu destul de puțini îmbunătățiri. De asemenea, vine cu o avertizare:

Algoritmul Coppersmith – Winograd este frecvent utilizat ca element de construcție în alți algoritmi pentru a dovedi limitele teoretice ale timpului. Cu toate acestea, spre deosebire de algoritmul Strassen, acesta nu este utilizat în practică deoarece oferă doar un avantaj pentru matricile atât de mari încât nu pot fi procesat de hardware-ul modern.

Deci, este mai bine atunci când lucrați la matrici super mari, dar din nou, nu este util pentru o matrice 4×4.

Acest lucru se reflectă din nou în pagina „Wikipedia” din Înmulțirea matricei: algoritmi sub-cubici care ajunge la motivul pentru care lucrurile rulează mai repede:

Există algoritmi care pr prevede timpi de rulare mai buni decât cei simpli. Primul care a fost descoperit a fost algoritmul lui Strassen, conceput de Volker Strassen în 1969 și adesea denumit „multiplicare rapidă a matricei”. Se bazează pe o modalitate de a înmulți două matrici 2 × 2 care necesită doar 7 multiplicări (în loc de 8 obișnuit), în detrimentul mai multor operațiuni suplimentare de adunare și scădere. Aplicarea acestei recursive dă un algoritm cu un cost multiplicativ de O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Algoritmul lui Strassen este mai complex, iar stabilitatea numerică este redusă în comparație cu algoritmul naiv, dar este mai rapid în cazurile în care n> 100 sau cam asa ceva și apare în mai multe biblioteci, cum ar fi BLAS.

Și acest lucru ajunge la esența motivului pentru care algoritmii sunt mai rapizi – vă schimbați o oarecare stabilitate numerică și o configurare suplimentară. Această configurare suplimentară pentru o matrice 4×4 este mult mai mult decât costul de a face multiplicarea mai mare.

Și acum, pentru a răspunde la întrebarea dvs.:

Dar există câțiva algoritmi care sunt deosebit de eficienți pentru matrici atât de mici?

Nu, nu există algoritmi care sunt optimizați pentru multiplicarea matricii 4×4 deoarece O (n ³ ) funcționează destul de rezonabil până când începeți să constatați că sunteți dispus să luați o lovitură mare pentru cheltuieli generale. Pentru situația dvs. specifică, ar putea exista unele cheltuieli generale care ar putea duce la cunoașterea unor lucruri specifice în prealabil despre matricele dvs. (cum ar fi cât de multe date vor fi refolosite), dar într-adevăr cel mai ușor lucru de făcut este să scrieți un cod bun pentru O (n ³ ), lăsați compilatorul să o gestioneze și să o profilați mai târziu pentru a vedea dacă de fapt codul este punctul lent în înmulțirea matricei.

În legătură cu Math.SE: Numărul minim de înmulțiri necesare pentru a inversa o matrice 4×4

Adesea, algoritmii simpli sunt cei mai rapizi pentru seturi foarte mici, deoarece algoritmii mai complecși folosesc de obicei o transformare care adaugă o anumită cheltuială. Cred că cel mai bun pariu al tău nu este pe un algoritm mai eficient (cred că majoritatea bibliotecilor folosesc metode simple), ci pe o implementare mai eficientă, de exemplu, una care folosește extensii SIMD (presupunând codul x86 sau amd64), sau scrisă manual în asamblare . De asemenea, aspectul memoriei ar trebui să fie bine gândit. Ar trebui să puteți găsi resurse suficiente în acest sens.

Pentru multiplicarea 4×4 mat / mat, îmbunătățirile algoritmice sunt deseori . Algoritmul de bază al complexității timpului cubic tinde să se descurce destul de bine și orice altceva mai elegant decât acesta este mai probabil să se degradeze, decât să îmbunătățească timpii. Doar în general, algoritmii fanteziști nu sunt potriviți dacă nu este implicat un factor de scalabilitate (de exemplu: încercarea de a ordona rapid o matrice care întotdeauna are 6 elemente, spre deosebire de o inserție simplă sau sortare cu bule). lucruri precum transpunerea matricei aici pentru a îmbunătăți localitatea de referință, de asemenea, nu ajută de fapt localitatea de referință atunci când o întreagă matrice se poate încadra într-una sau două linii cache. La acest tip de scară miniaturală, dacă efectuați înmulțire 4×4 mat / mat, îmbunătățirile vor proveni, în general, din optimizări la nivel micro de instrucțiuni și memorie, cum ar fi alinierea corectă a liniei cache.

Comentarii

• Răspuns excelent! ‘ nu am auzit niciodată de acronimul SoA (cel puțin, în olandeză este un acronim pentru ‘ seksueel overdraagbare aandoening ‘ care înseamnă ‘ boală cu transmitere sexuală ‘ … dar că ‘ s sperăm că nu ceea ce vrei să spui aici). Tehnica pare clară, am ‘ chiar destul de surprins că există un nume pentru aceasta. Ce reprezintă SoA?
• @Ruben Structure of Arrays spre deosebire de Arrays of Structures. SoA-urile pot fi și PITA – cel mai bine salvate pentru căile dvs. cele mai critice. Aici ‘ un mic și frumos link pe care l-am găsit pe subiect: stackoverflow.com/questions/17924705/…
• Ați putea dori să menționați C ++ 11 / C11 alignas .

Dacă știți sigur că va trebui să multiplicați doar 4×4 matrice, atunci nu trebuie să vă faceți griji cu privire la un algoritm general. Puteți pur și simplu să luați două indicatoare și să utilizați acest lucru:

(aș recomanda cu tărie traducerea în mod automat).

Compilatorul ar fi apoi poziționat optim pentru a optimiza acest cod (pentru a reutiliza sume parțiale, reordona matematica etc.) deoarece poate vedea totul, nu există bucle dinamice și nici un flux de control.

Greu de imaginat că acest lucru poate fi învins fără folosind elemente intrinseci.

Nu puteți compara direct complexitatea asimptotică dacă definiți diferit n. Sunteți obișnuiți să comparați complexitatea algoritmilor pe structuri de date plane, cum ar fi liste, unde n este definit ca fiind numărul total de elemente din lista, dar algoritmii matricei definesc n ca fiind doar lungimea unei fețe .

Prin această definiție a n, ceva la fel de simplu ca să te uiți la fiecare element o singură dată pentru a-l tipări, ceea ce ai crede în mod normal ca O (n), este O (n ² ) . Dacă definiți n ca numărul total de elemente din matrice, adică n = 16 pentru o matrice 4×4, atunci multiplicarea naivă a matricei este doar O (n ^1.5 ), care este destul de bun.

Cel mai bun pariu este să profitați de paralelism utilizând instrucțiuni SIMD sau un GPU, mai degrabă decât să încercați să îmbunătățiți algoritmul pe baza credinței greșite că O (n ³ ) este la fel de rău ar fi dacă n ar fi definit comparabil cu o structură de date plană.