抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフ分割スケジュールは,スパース行列ベクトル乗算(SpMV)のような並列計算を行う。N非ゼロを持つスパース行列のm列(またはカラム)が再順序付けなしにK部分に分割される隣接分割を考察した。隣接領域におけるいくつかのグラフ分割問題に対する最初の近線形時間アルゴリズムを提案した。単純なエッジカット,ハイパーエッジカット,またはハイパーグラフ連結性のような従来の目的は,バランス制約の下ですべての部品の総コストを最小化する。著者らの全分割器はO(Km+N)空間を使用する。それらは,O((Kmlog(m)+N)log(N))時間において実行して,KernighanとGrandjeanらによる以前のO(K(m ̄2+N))時間アルゴリズムに関する重要な改良であった。Bottleneck分割は,どの部分の最大コストを最小化する。著者らは,各部分に関する通信と計算の合計を反映する新しいボトルネックコストを提案した。ボトルネック分割器は線形空間を使用する。正確なアルゴリズムは,K ̄2がC<1のO(N ̄C)であるとき,線形時間で実行される。Klog(c_high/(c_lowε))がC<1のO(N ̄C)であるとき,著者らの(1+ε)近似アルゴリズムは線形時間で実行され,そこではc_highとc_lowが最適コストの上限と下限である。また,線形時間からlog(c_high/(c_lowε))の因子で動作するより単純な(1+ε)近似アルゴリズムを提案した。著者らは,著者らのアルゴリズムが,42の試験行列のテストセットに関して高品質な隣接分割を効率的に作り出すことを経験的に実証した。K=8の場合,超グラフ連結性分割器は事前アルゴリズムよりも53×(平均15.1×)の高速化を達成した。ボトルネック分割器の平均実行時間は5.15SpMVであった。【JST・京大機械翻訳】
