第１２回研究会（２００８年８月２日（土） １４時 〜）講演概要
会場： 産業技術大学院大学 ３階
３１４情報センター講義室
講演者：
岡本 吉央 氏 （東京工業大学）
タイトル：
Tutte多項式計算の厳密アルゴリズム
概要： Tutte多項式はグラフの基本的な不変量であり，様々なグラフ不変量が その評価値として表せるため，離散アルゴリズムの分野でもその有用 性が認識され，多くの研究がなされてきた．本講演では，まずTutte多 項式の定義から始めて，その計算が理論的にどれほど速く行えるのか， 講演者らの結果を言及しながら紹介する．
講演者：
室田 一雄 氏 （東京大学）
タイトル：
行列のブロック対角化の諸相
概要： 与えられた複数の行列に同じ変換を施して， すべてを同時にブロック対角形やブロック三角形に分解することを考えます． この種の手法は，物理学などいろいろな分野で用いられてきましたが， 最適化においても，最近，群対称性をもつ半正定値計画（ＳＤＰ） の効率的解法という文脈で利用されています．
私見によれば，行列が分解できる主な理由には， (1) 群論的な対称性 (group symmetry) と (2) 疎性（sparsity）の二つがあります． 群対称性に着目する手法の基礎は群表現論にあり， 疎性に着目する手法の基礎は，グラフ／マトロイド理論にあります． 現実のシステムでは群対称性と疎性が絡み合っているのですが， これをどう扱うかについて，２０年くらい前から気になっていました． 本発表では，この辺りの問題意識から説明して，＊代数の枠組みによる手法 （小島政和氏，小島定吉氏，寒野善博氏，前原貴憲氏との共同研究） の概略を紹介します．
ホーム
Copyright, S@CO All rights reserved, 2006-2008.
