文献

J-GLOBAL ID：201702224341228601   整理番号：17A1729986

ファーストルック:行列乗算のない計数線形代数ベースの三角形【Powered by NICT】

First look: Linear algebra-based triangle counting without matrix multiplication

著者 (6件)： Low Tze Meng (Department of Electrical and Computer Engineering, Carnegie Mellon University) ,  Rao Varun Nagaraj (Department of Electrical and Computer Engineering, Carnegie Mellon University) ,  Lee Matthew (Department of Electrical and Computer Engineering, Carnegie Mellon University) ,  Popovici Doru (Department of Electrical and Computer Engineering, Carnegie Mellon University) ,  Franchetti Franz (Department of Electrical and Computer Engineering, Carnegie Mellon University) ,  McMillan Scott (Software Engineering Institute, Carnegie Mellon University)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： HPEC  ページ： 1-6  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 厳密な三角形計数への線形代数ベースのアプローチは,原始的な操作としてスパース行列乗算を必要とする。同じ問題への非線形代数アプローチは,グラフの隣接行列が利用できないと仮定した。本論文では,両方のアプローチは,アルゴリズム設計からのデータフォーマットを分離する単一アプローチに統一できることを示した。三角形計数アルゴリズムを鋳造行列乗算にないことで,各三角形を正確にことを異なるアルゴリズムを同定することができる。さらに,適切な疎行列形式を選択することにより,同じアルゴリズムで得られた小型順方向アルゴリズムと等価であることを仮定してグラフの隣接行列が利用できないことを示した。は,筆者らのアプローチは,参照実装よりも2000倍69以上速いことを初期実装をもたらすことを示した。も初期実装は,共有メモリシステム上での並列化が容易にできることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *線形代数 ,  アルゴリズム ,  *乗算 ,  グラフ ,  鋳造 ,  データフォーマット ,  スパース行列
準シソーラス用語： アルゴリズム設計 ,  隣接行列 ,  代数的アプローチ ,  *計数 ,  *行列積 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 行列乗算 ,  計数 ,  線形代数 ,  三角形