@article{oai:ipsj.ixsq.nii.ac.jp:00016405,
 author = {高岡, 忠雄 and 福地, 陽一 and Tadao, Takaoka and Yoichi, Fukuchi},
 issue = {1},
 journal = {情報処理学会論文誌},
 month = {Jan},
 note = {本論文では ブール行列の乗算のための新しく能率のよいアルゴリズムを開発し 計算機実験により 従来のアルゴリズムと性能の比較をしている.プール行列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/logN)の時間で計算する.本論文の方法は 4人のロシア人におけるデータ圧縮の考え方とループ脱出法の考え方を共存させることにより 平均Ο(n^2/(p^2logN))+Ο(n^2) 最悪Ο(n^3/logN)の時間で走る.計算機実験でも このアルゴリズムが速く走ることを確かめた.したがって 本論文の方法は実用的評価に耐えるものと考えられる.},
 pages = {45--49},
 title = {ブール行列の乗算アルゴリズムの高速化について},
 volume = {20},
 year = {1979}
}