ブール行列の乗算アルゴリズムの高速化について

概要

論文の詳細を見る
本論文では, ブール行列の乗算のための新しく能率のよいアルゴリズムを開発し, 計算機実験により, 従来のアルゴリズムと性能の比較をしている. ブール行列A, Bが与えられたとき, その積C=A・Bはc_<ij>=Σ^^n__<k=1>a_<ik>・b_<kj>で与えられる. 上の計算を定義通りやると, もちろんΟ(n^3)の手間がかかる. この計算において, a_<ik>・b_<kj>=1となるところでΣの計算を打切るようにすれば, 1の発生確率をpとして, Ο(n^2/p^2)の時間で計算できる. この方法をループ脱出法と呼ぶことにする. 従来知られているブール行列乗算の高速化の代表的なものはStrassen法と4人のロシア人の方法である. Strassen法では, ブール代数を環の中に埋め込むことによって, Ο(n^<2,5>)で計算する. 4人のロシア人ではビットパタン1101を数値13のようにデータ圧縮することによって, Ο(n^2/log n)の時間で計算する. 本論文の方法は, 4人のロシア人におけるデータ圧縮の考え方とループ脱出法の考え方を共存させることにより, 平均Ο(n^2/(p^2 log n))+Ο(n^2), 最悪Ο(n^3/log n)の時間で走る. 計算機実験でも, このアルゴリズムが速く走ることを確かめた. したがって, 本論文の方法は実用的評価に耐えるものと考えられる.
1979-01-15