{"links":{},"id":16405,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00016405","sets":["581:927:933"]},"path":["933"],"owner":"1","recid":"16405","title":["ブール行列の乗算アルゴリズムの高速化について"],"pubdate":{"attribute_name":"公開日","attribute_value":"1979-01-15"},"_buckets":{"deposit":"d6b695ff-90ad-437e-bb51-a5f0c0819661"},"_deposit":{"id":"16405","pid":{"type":"depid","value":"16405","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"ブール行列の乗算アルゴリズムの高速化について","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"ブール行列の乗算アルゴリズムの高速化について"},{"subitem_title":"On the Speed - up of Algorithms for Boolean Matrix Multiplication","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"論文","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"1979-01-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"茨城大学工学部情報工学科"},{"subitem_text_value":"三菱電機（株）電子技術部"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Engineering, Ibaraki University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Engineering, Ibaraki University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/16405/files/IPSJ-JNL2001007.pdf"},"date":[{"dateType":"Available","dateValue":"1981-01-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL2001007.pdf","filesize":[{"value":"396.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"8b814905-68a7-4d54-b9f9-b91c8711ecf5","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1979 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"高岡, 忠雄"},{"creatorName":"福地, 陽一"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tadao, Takaoka","creatorNameLang":"en"},{"creatorName":"Yoichi, Fukuchi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本論文では ブール行列の乗算のための新しく能率のよいアルゴリズムを開発し 計算機実験により 従来のアルゴリズムと性能の比較をしている.プール行列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)の時間で走る.計算機実験でも このアルゴリズムが速く走ることを確かめた.したがって 本論文の方法は実用的評価に耐えるものと考えられる.","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"49","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicPageStart":"45","bibliographicIssueDates":{"bibliographicIssueDate":"1979-01-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"20"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"created":"2025-01-18T22:49:41.179466+00:00","updated":"2025-01-22T23:53:01.319509+00:00"}