大規模半正定値計画問題に対する内点法アルゴリズムの高速計算

藤澤克樹; 遠藤敏夫

論文・著書情報

タイトル

和文:	大規模半正定値計画問題に対する内点法アルゴリズムの高速計算
英文:	High-Performance General Solver for Extremely Large-Scale Semidefinite Programming Problems

著者

和文:	藤澤克樹, 遠藤敏夫.
英文:	Katsuki Fujisawa, Toshio Endo.

言語

Japanese

掲載誌/書名

和文:	TSUBAME e-Science Journal
英文:	TSUBAME e-Science Journal

巻, 号, ページ

No. 7

出版年月

2012年12月26日

出版者

和文:	東京工業大学学術国際情報センター
英文:	GSIC, Tokyo Institute of Technology

会議名称

和文:
英文:

開催地

和文:
英文:

アブストラクト

半正定値計画問題（SDP）は組合せ最適化、システムと制御、データ科学、金融工学、量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。また今後のエネルギー供給計画（スマートグリッド等）では非線形の複雑な最適化問題を扱う必要があり、これらの問題に対して強力な緩和値を算出できるSDP の高速計算技術の確立が急務とされている。SDP に対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算が大きなボトルネックとなっている。著者らのグループでは内点法アルゴリズムを記述したソフトウェアの開発・評価・公開を 15 年以上行っており、疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術を他に先駆けて実現し、大規模な並列計算等によって上記のボトルネックの高速化と世界最大規模のSDP を高速に解くことに成功している。今回、東京工業大学のスーパーコンピュータTSUBAME 2.0 において、多数 GPU の活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの 1 つである線形方程式系のCholesky 分解の高速化に成功した。さらに制約式の数が 148 万以上となる世界最大規模の巨大 SDP を解き、SDP の世界記録の更新及び最大で 533TFlops（Cholesky 分解：4080 GPU）の性能を達成した。

Home

各種検索

サポート

T2R2について

関連リンク

論文・著書情報