¿Por qué las matrices de permutación se utilizan para intercambiar filas de una matriz?

Question

¿Cuáles son las ventajas de usar una matriz de permutación para intercambiar filas? ¿Por qué uno crearía una matriz de permutación y luego aplicaría una multiplicación de matrices? ¿Es más fácil y más eficiente que simplemente intercambiar filas con un ciclo for?

Answer 1

Las matrices de permutación son una abstracción matemática útil, ya que permiten el análisis utilizando las reglas normales del álgebra matricial, sin tener que introducir otro tipo de operación.

En el software, las buenas implementaciones no almacenan una matriz de permutación como una matriz completa, almacenan una matriz de permutación y la aplican directamente (sin una multiplicación de matriz completa).

Dependiendo de los tamaños de las matrices y las operaciones y los patrones de acceso implicados, puede ser más barato no aplicar la permutación a los datos en la memoria, sino simplemente usarla como una indirección adicional. Entonces, cuando solicite (P * M)(i,j), donde P es una matriz de permutación y M es otra matriz que está permutando, los datos no necesitan ser reorganizados en absoluto, sino que la operación de acceso al elemento buscará la fila permutada cuando acceda el elemento.

Answer 2

Lo primero que me viene a la mente es el problema llamado "localidad espacial". Las tecnologías de almacenamiento en caché asumen que si se accede a una ubicación de memoria, es probable acceder a las ubicaciones cercanas de la memoria. En algunos lenguajes de programación, los elementos en las filas son vecinos, mientras que los elementos en las columnas son vecinos en los demás. Depende de la implementación. Supongo que las matrices de permutación están diseñadas para resolver este problema, ya que la optimización de la multiplicación de matrices es uno de los problemas que los algoritmos académicos principalmente trabajan para mejorar. La estructura de bucle simple no podrá usar tecnologías de caché para mejorar el rendimiento.