¿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 matriz, ¿es más fácil y más eficiente que simplemente intercambiar filas con un bucle 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 de matriz, 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 involucrados, puede ser más barato no aplicar la permutación a los datos en la memoria, sino solo usarlo como una indirección adicional. Entonces, cuando solicitas (P * M)(i,j), dónde P es una matriz de permutación y M Es alguna otra matriz que está permitiendo, los datos no necesitan ser reorganizados en absoluto, sino que la operación de acceso al elemento buscará la fila permutada cuando acceda al elemento.

Answer 2

Lo primero que me viene a la mente es el problema llamado "localidad espacial". Las tecnologías de almacenamiento en caché suponen 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 de otros. 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 matriz es uno de los problemas que los algoritmos de la academia trabajan principalmente en mejorar. La estructura de bucle simple no podrá utilizar las tecnologías de caché para mejorar el rendimiento.