4人のロシア人の方法

コンピュータサイエンスにおいて、4人のロシア人法とは、ブール行列を含むアルゴリズム、またはより一般的には、各セルが限られた数のみの可能な値を取ることができる行列を含むアルゴリズムを高速化する手法です。

この方法の主なアイデアは、何らかのパラメータtに対して行列をt × tのサイズの小さな正方形ブロックに分割し、ルックアップ テーブルを使用して各ブロック内でアルゴリズムを迅速に実行することです。ルックアップ テーブルのインデックスは、アルゴリズムの何らかの操作の前にブロック境界の左上にある行列セルの値をエンコードし、ルックアップ テーブルの結果は、操作後にブロックの右下にある境界セルの値をエンコードします。したがって、全体的なアルゴリズムは、n ²個の行列セルではなく、 ( n / t ) ²個のブロックのみを操作することで実行できます。ここで、nは行列の辺の長さです。ルックアップ テーブルのサイズ (およびそれらを初期化するために必要な時間) を十分に小さく保つために、tは通常、 O (log n )に選択されます。

4 つのロシア人の方法を適用できるアルゴリズムには次のものがあります。

• グラフの推移閉包を計算する、
• ブール行列乗算、
• 距離計算を編集、
• 配列アライメント、
• バイナリの乱雑なパターンマッチングのためのインデックス計算。

いずれの場合も、アルゴリズムの速度は 1 倍または 2 倍の対数係数で向上します。

バードが発表した4つのロシア人の方法による行列反転アルゴリズムは、_F2上の密行列の高速演算のためにM4RIライブラリに実装されています。M4RIはSageMathとPolyBoRiライブラリで使用されています。 ^[1]

このアルゴリズムは、1970年にVL Arlazarov、EA Dinic、MA Kronrod、IA Faradževによって導入されました。^[2]名前の由来は不明ですが、Aho、Hopcroft、Ullman（1974）は次のように説明しています。

2番目の方法は、発明者の基数と国籍にちなんで「4人のロシア人」アルゴリズムと呼ばれることが多く、定理6.9のアルゴリズムよりもやや「実用的」です。^[3]

4人の著者は当時ソビエト連邦のモスクワで活動していた。 ^[4]

• Arlazarov, V. ; Dinic, E.; Kronrod, M.; Faradžev, I. (1970)「有向グラフの推移閉包の経済的な構築について」Dokl. Akad. Nauk SSSR、194 (11)。原題：「Об экономном построении транзитивного замыкания ориентированного графа」、発行：Доклады Академии Наук СССР 134 (3)、1970 年。
• Aho, Alfred V. ; Hopcroft, John E. ; Ullman, Jeffrey D. (1974)。『コンピュータアルゴリズムの設計と分析』 Addison- Wesley。ISBN 978-0-201-00029-0. OCLC  1147299.
• バード、グレゴリー V. (2009)、代数暗号解析、シュプリンガー、ISBN 978-0-387-88756-2