研究紹介: グレブナ基底

グレブナ基底とは？

グレブナ基底は、1960年代に Buchberger によって多項式環のイデアルや加群の構造を計算するのに導入された。 一方で同じ頃、広中平祐により、巾級数環に同様の概念が導入され、 特異点解消のきっかけとなった。 近年では、グレブナ基底は代数幾何や可換代数における多くのアルゴリズムの 基礎になっていると共に、 ほとんどの数式処理システムに導入されている。

グレブナ基底の応用

近年では、 イデアルのグレブナ基底が様々な分野のアルゴリズムに応用されている。 例えば、

• 整数計画問題
• 連立線形方程式系
• 符号理論
• CG
• 凸多面体の三角形分割
• 統計学における二元表の数え上げやサンプリング
• 物理学における分岐理論や軌道空間分類

といった、幅広い分野への応用が行われている。 本研究では、様々な分野のアルゴリズムに対し、 グレブナ基底を用いた代数的なアプローチを行い、 それらの問題の構造を解明することが目的である。

これまでの研究成果

（論文）

これまでは、グラフのサイクル全体のなす線形空間に対応する 「グラフのトーリックイデアル」のグレブナ基底の構造の解析を行った。 過去には、無向グラフのグレブナ基底は解析され、 様々な分野への応用が行われていた。 一方、有向グラフについては、代数構造が悪く、 解析が行われていなかった。 そこで、有向閉路を持たない有向グラフのグレブナ基底の構造を調べ、 次数やグレブナ基底の要素数などの複雑度について解析を行った。 さらに、このグラフのグレブナ基底の応用として、次のことを行った。

最小費用流問題への応用

有向グラフ上での最適化問題の1つである最小費用流問題について、 グレブナ基底を用いたアルゴリズムを適用し、計算量を解析した。 最小費用流はもともと多項式時間解法が示されていたが、 グレブナ基底を用いた代数的な観点からのアプローチを行った。

ある超幾何系の解の次元解析

Lie 代数から生じる、「超幾何系」 と呼ばれる線形偏微分方程式系のある種に対して、 その解の次元がグレブナ基底を用いて計算できることを示した。 この次元はもともと Gelfand-Graev-Postnikov によって別の観点から示されていたが、 我々は代数的な観点から別証を与えた。