フレイヴァルズのアルゴリズム

フレイヴァルドのアルゴリズム（ルーシンシュ・マルティンシュ・フレイヴァルドにちなんで命名）は、行列乗算を検証するために使用される確率的ランダム化アルゴリズムです。3 つのn × n行列が与えられた場合、  ${\displaystyle A}$、${\displaystyle B}$、 そして${\displaystyle C}$一般的な問題は、${\displaystyle A\times B=C}$単純なアルゴリズムでは、積を計算する。${\displaystyle A\times B}$明示的に、この積が等しいかどうかを項ごとに比較します${\displaystyle C}$しかし、最もよく知られている行列乗算アルゴリズムは、${\displaystyle O(n^{2.372})}$時間。フレイヴァルドのアルゴリズムは、ランダム化を利用して、この制限時間を短縮します。${\displaystyle O(n^{2})}$^{[ 1 ]}高い確率で。${\displaystyle O(kn^{2})}$アルゴリズムは、以下の確率で行列積を検証できます。$2^{-k}}$。

仮に、次のようなことを確認したいとします。

${\displaystyle AB={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\stackrel {?}{=}}{\begin{bmatrix}6&5\\8&7\end{bmatrix}}=C.}$

要素が0または1のランダムな2要素ベクトルが選択されます。 ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$ そして、以下の計算に使用されます。

${\displaystyle {\begin{aligned}A\times (B{\vec {r}})-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\\&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}11\\15\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}0\\0\end{bmatrix}}.\end{aligned}}}$

これによりゼロベクトルが得られ、AB = C の可能性が示唆されます。しかし、2回目の試行でベクトルが${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$が選択されると、結果は次のようになります。

${\displaystyle A\times (B{\vec {r}})-C{\vec {r}}={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}-1\\-1\end{bmatrix}}.}$

結果はゼロではないため、実際にはAB ≠ Cであることが証明される。

2要素の0/1ベクトルは4つあり、そのうち半分はこの場合ゼロベクトルになります（${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$そして${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$）、したがって、これらを 2 回の試行でランダムに選択する確率 (そして AB=C と誤って結論付ける確率) は 1/2 または 1/4 です^。一般的には、ゼロベクトルを生成するrの割合は 1/2 未満になる可能性があり、より多くの試行 (例えば 20 回) を使用することで、エラーの確率は非常に小さくなります。

pを誤りの確率とする。A × B = Cの場合、p = 0であり、A × B ≠ Cの場合、p ≤ 1/2 であると主張する。    

簡単なアルゴリズム解析によると、このアルゴリズムの実行時間は${\displaystyle O(n^{2})}$（ビッグオー記法で）これは、古典的な決定論的アルゴリズムの実行時間を上回ります。${\displaystyle O(n^{3})}$（または${\displaystyle O(n^{2.372})}$高速行列乗算を使用する場合）。エラー分析では、アルゴリズムを実行すると、${\displaystyle k}$回数、誤差範囲は以下${\displaystyle 1/2^{k}}$指数関数的に小さい量で達成できます。また、行列とベクトルの積の高速な実装が広く利用可能であるため、このアルゴリズムは実際には高速です。したがって、ランダム化アルゴリズムを利用することで、非常に遅い決定論的アルゴリズムを高速化できます。

フレイヴァルズのアルゴリズムは、その簡潔さと、いくつかの問題において確率的アルゴリズムが実際に優れていることを示す例として、確率的アルゴリズムの入門書で頻繁に取り上げられる。

• シュワルツ・ジッペル補題