Pourquoi les matrices de permutation sont utilisés pour les lignes de swap d'un tableau?

Question

Quels sont les avantages de l'utilisation d'une matrice de permutation à des lignes de swap? Pourquoi on va créer une matrice de permutation, puis appliquer une multiplication matricielle, est-il plus facile et plus efficace qu'une simple permutation des lignes avec une boucle?

Answer 1

matrices Permutation sont une abstraction mathématique utile, car ils permettent une analyse en utilisant les règles normales de l'algèbre matricielle, sans avoir à introduire un autre type d'opération.

Dans le logiciel, les bonnes implémentations ne stockent pas une matrice de permutation comme une matrice complète, ils stockent une matrice de permutation et ils appliquent directement (sans une multiplication de matrice complète).

En fonction de la taille des matrices et des opérations et des modèles d'accès impliqués, il peut être moins cher de ne pas appliquer la permutation des données en mémoire du tout, mais juste pour l'utiliser comme une indirection supplémentaire. Donc, lorsque vous demandez (P * M)(i,j), où P est une matrice de permutation et M est une autre matrice que vous permutant, les données ne doivent pas être réagencées du tout, mais plutôt l'opération d'accès de l'élément recherchera la ligne permutée lorsque vous accédez l'élément.

Answer 2

La première chose qui me vient à l'esprit est la question appelée « localisation spatiale ». technologies supposent que si la mise en cache un emplacement de mémoire est accessible, il est probable d'accéder aux localités voisines de la mémoire. Dans certains langages de programmation, des éléments en lignes sont voisins tandis que les éléments dans les colonnes sont voisins dans d'autres. Cela dépend de la mise en œuvre. Je suppose que les matrices de permutation sont conçus pour résoudre ce problème, étant donné que l'optimisation de la multiplication de la matrice est l'un des problèmes que les algorithmes du monde universitaire travaille principalement sur l'amélioration. structure simple boucle ne sera pas en mesure d'utiliser des technologies de cache pour améliorer les performances.