数式処理学会理論分科会研究会 (第1回) および Computer Algebra Seminar No.32 (計算代数セミナー, 第32回) [共催です] at University of Tokyo
(東京大学)
Feb 13 (Fri), 2009. 2月13日 (金曜日), 10:00---17:00
場所:東京大学 本郷キャンパス 工学部 14号館 501 号室. 地図
Place: University of Tokyo, Hongo campus, Faculty of engineering, Bldg 14, Room 501. map
-
10:00--10:10: 会長挨拶, 齋藤友克
-
10:10--11:10: 木村欣司(京都大学),
「行列式の余因子展開・ラプラス展開による計算から見た近年の数式処理ソフト研究の発展と今後の展望」
要約: はじめに、行列式の余因子展開・ラプラス展開に効率的な実装において、
ハッシュ法によるデータの再利用における効率化は、必要ではないことを示す。
すなわち、余因子展開・ラプラス展開では、計算式によるテーブル参照によって、
効率的なデータの再利用が行えることを示す。次に、余因子展開・ラプラス展開に
よる計算の基本となる演算は、多項式の加減演算と乗算であるため、
その効率化を達成するアルゴリズムを紹介する。
しかし、演算の基本単位は、多項式の加減演算と乗算とするよりも内積とするべきで
あることがすぐにわかる。よって、これからの数式処理ソフトの演算の基本単位は、
四則演算に加えて、内積もいれるべきであることを提案する。
さらに、中国剰余定理に付随した有限体の演算においても、四則演算に加えて、
内積も、演算の基本単位に加えることで高速化がはかれることを示す。
-
11:30--12:30: 田島慎一(新潟大学), 小原功任(金沢大学),
「レゾルベントの留数解析と行列のスペクトル分解アルゴリズム」
要約: 最小多項式が重複因子を持たないような正方行列に対し、レゾルベントの
留数値を求めることで行列のスペクトル分解を効率的に計算する
アルゴリズムを導出した。アルゴリズムの導出法、特性、並列化等について述べる。
-
14:00--15:00: 竹縄知之(海洋大), 関口良行(海洋大), 脇隼人(電通大),
"Real ideal and the duality of semidefinite programming for
polynomial optimization "
要約:
与えられた等式および不等式を満たす半代数的集合上でゼロになる多項式全体が等式から作られるイデアルになるための必要十分条件について調べる.またCylindrical Algebraic Decomposition
を用いてそのようなイデアルを具体的に求めるアルゴリズムを提案する.応用として,Lasserreらによる半正定値計画を用いた多項式最適化問題の解法(半正定値計画緩和)において現れる主双対問題の双対 GAPが0にできることを示す.
-
15:30--16:15: Martin Mevissen (東京工業大学),
"Enumerating the solutions of a polynomial system derived from fluid dynamics"
Abstract:
We present a general algorithm to approximately enumerate all solutions of a zero-dimensional polynomial system with respect to a given objective function. The algorithm is developed and is used to study a polynomial system obtained by discretizing the steady cavity flow problem in two dimensions, which is a simple model of a flow with closed streamlines.
The key technique on which our algorithm is based is to solve polynomial optimization problems via sparse semidefinite programming relaxations (SDPR), which has been adopted successfully to solve reaction-diffusion boundary value problems in our previous work. The objective function to be minimized is derived from discretizing the kinetic energy of the fluid. The solutions of the enumeration algorithm are shown to converge to the minimal kinetic energy solutions for SDPR of increasing order. We take advantage of Groebner basis method to tune the performance of the algorithm, demonstrate the algorithm with SDPR of first and second order on polynomial systems for different scenarios of the cavity flow problem and succeed in approximately deriving the k smallest kinetic energy solutions.
This is a joint work with Kosuke Yokoyama and Nobuki Takayama.
- 16:15--17:00: 自由討論 (free discussions)
Past Lectures.
---------------------------------------------------------------
The computer algebra seminar is co-organized by
M.Noro, noro @ math.kobe-u.ac.jp
N.Takayama, takayama @ math.kobe-u.ac.jp
K.Yokoyama, yokoyama @ rkmath.rikkyo.ac.jp
For more info see http://www.math.kobe-u.ac.jp/seminar.html/compalg.html
http://www.math.kobe-u.ac.jp/seminars.html