Quale algoritmo è performante per la moltiplicazione di matrici 4x4 di trasformazioni affini

Wikipedia elenca quattro algoritmi per moltiplicazione di matrice di due matrici nxn .

Quello classico che un programmatore dovrebbe scrivere è O (n ³ ) ed è elencato come "moltiplicazione della matrice scolastica". Sì. O (n ³ ) è un po 'un successo. Diamo un'occhiata al prossimo migliore.

L'algoritmo Strassen è O (n ^2.807 ). Questo funzionerebbe - ha alcune restrizioni (come la dimensione è una potenza di due) e ha un avvertimento nella descrizione:

Compared to conventional matrix multiplication, the algorithm adds a considerable O(n²) workload in addition/subtractions; so below a certain size, it will be better to use conventional multiplication.

Per coloro che sono interessati a questo algoritmo e alle sue origini, guardando In che modo Strassen ha trovato il suo metodo di moltiplicazione della matrice? può essere una buona lettura. Fornisce un suggerimento sulla complessità del carico di lavoro iniziale di O (n ² ) che viene aggiunto e sul motivo per cui ciò sarebbe più costoso della semplice moltiplicazione classica.

Quindi è davvero O (n ² + n ^2.807 ) con quel bit su esponente inferiore n che viene ignorato quando si scrive grande O Sembra che se stai lavorando su una bella matrice 2048x2048, questo potrebbe essere utile. Per una matrice 4x4, probabilmente lo troverà più lento man mano che l'overhead si mangerà tutto il resto.

E poi c'è l'algoritmo Coppersmith-Winograd che è O (n ^2.373 ) con alcuni piccoli miglioramenti. Inoltre viene fornito un avvertimento:

The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds. However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.

Quindi, è meglio quando lavori su matrici super grandi, ma ancora, non utile per una matrice 4x4.

Questo si riflette di nuovo nella pagina di wikipedia in Matrix moltiplicazione: algoritmi sub-cubici che arriva al perché le cose girano più velocemente:

Algorithms exist that provide better running times than the straightforward ones. The first to be discovered was Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication". It is based on a way of multiplying two 2 × 2-matrices which requires only 7 multiplications (instead of the usual 8), at the expense of several additional addition and subtraction operations. Applying this recursively gives an algorithm with a multiplicative cost of O(n^log₂7) ≈ O(n^2.807). Strassen's algorithm is more complex, and the numerical stability is reduced compared to the naïve algorithm, but it is faster in cases where n > 100 or so and appears in several libraries, such as BLAS.

E questo è il motivo principale per cui gli algoritmi sono più veloci - si scambiano stabilità numerica e alcune impostazioni aggiuntive. Quella configurazione aggiuntiva per una matrice 4x4 è molto più del costo di fare più moltiplicazione.

E ora, per rispondere alla tua domanda:

But are there some algorithms that are especially efficient for matrices that small?

No, non ci sono algoritmi ottimizzati per la moltiplicazione delle matrici 4x4 perché O (n ³ ) funziona abbastanza ragionevolmente finché non inizi a scoprire che sei disposto a prendere un grande colpisci per sovraccarico. Per la tua situazione specifica, potrebbe esserci un sovraccarico che potresti affrontare conoscendo cose specifiche in anticipo sulle tue matrici (come la quantità di dati che verranno riutilizzati), ma in realtà la cosa più semplice da fare è scrivere un buon codice per O (n ³ ), lascia che sia il compilatore a gestirlo e analizzalo in un secondo momento per vedere se effettivamente il codice è il punto lento nella moltiplicazione della matrice.

Relativo a Math.SE: Numero minimo di moltiplicazioni richieste per invertire una matrice 4x4

Spesso, gli algoritmi semplici sono i più veloci per insiemi molto piccoli, perché solitamente algoritmi più complessi utilizzano alcune trasformazioni che aggiungono un sovraccarico. Penso che la soluzione migliore non sia un algoritmo più efficiente (penso che la maggior parte delle librerie utilizzi metodi diretti), ma su un'implementazione più efficiente, ad esempio, l'utilizzo di estensioni SIMD (supponendo codice x86 o amd64) o scritto a mano in assembly . Inoltre, il layout della memoria dovrebbe essere ben pensato. Dovresti riuscire a trovare abbastanza risorse su questo.

Per la moltiplicazione mat / mat 4x4, i miglioramenti algoritmici sono spesso fuori. L'algoritmo di base della complessità in termini di tempo cubico tende a fare abbastanza bene, e qualsiasi cosa più divertente di quella è più probabile che si degradi piuttosto che migliorare i tempi. Solo in generale, gli algoritmi elaborati non sono adatti se non è coinvolto un fattore di scalabilità (ad es. Cercando di eseguire una quicksort su un array che always ha 6 elementi rispetto a un semplice inserimento o bubble sort). Fare cose come la trasposizione delle matrici qui per migliorare la localizzazione di riferimento, inoltre, non aiuta effettivamente la localizzazione di riferimento quando un'intera matrice può inserirsi in una o due linee di cache. Con questo tipo di scala in miniatura, se si sta facendo una moltiplicazione di mat 4x mat / mat in massa, i miglioramenti derivano in genere dalle ottimizzazioni a livello micro delle istruzioni e della memoria, come un corretto allineamento della cache line.

Se sai per certo che dovrai solo moltiplicare le matrici 4x4, allora non dovrai assolutamente preoccuparti di un algoritmo generale. Puoi solo prendere due suggerimenti e usarlo:

(Consiglio vivamente di tradurre questo in modo automatico).

Il compilatore sarebbe quindi posizionato in modo ottimale per ottimizzare questo codice (per riutilizzare somme parziali, riordinare i calcoli matematici ecc.) in quanto può vedere tutto, non ci sono loop dinamici e nessun flusso di controllo.

Difficile immaginare che questo possa essere battuto senza usare intrinseche.

Non puoi confrontare direttamente la complessità asintotica se definisci n in modo diverso. sei abituato a confrontare la complessità degli algoritmi su strutture di dati piatte come le liste, dove n è definita come numero totale di elementi nell'elenco, ma gli algoritmi della matrice definiscono n come la sola lunghezza di un lato .

Con questa definizione di n , qualcosa di semplice come guardare ogni elemento una volta per stamparlo, ciò che normalmente penseresti come O (n), è O (n ² ). Se definisci n come numero totale di elementi nella matrice, cioè n = 16 per una matrice 4x4, allora la moltiplicazione della matrice naïve è solo O (n ^1.5 ), che è piuttosto buona.

La cosa migliore è sfruttare il parallelismo usando le istruzioni SIMD o una GPU, piuttosto che provare a migliorare l'algoritmo basandosi sulla convinzione errata che O (n ³ ) sia così male sarebbe se n fosse definito in modo comparabile a una struttura di dati piatta.