大規模グラフ最適化(解析)の重要性
大規模推測における最適なランキングと選択の方法：ベイズ流階層混合モデリングの応用
... FDR の情報を付与すること も可能であり, 実践的なデータ解析には明確な 利点があると思われる. 本稿では, R 値による ランキングの方法にフォーカスして議論を行っ たが, この他にも Laird & Louis (1989), Lin et ...値によるランキングそのも のの実践的な有用性については, 今後の研究に よって, ...
14
大規模データ可視化におけるレベルセットグラフの可能性 (21世紀における数値解析の新展開)
... 数値シミュレーションや計測を行うための環境の劇的な進歩によって , 日常的に取り扱うデータの量は飛 躍的に増大している. たとえば 1 つのランにつき , 現在利用可能な GPU の $3\mathrm{D}$ テクスチャマッピング機能 を用いて , 効率的にレンダリングできる 256 の 1 バイト長 3 次元規則格子データ ( ボリュームデータ ...
6
ポストペタスケール高性能計算に資するシステムソフトウェア技術の創出 平成 23 年度採択研究代表者 H27 年度 実績報告書 藤澤克樹 九州大学マス フォア インダストリ研究所 教授 ポストペタスケールシステムにおける超大規模グラフ最適化基盤 1. 研究実施体制 (1) 大規模最適化 グループ( 九
... 新しいスーパーコンピュータの応用として大規模なグラフ解析が注目を集めている. グラフ解析の 応用分野としては大規模災害等での避難誘導計画，社会公共政策や企業経営等のためソーシャ ルネットワーク等の大規模データの有効活用等が想定されているが, ...
5
大規模動的ネットワークに特化した グラフデータ格納基盤
... • ソーシャルネットワークデータに対する解析 ：動的な重要度、影 響度の判定。各点の周辺、及び広域内における影響（情報の 伝播力)を推定する • その他：疫病の拡散、人口の増減、経済動向等の分析。ライフ ライン等の基盤計画（電力、水、食料）。生命科学系（創薬、遺 伝子）。ビジネス系（金融、データマイニング）。安全保障分野 ...
37
大規模な組合せ最適化問題に対する 発 見見的解法 大阪 大学 大学院情報科学研究科 科学技術振興機構 梅 谷俊治 2014 年年 3 月 12 日 数学協働プログラムチュートリアル ビッググラフと最適化
... – 結果が⾮非常に悪くなるごく少数の反例例が存在する場合や，アル ゴリズムが複雑過ぎて解析的な評価ができない場合が多い． • メタヒューリスティクス – 最適化問題に対する実⽤用的なアルゴリズムを設計するための⼀一 般的な枠組み(レシピ集)，もしくはそのような考え⽅方に従って 設計された様々なアルゴリズムの総称として呼ばれる． ...
51
メモリ階層構造を考慮した大規模グラフ処理の高速化
... 道路ネットワーク USA-road-d.LKS.gr (n = 2.76M, m = 6.89M) : 20.6 日間 特許引用ネットワーク cit-Patents (n = 3.77M, m = 16.52M) : 23.6 時間 性能を引き出すためには 特殊な計算機環境 (CRAY XMT) が必要 ボトルネック となる 最短路計算 に対する汎用的な実装は存在しない ⇒ 高性能ネットワーク解析ライブラリ NETAL ...
23
クローフリー双向グラフに対する一般化安定集合問題 (数理最適化の理論と応用)
... た準最適解 $X$ に対して \mbox{\boldmath $\delta$}x(A) 最大の交互集合 $A4$ を求めれば , $X\triangle A$ は準最適解に なる . よって \mbox{\boldmath $\delta$}x(A) 最大の交互集合 $-4$ を繰り返し求めることによって , 無向クロー フリ $-$ ...
10
比較推定による最適化アルゴリズムの効率性向上(最適化問題における確率モデルの展開と応用)
... 満足したときに実際に解を受け入れる確率であり, $P_{c}$ が $0$ の場合は , 推定値のみによる判定となり従来の ポテンシャル法と一致する , P』が 1 の場合は混雑度による判定を完全に受け入れることになる. $P_{c}$ を大き くすると重要なベクトルを拒否する可能性が下がるが , 逆に悪いベクトルを受け入れる可能性が高くなる . ...
12
極大鎖グラフを用いた順序複体のシェリング可能性の判定について (数理最適化の理論とアルゴリズム)
... 的サイクルを持たないことが必要であることが示された. しカル , [5] ではそのための有効なアルゴリズムが示 されていない. また, 与えられた条件が十分条件となっているかどうかについても述べられていない. 本論文で は , 極大鎖グラフが本質的サイクルを持たないという条件を効率的に調べるのに役立つ定理とこの条件が十分条 件とはならないことを , Dunce hat ([15], [17]) ...
10
大規模な非線形最適化問題に対する主双対内点法について(数値計算アルゴリズムの研究)
... Z_{k})\}$ の局所的超 1 次収束性を議論した . こうした収束性の解 析において , 局所的収束性に関しては本来のニュートン方向が活かされているのに対して , 大域的収束性に 関してはバリヤペナルティ関数を単調に減少させる必要があるので必ずしも —= ...
8
大規模な制約なし最小化問題に対するコーダル部分グラフを用いたスパース準ニュートン法 (数値最適化の理論と実際)
... F$ の成分は $(\overline{H}_{k+1})_{tj},$ $\forall(i,j)\in F$ のみから式 (8) $\sim(10)$ を用いて計算できることに注意す ると , MCQN 法の実装の際には, $H_{k}$ を陽に計算する必要はなく , 行列 $H_{k}$ とあるベクトル $d\in \mathbb{R}^{\mathfrak{n}}$ の積 ...
12
グラフのLaplace-Beltrami作用素とその応用 (数理最適化の理論とアルゴリズム)
... 本論文では, このようなヘテロな構造を持つネットワークに適した新しい作用素による拡散 を考え , 特に, 帯域幅などの重みが付いたネットワーク上の分散 $\theta^{-}-J\backslash ^{\backslash ^{\backslash }}$ の負荷均一化への応用 を検討する. これらの結果が , WWW ...
9
大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開)
... 的かつ大幅な高速化を行うことが可能であることを示した．本研究で高速化を施したバイナリヒープを適 用したダイクストラ法は，先行研究のマルチレベル．バケットに対して 1 スレッド時には同程度の性能を示 し，メモリ要求量が同量となる 4 スレッド時には 4O2 倍高速である．数値実験により本ソフトウェアは L2 キャッシュメモリ帯域幅に律速しているが確認され， L2 ...
11
完全グラフ上の最大辺素パス問題に対する貪欲近似アルゴリズム (最適化の数理とアルゴリズム)
... ルゴリズムは Erlebach and Vukadinovic’[2] によって与えられた . このアルゴリズムでは , 最初に頂点集 合 $V$ を $V_{1},$ $V_{2},$ $V_{3}$ という 3 つの概ね等しいサイズの部分に分け , リクエスト $\mathcal{R}$ も $\mathcal{R}_{12},\mathcal{R}_{23},\mathcal{R}_{31}$ という 3 ...
12
信頼領域を用いた大規模非線形計画問題に対する並列部分空間法 (最適化モデルとアルゴリズムの新展開)
... 際に，大規模問題においてしばしば生じる行列の疎構造を考慮していない．そう いったプログラムの実装上の改善も今後の重要な課題である． 参考文献 [1] M. Fukushima, Parallel variable transformation in unconstrained optimiza- ...
5
ネットワーク・デザイン問題とそのグラフ構造 (決定理論と最適化アルゴリズム)
... [email protected], [email protected] 1 はじめに ネットワーク $|1$ デザイン問題は , 多品種流問題と各アークに関する設備配置を同時に 考える問題である . 多種多様なバリエーションをこの問題は持っている . 応用は, 計算 機ネットワー久 通信ネットワー久 交通ネットワークの計画等にわたる. 特にインター ネット社会ではその重要性は増している . ...
10
セル複体に付随するグラフの向き付けとその最適解 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... 56 の最適解からの議論は共に acyclic な 向き付けの線形拡大に沿った逐次構成を元にしているが、 他の組合せ的な構造において も逐次構成に沿った性質に対しても同じように acyclic な向き付けの空間中の最適化の 形で議論することは可能かもしれない。 ...
11
半正定値計画問題での大規模線形方程式系に対する前処理付き共役勾配法 (最適化のための連続と離散数理)
... そのため、線形方程式系 の制約行列の構造を基に、不完全 Gram-Schmidt の直交化法という観点から、共役勾配法の前処 理の統– 的な枠組みを提案した。そして、 この枠組みから幾つかの前処理法を導出し、 各々の前 処理が共役勾配法の収束性に与える影響を測定した。 しかし、 ...
12
解の多様性を維持するアントコロニー最適化手法(モデリングと最適化の理論)
... Bullnheimer らにより提案された Rar&-based Ant System (AS-rank) [2] は, フェロモン値の更新 の際 , その反復で得られた解 $X^{k}$ を巡回俳門が短い解からソートしたリスト $\mathcal{L}\subset A$ を作成し , その ランクに対応した重み $w_{k}$ を用いて各路のフ $i=$ ロモン値を更新する方法である ...
9
量子化学計算の大規模化１
... データの依存関係や多重ループ内にIF文があるなど複雑になると、 最適化されない場合が多い • BLAS, LAPACKなど数学ライブラリの利用 – BLASライブラリはCPUの性能を引き出してくれるが、小さい配列(100 次元程度)の場合、サブルーチンコールのオーバヘッドの方が大きく ...
38