佐藤　峻
2014/4/16 (水), 15:00-18:00
東京大学 工学部6号館 235号室

　有理関数行列におけるk次小行列式の最大次数は，無限遠点におけるSmith-McMillan正準形を求める場合等に有用である．有理関数行列A(x)が与えられたとき，固定された任意のkに対してk次小行列式最大次数を求めるための組合せ緩和アルゴリズムが，室田らによって提案されている([2])．
　卒業論文では，k = 1からk=rank Aまでの全てのkについてk次小行列式最大次数を求める場合に，k次小行列式最大次数がkについて凹関数であるなどの良い性質をもつことを利用した組合せ緩和アルゴリズムを提案し，その最悪計算量が室田-岩田-作田[1]によるアルゴリズムよりも改善されることを示した．
　今回の発表では，その主たる特徴と重要な補題を述べる．

参考文献
[1] S. Iwata, K. Murota, and I. Sakuta. Primal-dual combinatorial relaxation algorithm for the maximum degree of subdeterminants. SIAM J. Sci. Comput., Vol. 17, pp. 993–1012, 1996.
[2] K. Murota. Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-Mcmillan form at infinity and structural indices in Kronecker form. Appl. Algebra Eng. Commun. Comput., Vol. 6, pp. 251–273, 1995.