グレブナー基底・ブッフバーガーアルゴリズム

@hiroyuking

2022/03/07 00:29 更新

グレブナー基底

158 いいね 0 ブックマーク

前提となる知識のキーワード
- 項順序
- 多項式環
- イデアル
  - 上記の知識は、最近すうがくぶんかにて主催された無料公開講座　グレブナー基底入門で知ることができるので、興味がある方はぜひ。
モチベーション
- 筆者はある種の数式を自動で解けるという仕組みが個人的に気になっており、グレブナー基底やQEを調べている

前提知識は最後の方に書いている

ブッフバーガーアルゴリズム

野呂正行・横山和弘「グレブナー基底の計算基礎編計算代数入門」, p196 より引用

ブッフバーガーアルゴリズムの疑似コードを見て、理解を深めたい。
以下のアルゴリズムに多項式$F$と、項順序$\prec$を与えるとグレブナー基底が返る。

アルゴリズム 5.20_Buchberger(F,$\prec$)

$${\begin{aligned} & {\bf Input:} 多項式集合F, 項順序 \prec \\ & {\bf Output:} \left⟨ F\right⟩ の\prec に関するグレブナー基底 G \\ & \quad D \gets \{\{u, v\} | u, v \in F, u \neq v \} \\ & \quad G \gets F \\ & \quad {\bf while} \; D \neq \phi \; {\bf do} \\ & \quad \quad \{u, v\} \gets Dの要素 \\ & \quad \quad D \gets D \; \backslash \; \{\{u, v\}\} \\ & \quad \quad Spoly (u, v) \xrightarrow[G]{*} r かつ Gに関して正規形となるrを計算(*) \\ & \quad \quad \\ & \quad \quad {\bf if} \; r \neq 0 \; {\bf then} \\ & \quad \quad \quad D \gets D \; \cup \{\{ h, r \} \; | \; h \in G \} \\ & \quad \quad \quad G \gets G \; \cup \{ r \} \\ & \quad \quad {\bf end \; if} \\ & \quad {\bf end \; while} \\ & {\bf return \;} G \\ \end{aligned} }$$

前提知識

$\prec$ (=項順序)

項順序はWikipediaに記載がある通り、多項式の項の順序を定めるもの
$a \prec b$ は順序的にbのほうがaより大きいということを示す、どう並べるかは文脈しだいだが多項式の場合普通は降順(desc)に並べる

とりあえず、辞書式順序を覚えておけば大丈夫そう。

Wikipediaから引用

辞書式順序 (lexicographic order, lex) は、β - α の 0 でない最初の成分が正である場合に xα < xβ として定義される単項式順序である。素朴に表現するならば、lex 順序はまず最も「上位の」不定元の指数の大きさによって順序付け、それが同じものについては順次「下位の」不定元の指数の大きさによって順序付ける。

3つの単項式 $x^2yz, x^3, xy^3$ を考えよう。不定元の間には x > y > z という順序が定まっているとすると、代表的な単項式順序においては、次のように順序付けられる。

lex 順序では$x^3 > x^2yz > xy^3$となる（x の指数の大きさが順序を決める）。

lex順序とは辞書式順序である。要は、後で掃き出し操作するために単項式の順序を決めているんですね。

$D \; \backslash \; \{\{u, v\}\}$ (=差集合)

$D \gets D \; \backslash \; \{\{u, v\}\}$ は $D$ と $\{\{u, v\}\}$ の差集合を指す（普通にわからなかった）
要はループの前に１要素削除して次に行くということか

$Spoly(f, g)$ (＝掃き出し操作の一般化)

「グレブナー基底の計算実践篇 Risa/Asirで解く」, p127 より引用

定義 3.26（S多項式）

$${\begin{aligned} & Spoly(f, g) = \frac{lcm(HT(f), HT(g))}{ \underbrace{ HM(f) }_{ HM(f) = HC(f) \cdot HT(f) }} f - \frac{lcm(HT(f), HT(g))}{HM(g)} g \\ \end{aligned} }$$

$lcm$ とは、項の最小公倍項である
- 英語版のWikipediaに定義が載っていた Least common multiple
- 参考: gcd/lcmとmin/maxが同型という話

$$ \text{lcm}(x, y) = \prod_{p \in \mathbb{P}} p^{ \max(x_p, y_p) }$$

まあ、要はこのグレブナー基底のSpolyでは項のデカい方をとれば良いわけだ（x, yのどちらも１つしか項が与えられないはずなので）。

Spolyに出てくる用語の定義

$HT(f)$ ... 頭項(=Head Term)のこと、指定の項順序で式を並び替えたとき1番大きな項を指す
$HC(f)$ ... 頭係数(=Head Coefficient)のこと、頭項の係数
$HM(f)$ ... 頭単項式(=Head Monominial)のこと、指定の項順序で式を並び替えたときの単項式のうち先頭のものを指す

上記は「グレブナー基底の計算基礎編計算代数入門」, p72 より引用

Wikipediaの記述によれば、上記用語のHeadはLeadingと表されることもあり、両者は定義的に同一のものである。

なので、

$LT(f)$ ... Leading Term
$LC(f)$ ... Leading Coefficient
$LM(f)$ ... Leading Monominial

と書いても同じこと。

Spolyでやっていること

$f, g$のなるべく小さい単項式倍の中から頭項が一致するものを選んでその後を消去したもの（→ 掃き出し操作の一般化）、掃き出し操作とは連立方程式を解くための効率の良いアルゴリズムのこと。掃き出し法

次に、$Spoly(f,g)$の実際の計算例について

「グレブナー基底の計算実践篇 Risa/Asirで解く」, p127 より引用

書籍の計算例に間違いがあるようなのでこちらで修正している

例 3.26（S多項式の計算）

$${\begin{aligned} & \left\{ \begin{array}{l} f(x, y) = x^5-2yx^2+y^5 \\ g(x, y) = x^2+y^2-1. \end{array} \right. \\ & \\ & 与えられた多項式の頭項と頭係数は、\\ & \\ & \left\{ \begin{array}{l} HT(f) = x^5, HC(f) = 1 \\ HT(g) = x^2, HC(g) = 1. \end{array} \right. \\ & \\ & であるから、頭項の最小公倍式は、 \\ & \\ & lcm(HT(f), HT(g)) = x^5 \\ & \\ & となる。そこでS多項式は、 \\ & \\ & Spoly(f, g) \\ &= \frac{x^5}{(1) \cdot x^5}f - \frac{x^5}{(1) \cdot x^2}g \\ & = (x^5-2x^2y+y^5) - (x^5-x^3y^2-x^3) \\ & = x^3y^2+x^3-2x^2y+y^5 \\ \end{aligned} }$$

これで$Spoly(f,g)$の中身が具体的にわかった。SpolyはS-Polynomialを表すが、Sとは何なのだろう…？

$f \xrightarrow[G]{} g$ または $f \xrightarrow[G]{*} g$ (＝単項簡約)

有限多項式集合$G$に属する多項式による単項簡約を１回行う、あるいは０回以上繰り返すことにより$h$が得られたとき、それを $f \xrightarrow[G]{} h$ 、 $f \xrightarrow[G]{*} h$ で表す
単項簡約がもう実行できないとき、$f$は$G$に対して正規形であると言う。

TODO

単項簡約の計算例を後で書く

参考

前提知識部分の内容は JOISS2015 グレブナー基底発表joisinoお姉ちゃんを救おうと被っている
「グレブナー基底の計算基礎編計算代数入門」
「グレブナー基底の計算実践篇 Risa/Asirで解く」

次はRubyで実際にグレブナー基底を計算する予定