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

Question

行を入れ替えるために置換行列を使用する利点は何ですか？置換行列を作成してから行列の乗算を適用するのはなぜですか？行をforループで交換するよりも簡単で効率的ですか？

Answer 1

置換行列は、別のタイプの操作を導入することなく、行列代数の通常の規則を使用して分析できるため、有用な数学的抽象化です。

ソフトウェアでは、優れた実装は順列行列を完全な行列として格納せず、順列配列を格納し、それを直接適用します（完全な行列の乗算なしで）。

行列のサイズ、関連する操作およびアクセスパターンによっては、メモリ内のデータに順列を適用せずに、追加の間接参照として使用する方が安価な場合があります。したがって、を要求する(P * M)(i,j)と、Pは置換行列であり、は置換しMている他の行列です。データを再配置する必要はありませんが、要素にアクセスすると、要素アクセス操作によって置換された行が検索されます。

Answer 2

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