数理情報科学特論 グレブナー基底

\[(f_1(x, \ldots, z) =0, \cdots, f_n(x, \ldots, z) =0)\]

に対し，\(f_1, \ldots, f_n\) を組合わせでできる任意の多項式

\[A_1(x, \ldots, z) f_1(x, \ldots, z) + \cdots + A_n(x, \ldots, z) f_n(x, \ldots, z)\]

の集合を考えます．

この集合を \((f_1, ... , f_n)\) と表し，\(f_1\) から \(f_n\) が作る イデアル \({\cal I}\) と呼ぶ．

\({\cal I}\) を作ることのできる多項式の組をイデアルの基底と呼びます．

方程式を解くのに都合の良い基底を求めることは，同じ根を持つ，より簡単な 方程式系への変換となる．

この基底が例えば，

\[(g_1(x, z) =0, g_2(y,z) = 0, \cdots, g_m(z) =0)\]

という形で求まれば，多変数方程式の問題は， 一変数方程式の 問題に帰着される．

「このような変形はできるのか」，「変形する方針は」，「必ず求まるのか」 などが問題となる．

ウィスキーのグラス \(W\), ビールのグラス \(B\), お酒のグラス \(S\) が 一列に並んでいる.

グラスは次の置き換え規則で, 置き換えて良いとする.

\[置き換え規則 G \left\{ \begin{array}{rll} B & \leftarrow\rightarrow & W B\\ BS& \leftarrow\rightarrow & W \\ \end{array} \right.\]

1. \(BSBS\) は \(WWWB\) に置き換えできるか？
2. \(BSBBS\) は \(BWW\) に置き換えできるか？

• できる場合はその置き換えを示せば良いが,
• できない事を示す事.

• 簡単な方へ置き換える (簡約化)ことにする. \[簡約規則 R \left\{ \begin{array}{rll} WB & \rightarrow & B\\ BS & \rightarrow & W \\ \end{array} \right.\]
• これ以上簡約できないもの (正規形)

• 置き換え規則 \(G\) で置き換え可能な列の要素は 簡約規則 \(R\) で同じ正規系を持つか？

  この性質が成り立てば, 簡約系で正規形が同じであれば, 置き換え系で,置き換え可能となる.

• 置き換え可能なのに, 同じ正規形を持たない場合は, そのような簡約規則を追加すればよい.

  例えば, \(WBS\) は二つの

  \[\left\{ \begin{array}{rllll} WBS & \rightarrow & WW\\ WBS & \rightarrow & BS & \rightarrow & W\\ \end{array} \right.\]

  置き換え系では, \(WW\) と \(W\) は, \(WBS\) を通して置き換え可能である から, 簡約系で

  \[WW \rightarrow W\]

  を新しい簡約規則として採用すればいい事になる.

  この追加される簡約規則を同やって見付けるかが問題となる.

• 簡約規則の左項中で, 重なりが生ずるような二つの規則を探す. (この二つの簡約規則を*危険対*と呼ぶ).

  今の場合, \(BS\) と \(WB\) は 重なりを持つ項, \(WBS\) を別の正規形に簡 約する可能性を持つ.

• この操作を次々に繰り返し, 危険対が全て同じ簡約形を持つよう になった時, 置き換え可能である物は, 全て同じ正規形を持つ事になる.

簡約系の*完備化*という.完備な系とは,

• 正規系は有限ステップで求まる. (停止性)
• ある項の正規系は, 簡約順序によらず同じになる.(合流性)

簡約規則 \(R\) を完備化すると,

\[簡約規則 R' \left\{ \begin{array}{rll} WB & \rightarrow & B\\ BS & \rightarrow & W \\ WW & \rightarrow & W \\ \end{array} \right.\]

が得られる. これで, \(BSBS \rightarrow^* W\), \(WWWB \rightarrow^* B\), なので,置き換え可能ではない.

\(BSBBS \rightarrow^* BW\), \(BWWW \rightarrow^* BW\), なので,置き換え可能となる.

*これがどう方程式と関係しているのでしょう？ *

いくつの順序が考えられ, 順序によって完備な簡約系が異る.

辞書式順序:

： \(xyz > yz^3 > z^5\)

全次数辞書式順序:

\(x^5 > x^4y > x^3yz\)

基底の先頭項を残りの項で置き換える簡約規則と見て， 項をより低順位項で置き換える操作．

• 例２.１:: \(g_1\) を \(g_2\) でM簡約

  \(g_1 = x^4yz - xyz^2~~~(~head(g_1) = x^4yz~~,~~rest(g_1) = xyz^2~)~\)

  \(g_2 = x^3yz - xz^2~~~(~head(g_2) = x^3yz~~,~~rest(g_2) = xz^2)~\)

\[\begin{array}{ll} g' & = g_1 - ( head(g_1) / head(g_2) ) g_2 \\ & = g_1 - ( x^4yz / x^3yz ) g_2 \\ & = x^2z^2 - xyz^2 \end{array}\]

新たな簡約規則を得るための計算．

２つの多項式 \(f_1,f_2\) のS多項式を \(Sp(f_1,f_2)\) と書き、以下のように計算する。

\[Sp(f_1,f_2)= \frac{lcm}{head(f_1)}f_1 - \frac{lcm}{head(f_2)}f_2\]

• 例２.２:: \(g_1\) と \(g_2\) のS多項式

  \(g_1 = x^3yz - xz^2,\ \ head(g_1) = x^3yz\)

  \(g_2 = x^2y^2 - z^2,\ \ \ head(g_2) = x^2y^2\)

  \(lcm(head(g_1), head(g_2)) = x^3y^2z\)

  \[\begin{array}{ll} Sp(g_1,g_2) &= ( lcm / head(g_1) ) g_1 - ( lcm / head(g_1)) g_2 \\ &= ( x^3y^2z / x^3yz ) g_1 - ( x^3y^2z / x^2y^2 ) g_2 \\ &= -xyz^2 + xz^3 \end{array}\]

イデアル \({\cal I}\) の基底を \(G={f_1,\cdots,f_n}\) とする。

\(F\) を可能な限りM簡約した結果を \(F'\) とし，

\[F \stackrel{G}{\longmapsto} F'\] と表す.

\({\cal I}\) の任意の要素 $f$に対し，

\[f \stackrel{G}{\longmapsto} 0\] という性質を持つとき，\(G\) をグレブナー基底と呼ぶ。

\(G\) がグレブナー基底の時，\(f \stackrel{\psi}{\longmapsto} f'\) を計算 し，\(f'=0\) を調べることで、\(f \in {\cal I}\) であるかを簡単に決定できる.

例２.３

\(f_1,f_2,f_3\) のグレブナー基底を求める。(全次数辞書式順序）*

$$\left\{

\begin{array}{l} f_1 = 2{x_1}^3x_2 +6{x_1}^3-2{x_1}^2-x_1x_2-3x_1-x_2+3\vspace{.2in}\\ f_2 = {x_1}^3x_2 + 3{x_1}^3 + {x_1}^2x_2 + 2{x_1}^2\vspace{.2in}\\ f_3 = 3{x_1}^2x_2 + 9{x_1}^2 + 2x_1x_2 + 5x_1 + x_2 -3 \end{array}

\right.$$

(ｓ多項式の例）

\(\begin{array}{ll} Sp(f_1,f_2) &= ( lcm / head(f_1) ) f_1 - ( lcm / head(f_1)) f_2 \\ &= ( 2{x_1}^3x_2 / 2{x_1}^3x_2 ) f_1 - ( 2{x_1}^3x_2 / {x_1}^3x_2 ) f_2 \\ &= -2x_1^2 x_2 -6x_1^2 -x_1 x_2 - 3x_1 -x_2 +3 = f'_4 \end{array}\)

（Ｍ簡約の例）

\(\begin{array}{lll} f'_4 & \stackrel{f_3}{\longmapsto} & f'_4 - (-2x_1^2 x_2 /{head(f_3)})f_3 \\ & = & x_1 x_2+ x_1 -x_2 +3 \end{array}\)

＜\(f_1,f_2,f_3\) のグレブナー基底＞ \[G = [x_1 x_2 + x_1- x_2 + 3, 2{x_1}^2 - 3 x_1 + 2 x_2 - 6, 2{x_2}^2 - 8 x_1 - 5 x_2 -3]\]

Input: $F = \{ f_1, \ldots, f_l\}$
Output: Gröbner基底 \(G\) of \(Ideal(F)\)

#+BEGIN_QUOTE \(PairQ \longleftarrow \phi\);
\(G \longleftarrow \phi\);

foreach (\(f_i \in F\)) \(\{\)

#+BEGIN_QUOTE $ PairQ \longleftarrow UpdatePairQ(PairQ, f_i, F)$;
$ G \longleftarrow UpdateBase(G, f_i)$;

\(\}\)

while ( \(PairQ \ne \phi\) ) \(\{\)

\((g_i, g_j) \longleftarrow\) select an element of \(PairQ\);
\(PairQ \longleftarrow PairQ \setminus \{(g_i, g_j)\}\);
\(g_k \longleftarrow {{{\mathrm{SPOL}}(g_i, g_j)\!\downarrow_{G}}}\);

if $g_k ≠ 0 $ \(\{\)

#+BEGIN_QUOTE \(PairQ \longleftarrow UpdateQ(PairQ, g_k, G)\);
\(G \longleftarrow UpdateBase(G, g_k)\);

\(\}\) #+END_QUOTE

\(\}\) #+END_QUOTE #+END_QUOTE

• $G$は中間的な基底の集合，\(PairQ\) は新たな基底を構成可能な 中間基底の組 (ペア)の集合，を表している．
• \(PairQ\) から一つのペア \((g_i, g_j)\) を選ぶ． この選び方を選択戦術と呼ぶ．
• \({\mathrm{SPOL}}(g_i, g_j)\) の現在の中間基底での正規形$g_k$を求める． 簡約基底の選び方の順序や簡約法を簡約化戦術と呼ぶ．
• $g_k$が0でなければ，
  • ペア削除戦術により，新たなペアの生成と，不必要なペアの削除をお こない(\(UpdateQ\))，
  • 中間基底に追加し，基底削除戦術により不必要な中間基底の削除をおこ なう (\(UpdateBase\))，
• \(PairQ\) が空になった時点で算法は停止し， \(G\) に Gröbner 基底が求まる．

Buchberger算法の計算上の問題点は，ペアの個数の組み合わせ的な膨張と，中 間基底の数係数の膨張である．ペアの個数の膨張を防ぐために，いくつかの選 択戦術が考えられており，選択戦術を保持したまま，ペアの個数に関する並列 性の導入が必要となる \cite{strategy-accurate}．

野呂ら\cite{noro97-ap}は, 数係数の膨張による計算時間の増大を，並列計算 により減らせることを示した．筆者\cite{asir-para}は，共有メモリを用いて 更に高速化を行った．一つの基底によるS多項式の簡約 (\({{{\mathrm{SPOL}}(g_i, g_j)\!\downarrow_{\{g_k\}}}}\)) を${\mathrm{SPOL}}(g_i, g_j)$や$g_k$を分割 し，並列計算する．これを*一簡約並列*と呼ぶ．この方式では，

• 全ての戦術を保持したまま並列計算が可能であるが,
• 細粒度の並列化であり，有効となるのは数係数が大きくなった場合に限る，
• 逐次部分が残る．

この方式は，大規模なGröbner基底計算\cite{noro97-mckay}において，並 列度が中規模($ ≤ 20$) 程度であれば良い性能を示している \cite{noro97-ap,asir-para}．しかし計算の逐次部分，通信コストのために， 性能限界を持つ．

\cite{strategy-accurate}では， 選択戦術を忠実に守りつつ，ペアに関する簡約 (\({{{\mathrm{SPOL}}(g_i,g_j)\!\downarrow_{G}}}\)) を並列に行っている．$G$を共有し，複 数のワーカが別々の簡約を行う．以後，この並列化を*ペア並列*と呼ぶ． ペア並列では，

• 逐次部分がないが，
• 中間基底の生成順序を保つため，S多項式の生成，簡約化に待ち が生ずる，
• 無駄な計算 (0簡約される基底を用いたペア)が生ずる．

この方式では, 中間基底の生成順序による待ちがボトルネックとなり， 様々な問題に対して性能限界が生じることが報告されている． この論文中，斉次な基底計算の場合，生成順序による待ちが大幅に減らせ， 高い並列性能を示すことが言及されているが，その性能は示されていない．

S多項式の全次数(またはsugar次数) \(d\) で打ち切った Buchberger 算法の結果を \(G_d\) とする．この$G_d$のことを*$d$-グレブナー基底* という．

[th-d] 斉次多項式 \(f_1, \ldots, f_n\) に対する$d$-グレブナー基底は以下の性質 を持つ：

1. $°(f) < d $ な \(f\) に対し, \({{\!\stackrel{G_d}{\longrightarrow^{*}} }}\) が定義さ れる．
2. \(\forall p \in {\mathcal{I}} \ \deg(p) \le d\) \(\Rightarrow\) \({{p\!\stackrel{G_d}{\longrightarrow^{*}} 0}}\)
3. \(\forall f, g \in G_d\) $°({\mathrm{HT}}(f),{\mathrm{HT}}(g)) ≤ d $に対し， \({{{\mathrm{SPOL}}(f, g)\!\stackrel{G_d}{\longrightarrow^{*}} 0}}\)

\(\forall d > d_\infty \ G_d = G_{d_\infty}\) となる $d_∞$が存在する． □

任意の多項式に対し，定理[th-d]の$°$を\(\deg_S\) で置き換えて，性 質 1, 2, 3 および\(d_{infty}\) の存在が成り立つ．

定理より$d$-グレブナー基底は，

\[G_0 \rightarrow G_1 \rightarrow \cdots \rightarrow G_{d} \rightarrow G_{d+1} \rightarrow \cdots \rightarrow G_{d_\infty} = \cdots\]

のように計算でき，\(G_d = G_{d-1} + \{d\mbox{-次式}\}\) となる．

前節の定理より，$G_d-1$が求まっていて，$G_d$を求める場合は， 次の事が言える．

1. \(G_d\) に追加される基底は， \({\mathrm{SPOL}}(g_i, g_j)\), \(g_i, g_j \in G_{d-1}\), より作られ，基底候補のS多項式に依存性はない．
2. \({{{\mathrm{SPOL}}(g_i, g_j)\!\downarrow_{G_{d-1}}}}\) の計算にも 依存性はない．
3. 上の計算後，\({{{\mathrm{SPOL}}(g_i, g_j)\!\downarrow_{G_{d}}}}\) の計算は， 1,2 で作られた $d$-次基底のみの相互簡約で求められる．

つまり，S多項式の並列生成，$G_d-1$に関する並列簡約，が可能である． $d$-次基底の相互簡約には基底間の依存性が存在するが， これは一簡約並列実行可能である．