Perché matrici di permutazione vengono utilizzati per scambiare le righe di una matrice?

Question

Quali sono i vantaggi di utilizzare una matrice di permutazione a righe di swap? Perché si potrebbe creare una matrice di permutazione e poi applicare una moltiplicazione matrice, è più facile e più efficace di un semplice scambio righe con un ciclo?

Answer 1

matrici di permutazione sono un'utile astrazione matematica, in quanto consentono l'analisi utilizzando le normali regole di matriciale, senza dover introdurre un altro tipo di operazione.

Nel software, buone implementazioni non memorizzare una matrice di permutazione come matrice completa, immagazzinano una matrice di permutazione e si applicano direttamente (senza una moltiplicazione matrice completa).

A seconda delle dimensioni delle matrici e le operazioni ed i modelli di accesso coinvolti, può essere più conveniente di non applicare la permutazione ai dati in memoria a tutti, ma solo per usarlo come un riferimento indiretto in più. Così, quando si richiede (P * M)(i,j), dove P è una matrice di permutazione e M è qualche altra matrice che si sta permutando, i dati non devono essere ri-arrangiati a tutti, ma piuttosto l'operazione di accesso elemento sarà cercare la riga permutato quando l'accesso l'elemento.

Answer 2

La prima cosa che mi viene in mente è la questione denominata "località spaziale". tecnologie caching per scontato che se una posizione di memoria si accede, è probabile accedere ai luoghi della memoria nelle vicinanze. In alcuni linguaggi di programmazione, elementi in righe sono vicini, mentre gli elementi in colonne sono vicini in altri. Dipende dalla realizzazione. Credo matrici di permutazione sono progettati per risolvere questo problema, in quanto l'ottimizzazione della matrice di moltiplicazione è uno dei problemi che gli algoritmi accademico lavora principalmente sul miglioramento. Struttura semplice ciclo non sarà in grado di fare uso di tecnologie di cache per migliorare le prestazioni.