配列の行を交換するために順列行列が使用されるのはなぜですか？

Question

順列行列を使用して行を交換することの利点は何ですか？順列行列を作成し、マトリックスの乗算を適用する理由は、forループで行を交換するよりも簡単で効率的ですか？

Answer 1

順列行列は、別のタイプの操作を導入することなく、マトリックス代数の通常のルールを使用した分析を許可するため、有用な数学的抽象化です。

ソフトウェアでは、適切な実装は順列マトリックスを完全なマトリックスとして保存せず、順列アレイを保存し、直接適用します（完全なマトリックスの乗算なし）。

マトリックスのサイズと関連する操作とアクセスパターンに応じて、メモリ内のデータに順列をまったく適用せずに、追加の間接として使用する方が安価な場合があります。だから、あなたが要求するとき (P * M)(i,j), 、 どこ P 順列行列です M あなたが順番にしている他のいくつかのマトリックスは、データをまったく再配置する必要はありませんが、むしろ要素にアクセスすると、要素アクセス操作が順列の行を検索します。

Answer 2

私の頭に浮かぶ最初のことは、「Spatial Locality」と呼ばれる問題です。キャッシュテクノロジーは、メモリの場所にアクセスすると、メモリの近くの場所にアクセスする可能性があると想定しています。一部のプログラミング言語では、行の要素は隣人ですが、列の要素は他の隣の隣人です。実装に依存します。マトリックスの乗算の最適化は、アルゴリズムの学界が主に改善に取り組んでいる問題の1つであるため、順列行列はこの問題を解決するように設計されていると思います。シンプルなループ構造は、パフォーマンスを向上させるためにキャッシュテクノロジーを利用することができません。