[アルゴリズム]
グレブナー基底
以下、Wikipediaからの引用。重要なのは、最後の部分でコンピュータで連立方程式を解くのが簡単になるというところが超気になる。
- F と G は "等価"（つまり同じイデアルを生成する）
さらに、グレブナー基底についての理論から以下のことが分かっている。
- グレブナー基底の "性質の良さ" のため、F で解くのが難しい多くの問題をグレブナー基底 G で解くことができる。
- 任意の F を等価なグレブナー基底 G に変換するアルゴリズム（ブッフベルガーアルゴリズム）が存在する。
- G での問題の解法は、多くの場合、簡単に F での問題の解法に変換できる。
グレブナー基底の求め方
アルゴリズムと定式化
- MathWillsにアルゴリズムと定式化のための情報をまとめた
Rubyでの実装
- Rubyによる代数系の表現
- こちらはRubyによる一変数多項式環型(Poly1)のライブラリ
- Ruby版 多項式クラス
- こちらはRubyによる多項式型(Poly)のライブラリ
- GitHubにアーカイブがあったのでforkして今回はこちらを使わせてもらうことにする
- https://github.com/hangingman/Polynomial
参考
- よそのもう少しわかりやすそうな解説。
- 読み物