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

• Item type: Journal(1)
• 公開日: 1979-01-15
• タイトル: ブール行列の乗算アルゴリズムの高速化について
• タイトル / 言語: en
• タイトル: On the Speed - up of Algorithms for Boolean Matrix Multiplication
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 茨城大学工学部情報工学科
• 著者所属: 三菱電機（株）電子技術部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Ibaraki University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Ibaraki University
• 著者名: 高岡, 忠雄; 福地, 陽一
• 著者名(英): Tadao, Takaoka; Yoichi, Fukuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では ブール行列の乗算のための新しく能率のよいアルゴリズムを開発し 計算機実験により 従来のアルゴリズムと性能の比較をしている.プール行列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)の時間で走る.計算機実験でも このアルゴリズムが速く走ることを確かめた.したがって 本論文の方法は実用的評価に耐えるものと考えられる.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 20, 号 1, p. 45-49, 発行日 1979-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764