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

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

Quello classico che un programmatore scriverebbe è O (n ³ ) ed è indicato come “Moltiplicazione della matrice Schoolbook”. Sì. O (n ³ ) è un po un successo. Vediamo il prossimo migliore.

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

Rispetto alla moltiplicazione di matrici convenzionale, lalgoritmo aggiunge un considerevole carico di lavoro O (n ² ) in aggiunta / sottrazione; quindi al di sotto di una certa dimensione, sarà meglio usare la moltiplicazione convenzionale.

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

Quindi è davvero è O (n ² + n ^2.807 ) con quel bit sullesponente inferiore n ignorato quando si scrive una O grande. Sembra che se si stanno lavorando su una bella matrice 2048×2048, questo potrebbe essere utile. Per una matrice 4×4, probabilmente la troverà più lenta poiché il sovraccarico consuma tutto il resto.

E poi cè il Coppersmith – Winograd algoritmo che è O (n ^2.373 ) con alcuni miglioramenti. Inoltre è dotato di un avvertimento:

Lalgoritmo Coppersmith – Winograd viene spesso utilizzato come elemento costitutivo in altri algoritmi per dimostrare limiti di tempo teorici. Tuttavia, a differenza dellalgoritmo di Strassen, non viene utilizzato nella pratica perché fornisce solo un vantaggio per matrici così grandi che non possono essere elaborato da hardware moderno.

Quindi, è meglio quando lavori su matrici molto grandi, ma ancora una volta, non è utile per una matrice 4×4.

Ciò si riflette di nuovo nella pagina di wikipedia in Moltiplicazione di matrici: algoritmi subcubici che spiega perché le cose funzionano più velocemente:

esistono algoritmi che pr ovide tempi di esecuzione migliori rispetto a quelli semplici. Il primo ad essere scoperto è stato lalgoritmo di Strassen, ideato da Volker Strassen nel 1969 e spesso indicato come “moltiplicazione rapida di matrici”. Si basa su un modo di moltiplicare due matrici 2 × 2 che richiede solo 7 moltiplicazioni (invece di il solito 8), a scapito di diverse operazioni addizionali di addizione e sottrazione. Applicando ricorsivamente si ottiene un algoritmo con un costo moltiplicativo di O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Lalgoritmo di Strassen è più complesso e la stabilità numerica è ridotta rispetto allalgoritmo ingenuo, ma è più veloce nei casi in cui n> 100 o giù di lì e appare in diverse librerie, come BLAS.

E questo arriva al nocciolo del motivo per cui gli algoritmi sono più veloci: devi fare dei compromessi una certa stabilità numerica e alcune impostazioni aggiuntive. Questa configurazione aggiuntiva per una matrice 4×4 è molto più del costo per eseguire più moltiplicazioni.

E ora, per rispondere alla tua domanda:

Ma esistono algoritmi particolarmente efficienti per matrici così piccole?

No, non ci sono algoritmi ottimizzati per la moltiplicazione di matrici 4×4 perché quello O (n ³ ) funziona abbastanza ragionevolmente finché non inizi a scoprire che sei disposto a prendere un grosso colpo per le spese generali. Per la tua situazione specifica, potrebbe esserci un sovraccarico che potresti sostenere conoscendo in anticipo cose specifiche sulle tue matrici (come quanti dati 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 profilalo in seguito per vedere se il codice è effettivamente il punto lento nella moltiplicazione di matrici.

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

Spesso, gli algoritmi semplici sono i più veloci per insiemi molto piccoli, perché gli algoritmi più complessi di solito usano alcune trasformazioni che aggiungono un po di overhead. Penso che la tua scommessa migliore non sia su un algoritmo più efficiente (penso che la maggior parte delle librerie usi metodi semplici), ma su unimplementazione più efficiente, ad esempio, una che utilizza estensioni SIMD (assumendo codice x86 o amd64) o scritta a mano in assembly . Inoltre, il layout della memoria dovrebbe essere ben pensato. Dovresti essere in grado di trovare risorse sufficienti su questo.

Per la moltiplicazione mat / mat 4×4, i miglioramenti algoritmici sono spesso fuori . Lalgoritmo di complessità del tempo cubico di base tende ad andare abbastanza bene, e qualsiasi cosa più elaborata ha maggiori probabilità di degradare piuttosto che migliorare i tempi. In generale, algoritmi fantasiosi non sono adatti se non è coinvolto “un fattore di scalabilità (es: cercare di classificare rapidamente un array che sempre ha 6 elementi invece di un semplice inserimento o di un bubble sort). cose come la trasposizione della matrice qui per migliorare la località di riferimento inoltre non aiutano effettivamente la località di riferimento quando unintera matrice può stare in una o due linee di cache. In questo tipo di scala in miniatura, se si esegue la moltiplicazione 4×4 mat / mat in massa, i miglioramenti verranno generalmente da ottimizzazioni a livello micro delle istruzioni e della memoria, come il corretto allineamento della riga della cache.

Commenti

• Ottima risposta! ‘ non ho mai sentito parlare dellacronimo SoA (almeno, in olandese è lacronimo di ‘ seksueel overdraagbare aandoening ‘ che significa ‘ malattia a trasmissione sessuale ‘ … ma che ‘ spero non sia quello che intendi qui). La tecnica sembra chiara, ‘ sono anche abbastanza sorpreso che ci sia un nome. Cosa significa SoA?
• @Ruben Structure of Arrays in contrapposizione a Arrays of Structures. I SoA possono anche essere PITA, meglio salvati per i percorsi più critici. Ecco ‘ un bel link che ho trovato sullargomento: stackoverflow.com/questions/17924705/…
• Potresti menzionare C ++ 11 / C11 alignas .

Se sai per certo che dovrai moltiplicare solo 4×4 matrici, quindi non devi preoccuparti affatto di un algoritmo generale. Puoi semplicemente prendere due puntatori e utilizzare questo:

(consiglio vivamente di tradurla in modo automatico).

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

utilizzando gli intrinseci.

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 semplici come elenchi, dove n è definito come il numero totale di elementi in lelenco, ma gli algoritmi di matrice definiscono n solo la lunghezza di un lato .

Con questa definizione di n, qualcosa di semplice come guardare ogni elemento una volta per stamparlo, quello che normalmente penseresti come O (n), è O (n ² ) . Se definisci n come il numero totale di elementi nella matrice, ovvero n = 16 per una matrice 4×4, la moltiplicazione della matrice naïve è solo O (n ^1,5 ), che è abbastanza buono.

La soluzione migliore è sfruttare il parallelismo utilizzando le istruzioni SIMD o una GPU, piuttosto che provare a migliorare lalgoritmo basandosi sullerrata convinzione che O (n ³ ) sia così grave come sarebbe se n fosse definito in modo paragonabile a una struttura di dati piatta.