トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

グレブナー基底

[アルゴリズム]

グレブナー基底

以下、Wikipediaからの引用。重要なのは、最後の部分でコンピュータで連立方程式を解くのが簡単になるというところが超気になる。

概要
グレブナー基底の基本的な考え方は、多項式の集合 F を以下の特性を持つ "性質の良い"(グレブナー基底と呼ばれる)多項式の集合 G に変換することである。
  • F と G は "等価"(つまり同じイデアルを生成する)

さらに、グレブナー基底についての理論から以下のことが分かっている。

  • グレブナー基底の "性質の良さ" のため、F で解くのが難しい多くの問題をグレブナー基底 G で解くことができる。
  • 任意の F を等価なグレブナー基底 G に変換するアルゴリズム(ブッフベルガーアルゴリズム)が存在する。
  • G での問題の解法は、多くの場合、簡単に F での問題の解法に変換できる。

???ぜんぜんわからん、とりあえず

例えば、数式処理システムで多変数の連立代数方程式を解く場合、直接解くのは多くの場合難しい。その際に与えられた方程式のグレブナー基底を計算しそれらを解くことで、元の連立代数方程式の解を求めることができる。

OpenXMによる実践

  OpenXMのWindows版バイナリ

Groebner basis

よそのもう少しわかりやすそうな解説。

  読み物

  参考

お名前: コメント: