■第14回研究会(2005年4月16日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『半正定値計画問題を使って分子の電子構造を求めよう』東京工業大学 福田 光浩 氏
物理化学・化学物理におき基本的な問題として分子(原子)の 基底状態を理論的 に求めるものがある.特に(分子の)電子の 基底状態はSchrodinger波動関数の最小固有値問題を解くことに よって求まるが,解析的には2電子以上のものは解けない. そこで関数空間においてまず有限個の関数基底を固定し, 従来のアプローチでは波動関数の性質からHartree-Fock法, SDCI法,Full CI法等が基底状態エネルギーを近似するのに 提案され,広く使われている.本発表で登場する縮約密度行列法 の創案は1960年代に Coleman, Garrod, Percusらにより, 初期の数値実験は70年代に行われたが, 当時半正定値計画問題の 概念すらなかったので, そのまま忘れ去れてしまった. しかし 2001年に中田真秀は大規模な半正定値計画問題として 定式化された問題から小さい系の分子(原子)に対する良い基底 状態エネルギーの計算に成功した. 本発表では電子構造の基底 状態の半正定値計画問題緩和に用いる N-representability条件の いくつかを紹介する。また、並列計算によって求まった大規模な 半正定値計画 問題の最適値である基底状態エネルギーの近似や 解から求まる双極子モーメントの近似を波動関数から導かれる 従来のアプローチと比較する。
 
16:10--18:00『分子構造符号化とグラフ同型性判定』東京大学 小市 俊悟 氏
分子構造符号化とは,分子の平面構造や立体構造を文字列である 線形表記によって表現しようというものである.CAST/CNMRシステムと 呼ばれる,高精度な核磁気共鳴(NMR)化学シフト値予測システムでは, そのような線形表記を用いて分子の検索を行う.検索漏れを避け, データベース容量を抑えることを考慮すると,分子と線形表記に 一対一対応が付くことが望ましい.このような符号化法のことを 規範的な符号化法と呼ぶ.ここで,分子をグラフと捉えると規範的な 符号化法によって生成される線形表記は,分子グラフの標準形と 呼べるものである.グラフの標準形を求める問題はグラフ同型性 判定問題を含み,計算複雑度が未解決な問題として知られている. このような事実からグラフの標準形を求めるものとして,計算量の 多項式性は保証されないが,実用的に高速と言われる頂点分類型 アルゴリズムと呼ばれる枠組みがある.本研究では,その枠組みに入る 新たなアルゴリズムを考案し,そのアルゴリズムを分子構造符号化に 応用した.その結果,分子グラフに対しては実用的に十分高速に, その線形表記を得ることができる.これにより,CAST/CNMRシステムの 実用化が大きく進むこととなった.本講演では,CAST/CNMRシステムを 含め,グラフ同型性との関わりを中心に分子構造符号化について紹介する.
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.