第１０回研究会（２００８年３月１５日（土） １４時 〜）講演概要
会場： 上智大学 四谷キャンパス １１号館３階 １１−３０５
講演者：
藤重 悟 氏 （京都大学数理解析研究所）
タイトル：
最小ノルム点問題を巡って
概要： 最小ノルム点問題は与えられた多面体上のノルム最小の点を 見出す問題であり、Philip Wolfeのアルゴリズムがよく知ら れるが、 その変種もいくつか提案されている。多面体の与え方は色々あり、 その複雑さも色々であるが、Wolfeのアルゴリズムは、 与えられた多面体上の線形関数最小化が計算可能であれば使うことが 可能であるという特徴を有する。この特徴は大変ありがたくて、 基多面体を考えると劣モジュラ関数最小化に有効に使える。また、 いわゆるゾノトープもその上の線形関数最小化が容易であって、 それによって線形計画問題の新しいアルゴリズム(LP-Newton 法)が 構成できる。これらの話題を巡ってお話ししたい。
講演者：
藤澤 克樹 氏 （中央大学）
タイトル：
アルゴリズムサイエンス分野におけるソフトウェアの実装方式について
概要： 近年、アルゴリズムサイエンス分野における基礎理論の探求は飛躍 的に進んでおり、 以前のような理論的計算量を重視する立場から、ソフトウェア実装 面を意識して、 実際にどのような構造、特性を持つ場合において、高速かつ安定に 解けるかといったような 研究に移行してきている。 一方、コンピュータのハード＆ソフトウェア面での研究の進展も著しく、 近年ではスーパーコンピュータ等を中心した並列計算技術だけでな く、汎用的なマルチコア上の並列計算から 大規模環境下でのグリッド計算まで新世代の実装方式が開発されている。 しかし両者の有機的な融合方法については、最近では必要性が叫ば れ始めているものの、 いまだに説得力を持った合理的方法の形成には至っていない。つま り実装面においても 例えばメモリバンド幅の制御、キャッシュ＆メモリ階層構造の効率 的利用、複数プロセス間の同期方法などに ついては多くの研究が行われて成果が公表されているが、その探求 方法には膨大な選択肢が存在し、 アルゴリズムサイエンスの立場の人間がこれらをどこまで採用すべ きか、あるいはどのような効果が 期待できるかなどの知見はほとんど得られていない。 本発表では現在進行中の半正定値計画問題や最短路問題に対する高 速解法の開発に関する 研究を通して、CPU の演算性能や CPU <--> メモリ間 のバンド幅の限界近くまで 性能を上げる方法を紹介しながら、アルゴリズムサイエンス分野に おけるソフトウェアの実装方式 の方向性についても議論を行う。 この研究は SDPA Project のメンバー及びテキサス大の後藤 和茂氏との共同研究である。
ホーム
Copyright, S@CO All rights reserved, 2006-2007.
