Warum werden Permutationsmatrizen verwendet, um die Reihen eines Arrays auszutauschen?

Question

Was sind die Vorteile der Verwendung einer Permutationsmatrix, um Zeilen auszutauschen? Warum würde man eine Permutationsmatrix erstellen und dann eine Matrixmultiplikation anwenden, ist es einfacher und effizienter, als nur die Zeilen mit einer für die Schleife auszutauschen?

Answer 1

Permutationsmatrizen sind eine nützliche mathematische Abstraktion, da sie eine Analyse unter Verwendung der normalen Regeln der Matrixalgebra ermöglichen, ohne eine andere Art von Betrieb einzuführen.

In der Software speichern gute Implementierungen keine Permutationsmatrix als vollständige Matrix, sie speichern ein Permutations -Array und wenden sie direkt an (ohne eine vollständige Matrixmultiplikation).

Abhängig von den Größen der Matrizen und den beteiligten Operationen und Zugriffsmustern kann es billiger sein, die Permutation nicht auf die Daten im Speicher anzuwenden, sondern nur als zusätzliche Indirektion zu verwenden. Also, wenn Sie anfordern (P * M)(i,j), wo P ist eine Permutationsmatrix und M Ist eine andere Matrix, die Sie durchdringen, die Daten müssen überhaupt nicht neu arrangiert werden, sondern der Elementzugriffsvorgang sucht die permutierte Zeile nach, wenn Sie auf das Element zugreifen.

Answer 2

Das erste, was mir in den Sinn kommt, ist das Problem, das als "räumliche Lokalität" bezeichnet wird. Caching -Technologien gehen davon aus, dass es wahrscheinlich ist, dass auf einen Speicherort auf den Speicherstandorten zugreifen kann. In einigen Programmiersprachen sind Elemente in Reihen Nachbarn, während Elemente in Säulen in anderen Nachbarn sind. Es hängt von der Implementierung ab. Ich denke, Permutationsmatrizen sollen dieses Problem lösen, da die Optimierung der Matrixmultiplikation eines der Probleme ist, die die Algorithmen die Akademie hauptsächlich zur Verbesserung bewirken. Eine einfache Schleifenstruktur kann keine Cache -Technologien verwenden, um die Leistung zu verbessern.