数理解析研究所講究録
第 1815 巻 2012 年 46-57

46

グレブナー基底算法における項キャンセルの一般論
佐々木建昭 (Tateaki Sasaki) *筑波大学名誉教授 (数学系)
PROFESSOR EMERITUS, UNIVERSITY OF TSUKUBA
Abstract
Buchberger の算法は浮動小数係数のグレブナー基底計算では非常に不安定であるが、その最大の理由は頻繁な項キャンセルによる巨大な桁落ち誤差の発生である。従来はSylvester の恒等式に基づいて、 ごく限られた場合にだけ正確な項キャンセルが証明されていた。 本稿は、 Buchberger 算法に現れる多項式を部分終結式もどきの行列式
で表すことにより、 組織的で正確な項キャンセルの一般論の構築する。

1

はじめに
本稿では、 係数に誤差を含む多変数多項式系に対して、 Buchberger 算法でグレブナー

基底を計算することを念頭におく。この計算は非常に不安定であるが、その最大の理由は“正確で組織的な項キャンセル” によることが知られている。たとえば、次の簡単な入力に対して下記の連続した$S$

多項式計算を実行してみよう。

$=$$(P_{1},
P_{3})=$$(P_{2}, P_{3})=$$=x^{4}y+x^{2}y-2xy^{2},$$P_{1}$$P_{3}$$P_{4}$$P_{5}$$P_{6}$$P_{2}=x^{2}y^{3}+2x^{2}y-3xy^{2}$
$/*$

$=$

Spol

$=$

Spol

$=$

SPol $(P_{4},回は微小な数を表す

P_{5})=yP_{4}-xP_{5}=$瑠の計算では、回を含まない項が全て正確にキャンセルしている。 この例は、 正確な項
キャンセルが組織的に起きることを示唆するとともに、回が微小数のとき、 キャンセル
後には微小な項だけが残る、 すなわち巨大な桁落ち誤差が生じることを示している。
上記の型の項キャンセルは論文 [10] で理論的に解明されており (2 章を参照)、もう少し別の場合も論文 [11] で扱われている。一般論は多項式剰余列の場合の部分終結式理論に対応し、 算法で現れる多項式を入力多項式の係数ベクトルの行列式で表すことが目的である。一般論の構築は、 1980 年代、 Buchberger 自身や Collins らにより試みられ (論文 [6]参照) 最終的に Mandache[6] により “部分終結式のような行列式表現は存在しない” と、sasaki@math.tsukuba.ac.jp

$*$

47
されている。本稿は、 部分終結式をかなり拡張すれば行列式表現が得られることを示す。
ここで “拡張 “ とは、 部分終結式の元となる行列からある列を除去したり、 元となる行列にはない列や稀には行を付加することもある。行列式表現に基づけば、 どのような場合にどの程度の大きさの項キャンセルが生じるかの解明は容易である。

2

従来研究のサーベイ

本章では種々の記号の定義をするとともに、 上記の例を説明する理論を簡単に述べる。
そして、 部分終結式の拡張の一つとして、 列の除去が頻繁に必要であることを示す。
変数 $x,$ $y,$の多項式を $F$ や $G$ 等と表し、それらの係数をそれぞれゐや 等と表す。
は多項式環に設定された項順序とし、 に関する $F$ の最高順位項を主項といい lt $(F)$ と表し、 その係数を主係数といって lc $(F)$ と表す。変数のべきの積をべき積という。 $F$ の主項に現れるべき積を主べき積といい $1pp(F)$ と表す :lt $(F)=$ lc $(F)1pp(F)$$F$ と $G$ の多項式を Spol $(F, G)$ と、 $F$ の $G$ による主項簡約を Lred $(F, G)$ と表す。後者は$F$ 逸と図示することもある。
はが $G$ 既約になるまでの連続簡約を意味する。
部分終結式を構成する際には、行列要素が多項式の係数となるように、 多項式の割り算
を擬除算で定義する。 同様に、 本稿の場合には 多項式と主項簡約を次式で定義する。
$\ldots,$$z$$g_{j}$$\mathbb{C}[x, y, \ldots, z]$$\succ$$\succ$。

$S$$Farrow^{G}\tilde{F}$$\tilde{F}$$S$

Spol $(F, G)=$ lc $(G)[L/1pp(F)]F-$ lc $(F)[L/1pp(G)]G,$
Lred $(F, G)=$ lc $(G)F-$ lc $(F)$ [lpp(F)/lpp(G)] $G.$

(2.1)

ここで、 $L=$ lcm $(1pp(F)$ , lpp $(G))$ である。 $F$ と $G$ が次式で与えられる場合をみよう。
$F=f_{1}T_{1}+f_{2}T_{2}+\cdots+f_{m}T_{m}, G=g_{1}S_{1}+g_{2}S_{2}+\cdots+g_{n}S_{n}$とする。簡単のため、であるとすれば、 $Spo1(F, G)$ は次式のように行列式で表現できる。

ただし男， はべき積で、$S_{j}$$S_{i}=T_{i}(i=1,2, \ldots)$(2.2)$T_{1}\succ T_{2}\succ\cdots\succ T_{m},$$S_{1}\succ S_{2}\succ\cdots\succ S_{n}$$g_{1}(f_{1}T_{1}+f_{2}T_{2}+\cdots)-f_{1}(g_{1}T_{1}+g_{2}T_{2}+\cdots)$$g_{1}f_{1}$$g_{2}f_{2}|T_{2}+|\begin{array}{ll}g_{1} g_{3}f_{1} f_{3}\end{array}|T_{3}+|g_{1}f_{1}$$g_{4}f_{4}$$T_{4}+\cdots$$n\geq k+1$ , と
上記のような行列式表現を行列で簡潔に表そう $[2]_{0}M$ は $(k+1)\cross n$ 行列，$i\geq k+1$ , からなる行列式をし、第 列にはべき積 を対応させる。 $M$ の左 列と第 列，とすれば、 行列 $M$ と多項式 $P= \sum_{i=k+1}^{n}c_{i}T_{i}$ が一対一に対応する。 このとき、 $M$ を $P$に対する簡約行列という。 例えば上記 Spol $(F, G)$ に対応する簡約行列は次である。
$i$$T_{i}$$k$$i$$c_{i}$$(\begin{array}{lllll}g_{1} g_{2} g_{3} g_{4} \cdots f_{1} f_{2} f_{3} f_{4} \cdots\end{array})$(2.3)

亀 $=T_{i}$ が成立しない場合には条件が成立するように 係数項を付加する。 $S_{1}=T_{1}$ さえ成立しない場合には、 適当なべき積 $S$ と $T$ により $SS_{i}=TT_{i},$ $(i=1,2, \ldots)$ , が成立する
ように 係数項を付加すればよい。 一方、 主項簡約の方は少し注意を要する。
$0$

$0$

48
より一般の
このとき、

$\tilde{F}$$Farrow^{G_{1}}F_{1}arrow^{G_{2}}$は $F,$...

なる簡約で説明する。 ここで $G_{i}=G_{j}$ でもよい。
により次のように表される。
とべき積$U_{1},$$G_{k}$$G_{1},$$arrow\tilde{F}G_{k}$$\ldots,$$U_{k}$$\ldots,$(2.4)$\{\begin{array}{l}\tilde{F}=aF+b_{1}U_{1}G_{1}+b_{2}U_{2}G_{2}+\cdots+b_{k}U_{k}G_{k},a=\prod_{i=1}^{k}1c(G_{i}) , b_{1}, b_{2}, \ldots, b_{k}\in \mathbb{C},U_{1}G_{1}\succ U_{2}G_{2}\succ\cdots\succ U_{k}G_{k}.\end{array}$$1c(G_{i})=g_{i,1},$$(i=1, \ldots, k)$, とおき、 $F$ と$U_{1}G_{1},$$\ldots,$$\{\begin{array}{l}F =f_{1}T_{1}+f_{2}T_{2}+\cdots+f_{n}T_{n}+0T_{n+1}+\cdots,U_{1}G_{1}=g_{1},{}_{1}T_{1}+g_{1},{}_{2}T_{2}+\cdots+\cdots,:

ここで $fi,$$g_{1,1},$$\ldots,$$U_{k}G_{k}$を次のように表す。

(2.5):U_{k}G_{k}=0T_{1}+\cdots+g_{k},{}_{1}T_{k’}+g_{k},{}_{2}T_{k’+1}+\cdots\end{array}$

は $0$ ではないが、簡約行列の列を揃えるために、他の係数には $0$ も$g_{k,1}$あり得る (ほとんどの場合に、ある)。以下では、 $(f_{i}, f_{2}, \cdots, f_{n}, 0, \cdots),$ $(0, \cdots, g_{i,1}, g_{i,2}, \cdots)$の係数ベクトルを行とをそれぞれ $F$ との係数ベクトルと呼ぶ。 $F,$
$U_{1}G_{1},$$U_{i}G_{i}$$\ldots,$$U_{k}G_{k}$する行列がそのまま簡約行列にはならない場合があることを、例でみよう。
例1$F=x^{2}y-xy^{2}+2xy-3y^{2}+2x,$ $G=xy-y^{2}-y$$\succ$、は全次数順序とする。

$F$ は $G$ で 2 回簡約され、 $F-xG-3G=\tilde{F}$ となる。 $F,$ $xG,$ $G$ に現れるべき積の集合は$\{x^{2}y, xy^{2}, xy, y^{2}, x, y\}$であり、 この集合上での $F,$ $xG,$ $G$ の係数ベクトルからなる行列は$(\begin{array}{lllllll} x^{2}y xy^{2} xy y^{2} x yxG 1 -1 -1 0 G 1 -1 0-1F 1 -1 2 -3 2 0\end{array})$となる。 この行列の先頭の 2 列とそれぞれ第 3 列，．
．
．
，第 6 列からなる四つの 3 次行列式になる。第 2 列を除去し、 第 1 列と第 3 列およびそれぞれ第 4なる三つの行列式を計算すれば、 $\tilde{F}=0y^{2}+2x+3y$ の各係数が得られる。
はいずれも

$0$

$\sim$

第 6 列から◇に戻る。上記の例で第 2 列を除去する理由は、(2.5) の $F,$
. . . を表す行列式表現を順に構成していけば簡単に分かり、 次の定理が得られる。
$G_{1},$

定理 1([10]) $F,$

$Farrow^{G_{1}}F_{1},$$G_{k}$$F_{1}arrow^{G_{2}}F_{2},$$\ldots,$$G_{1},$$G_{g},\tilde{F}$$\ldots,$を上にように定めるとき、$\tilde{F}$は次のように表現できる。
$\ldots$$g_{2,1}$$\tilde{F}=\sum_{i=1}^{n’-k}$$g_{1,1}f_{1}$$g_{1,2}f_{2}$$\cdots$:$g_{2,k-1}g1,kg_{k,1}f_{k}$:$g_{k,1+i}g_{2,k-1+i}g1,k+if_{k+i}|T_{k+i}=|g_{1,1}f_{1}$$g_{2,1}g_{1,2}f_{2}$:$g_{1,k}g_{2,k-1}g_{k,1}f_{k}$:$U_{k}G_{k}U_{2}G_{2}U_{1}G_{1}F$

...
(2.6)

49
ここで簡約行列は、要素べき積$T_{1},$ $T_{2},$$\ldots,$$T_{k},$$\ldots$が対角上にくるように、 列が既に除去されており、は除去されずに残った列に順に対応するものとする。
$g_{1,1},$$\ldots,$ $g_{k,1}$$\theta$

定理 1 を使えば、第 1 章に例示した項キャンセルが次のように定式化される。多項式 $F$...
...
と $F’$ が次式で与えられたとして、とを考える。
$Farrow^{G_{1}}$$F’arrow^{G_{1}}$$arrow^{G_{k}}\tilde{F}$$arrow^{G_{k}}\tilde{F}’$$F=f_{1}T_{1}+f_{2}T_{2}+\cdots+f_{n}T_{n},$$T_{i}=T’T_{i}’(i=1,2, \ldots, n)$

.

(2.7)

$F’=f_{1}’T_{1}’+f_{2}’T_{2}’+\cdots+f_{n}’T_{n}’,$定理 1 によれば、$f_{1}g_{1,1}.\cdot.\cdot.$$\tilde{F}$$g_{k,1}f_{k}g_{1,k}:,$と$\tilde{F}’$は行列式で表現でき、 Spol$(\tilde{F},\tilde{F}’)$$f_{k+1}g_{k1+1}g_{1.k+1}:,.|\cdot|\begin{array}{llll}g_{1,1} \cdots g_{1,k} g_{1,k+i} \ddots \vdots \vdots g_{k,1} g_{k,1+i}f_{1} \cdots f_{k} f_{k+i}\end{array}|$$g_{1,1}$$g_{1,1}$...

の $T_{k+i}$ 項の係数は$|\begin{array}{l}same\vdotssamef_{j}arrow f_{j}\end{array}|\cdot|\begin{array}{l}same\vdots f_{j}arrow f_{j}’same\end{array}|(2.8)$$g_{1,k}$$g_{1,k+1}$$g_{1,k+i}$$g_{k,1}f_{k}$$g_{k,1+1}f_{k+1}$$g_{k,1+i}f_{k+i}$$f_{k}$$f_{k+1}$$f_{k+i}$

...

$=$

$g_{k1}g_{1,.k}:’,|.$(2.9)$.\cdot.\cdot.$$f_{1}’$$f_{1}$...

と表現することができる。 ここで、 (2.8) から (2.9) への変換は Sylvester の恒等式による。
この式によれば、 Spolの計算において、 積を含まない項は全て正確にキャンセルすることがわかる。
$(\tilde{F},\tilde{F}’)$$g_{1,1}\cdots g_{k,1}$

上記の項キャンセルは、数値行列でピボッティングなしの場合のキャンセルと全く同じメカニズムによる。 しかしながら、 Buchberger 算法における項キャンセルは数値行列のキャンセルよりも複雑で、 Sylvester の恒等式だけでは解明できない。
上記では非主項は簡約されていない。 同様に、 本稿を通じて次を仮定する。
前提 1 本稿では 多項式生成と主項簡約だけを用いてグレブナー基底を計算する。得られる基底は未簡約基底であり、 簡約基底が欲しい場合は最後に非主項を簡約する。
$S$

3

多項式剰余列型の簡約に対する行列式理論

部分終結式の定式化は Collins[2] らによりなされたが、 かなり面倒である。 Buchberger
算法における項簡約を部分終結式と同様に定式化すれば、 はるかに面倒になるのは明白である。 ところで、 筆者と古川は [9] において多重多項式剰余列を定式化したが、 そこでは“逆簡約” という方法が考案された。 簡約手順を逆にたどりつつ簡約行列を構成する方法である。本章では、扱い易い多項式剰余列型の項簡約に対して逆簡約法で簡約行列を構成することにより、 新しい定式化の簡潔さを示す。

50
次のような連続簡約を多項式剰余列型の簡約と呼ぶ。
(3.1)$P_{1}arrow^{P_{2}}P_{3}, P_{2}arrow^{P_{3}}P_{4}, \ldots, P_{i-1}arrow^{P_{i}}P_{i+1}, \ldots$

1 変数の場合、$(P_{1}, P_{2}, \cdots , P_{k})$は多項式剰余列に他ならず、 大きな項キャンセルが頻繁に起きることがよく知られている。多項式剰余列型の簡約に対しては部分終結式が素直にの A による島回の簡約とが拡張できることを示す。 (3.1) において、$P_{i-1}arrow^{P_{\mathfrak{i}}}P_{+1}$

するならば、$P_{i+1}$$P_{i-1}$は次のように表現できる。

(3.2)$P_{i+1}=$ $lc$ $(P_{i})^{k_{i}}P_{i-1}+b_{i,1}U_{i},{}_{1}P_{i}+\cdots+b_{i,k_{i}}U_{i,k_{i}}P_{i}$ここで、$b_{i,1},$は数であり、$b_{i,k_{i}}$$\ldots,$$U_{i,1},$$\ldots,$$U_{i,k_{i}}$はべき積で $U_{i,1}\succ\cdots\succ U_{i,k_{i}}$ である。

$supp(P_{i-1})\cup\bigcup_{j=1}^{k_{i}}supp(U_{i},{}_{j}P_{i})=\{T_{i},{}_{1}T_{i}, {}_{2}T_{i,n_{i}}\},$

集合上で係数ベクトルを定義すれば、$P_{i+1}$$T_{i,1}\succ T_{i,2}\succ\cdots\succ T_{i,n_{i}}$は次の簡約行列で表現できる。

coefficientvectorof U$M_{i+1}^{(i)}=$とし、 この$,{}_{1}P_{i}$(3.3)$coefficientvectorofU_{i},{}_{k}\dot{P}_{i})$$($coefficientvectorof P
行列を$P_{i-2}$と $P_{i-1}$ の係数ベクトルで表そう。 (3.2) と同様、

$P_{i}$

は次のように表せる。

$P_{i}=1c(P_{i-1})^{k_{l-1}}P_{i-2}+b_{i-1,1}U_{i-1},{}_{1}P_{i-1}+\cdots+b_{i-1,k_{i-1}}U_{i-1,k_{i-1}}P_{i-1}$

まず、 簡約行列に必要なべき積集合を$U_{i,1}U_{i-1,k_{l-1}}P_{i-1},$$\ldots,$$U_{i},{}_{1}P_{i-2},$$U_{i,k_{i}}U_{i-1,k_{i-1}}P_{i-1}$$\ldots,$$P_{i-1},$$U_{i,1}U_{i-1},{}_{1}P_{i-1},$$\ldots,$に現れる全ての異なるべき積の集合に再定義する。

$U_{i,1}U_{i-1,k_{i-、}}P_{i-1},$
次に、 多項式に付加して次の行列をつくる。
を行列$U_{i,1}U_{i-1},{}_{1}P_{i-1},$$U_{i,k_{i}}P_{i-2},$(3.4)$\ldots,$$\ldots,$$U_{i,k_{i}}U_{i-1,k_{i-1}}P_{i-1}$の係数ベクトル$M_{i+1}^{(i)}$coeffi.cientve.

coeffici.

cientv.ectorof$c,toro.f,\cdot.U_{i},{}_{1}P_{i}$Untvectorof$coe.ffi.$

U$U_{i-1},{}_{1}P_{i-1}coefficientvectorof..U_{i1}U_{i-1}{}_{2}P_{i-1}$$\check{M}_{i+1}^{(i)}=$

$($

$e.$

(3.5)

$P_{i})$$U_{i-1,k_{i-1}}^{\cdot}P_{i-1}$

coefficientvectorof U
coefficientvectorof P$(j=1,2, \ldots)$ , になるの $(k_{i}+j,j)$ 要素，
前章に説明した理由で、 主係数 lc $(P_{i-1})$ がとように、 不必要な列は除去されるものとする。 lc $(P_{i-1})$ のべき乗を除けば、$(1\leq i\leq k_{i})$ , をは同じ行列式表現を与える。 (3.4) によれば、 上記行列は砺$\check{M}_{i+1}^{(i)}$$M_{i+1}^{(i)}$$P_{i-2},$$\check{M}_{i+1}^{(i)}$$P_{i-1}$

51で簡約するのに十分な行を含む。 したがって、換えることができる。

の上部$\check{M}_{i+1}^{(i)}$$k_{i}$

個の行を次式のように置き

coefficientvectorof U

coeffi. ecnotevffie.ci.entvectorofU$.’ {}_{1}P_{i.-2}C\circ e.C_{coefficientvectorofU_{i,i_{k}}U_{i-1,k_{i-1}}P_{i-1}}$$M_{i+1}^{(i-1)}=$$($$,P_{i-2}coefficient.vectorofP_{i-1})$

$ci.$

(3.6)

$ct.orofU_{i,1}U_{i-1},{}_{1}P_{i-1}$

上記の手順を逆簡約と呼ぶが、 これを繰り返すと次の定理が得られる。 なお、 以下では簡約行列 $M$ が表す多項式を DetPol(M) と表す。
定理 2ば、

$P_{1},$$M_{i+1}^{(i)}$(3.1) で生成される各$P_{2}$$P_{i},$$(3\leq i\leq k)$, は、 lc$(\check{M}_{i+1}^{(i)})/1c(P_{i-1})^{\neq a}$(3.7)のそれで置き換えるためには、 各ベクトルの乃の係数ベクトルをを掛ける必要がある。 したがって、 次式が成り立つ。

$\check{M}_{i+1}^{(i)}$$(P_{i-1})^{k_{i-1}}$$P_{i-2}$$DetPo1(\check{M}_{i+1}^{(i)})=$lc$(P_{i-1})^{k_{i}k_{i-1}}$

DetPolとこれらより、次の命題が直ちに得られ、行列係数であることから、 系も簡単に得られる (証明略)。
$M_{i+1}^{(i)}$命題 1, lc $(P_{i-2})$ のべき乗倍を除けに付加される行の個数を#a とすれば、 (3.3) と (3.5) より次式が得られる。

次に、 行列lc$\ldots$とそのべき積倍の多項式の係数ベクトルからなる簡約行列で表現できる。 ◇DetPol $(M_{i+1}^{(i)})=(-1)^{k_{i}\neq a}$ DetPol$l_{\overline{c}}$$(P_{2}),$$M_{i+1}^{(i-1)}$$(M_{i+1}^{(i-1)})$(3.8)の各要素が関連する多項式の上記の記号の下、 次の関係式が成立する。
$DetPo1(M_{i+1}^{(i)})=(-1)^{\#ak_{i}}$lc$(P_{i-1})^{k_{i}k_{i-1}-\#a}$

DetPol$(M_{i+1}^{(i-1)})$(3.9)

において、 lc
上記の記号の下、 #a $<k_{i}k_{i-1}$ ならば、を含まない項は正確にキャンセルする。 さらに、 lc $(P_{-1})|\ll\Vert P_{i-1}\Vert$ ならば、 キャンセル
する項は主要項 (多項式の中で係数が相対的に大きい項) である。
◇

系1

$P_{i-1}arrow^{P_{i}}P_{i+1}$$(P_{i-1})^{k_{i}k_{i-1}-\#a}$

$|$

4

$S$

多項式にかかわる簡約に対する行列式理論

第 2 章において、 Buchberger 算法の典型的な項簡約に対する簡約行列の構成では列を除去する必要性が頻繁に生じることを示した。本章では、逆に列を追加する必要性も頻繁に生じることを示す。

52
まず、次のような$S$多項式の簡約を考える。
$Sdef=Spo1(F, G)arrow^{H_{1}}$

ここで、$H_{1},$ $H_{2},$$\ldots,$$H_{k}$

...

(4.1)

$arrow\tilde{S}H_{k}$には同じものがあってもよい。 8 はべき積

$U_{1},$$U_{2},$$\ldots$, 砿で次のように表される。

(4.2)$\{\begin{array}{l}\tilde{S}=aS+b_{1}U_{1}H_{1}+b_{2}U_{2}H_{2}+\cdots+b_{k}U_{k}H_{k},a=\prod_{i=1}^{k}1c(H_{i}) , b_{1}, b_{2}, \ldots, b_{k}\in \mathbb{C},U_{1}H_{1}\succ U_{2}H_{2}\succ\cdots\succ U_{k}H_{k}.\end{array}$

一般性を失うことなく、 $1pp(F)=$ lPP $(G)=$ 乃を仮定する。 lc $(F)=f_{0、}$ lc$\ldots\}=supp(F)$ Usupp $(G)$ 火 $火_{}i=1^{k}supp(H_{i})$ ,lc $(H_{i})=h_{i,1},$ $(i=1, \ldots, k)$ , とおき、 To,, とする。 すると、 $F$ や $G$ などは次のように表される。
$(G)=g_{0\backslash }$$\{$$T_{1},$ $T_{2},$$T_{0}\succ T_{1}\succ T_{2}\succ\cdots$$\{\begin{array}{l}F =f_{0}T_{0}+f_{1}T_{1}+\cdots+f_{m}T_{m}+0T_{m+1}+\cdots,G =g_{0}T_{0}+g_{1}T_{1}+\cdots+g_{n}T_{n}+0T_{n+1}+\cdot\cdot \cdot,U_{1}H_{1}=h_{1},{}_{1}T_{1}+h_{1},{}_{2}T_{2}+\cdots+\cdots,::U_{k}H_{k}=0T_{1}+\cdots+h_{k},{}_{1}T_{k’}+h_{k},{}_{2}T_{k’+1}+\cdots\end{array}$

ここで、 係数$f_{j},$$g_{j}(i\geq 1),$ $h_{i,j’}(j’\geq 2)$

の中には

$0$

(4.3)

があってもよい。 次の定理は逆簡約の操作から簡単に証明できるので、 証明は省略する。
定理 3 士符号を除けば、 8 は次の簡約行列で表すことができる。 ただし、 主係数$(i=1, \ldots, k)$ , が $(i+1, i)$ 要素になるよう、余分な列は除去されるものとする。

$(g_{0}f_{0} h_{1,1}g_{1}f_{1} h_{1,2}g_{2}f_{2}.

次に、

$S$

h_{k,1}h_{1,3}g_{3}f_{3}.

h_{k,2} \ldots) \theta$$h_{i,1},$(4.4)

多項式による簡約を考える。 まず、 例で説明する。

例 2( 多項式による項簡約)$S$$H=2x^{2}y^{2}+3x^{2}y+y^{2}-5,$に対して、$S^{d}=^{ef}$$F=2x^{2}y^{2}-x^{2}y+x^{2},$$G=3x^{2}y^{2}-2x^{2}y+y^{2}$

Spol $(F, G)=x^{2}y+3x^{2}-2y^{2}$ で $H$ を簡約すると、 次のようになる。
$Harrow^{S}arrow^{s}\tilde{H}, \tilde{H}=4y^{3}+9x^{2}-5y^{2}-5$

53$\tilde{H}$の簡約行列は、 $H,$ $yS,$ $S$ の係数ベクトルで次のように表すことができる。

$(\begin{array}{lllllll} x^{2}y^{2} x^{2}y y^{3} x^{2} y^{2} 1yS 1 3 -2 S 1 3 -2 H 2 3 1 -5\end{array})$$S=3F-2G$ なので、 の係数ベクトルを $F$ と のそれで表し、 次の行列を作る : 行数
と列数の増加量を等しくするため、 べき積に対応する列を追加したことに注意。
$S$

$G$

$()$
$x^{2}y^{2}$

第 1 列を消去してみれば、 上記行列は士符号を除き
例 2 は容易に複数個の

$S$

多項式

$S_{1},$$S_{k}$$\ldots,$$Harrow^{s_{1}}$$\tilde{H}$(4.5)

を与えることが分る。

$\theta$による $H$ の簡約に一般化できる :

...

(4.6)

$arrow^{s_{k}}\tilde{H}$

ここで、 $S_{i}=$ Spol $(F_{i}, G_{i}),$ $(i=1, \ldots, k)$ , である。 各多項式を次のように表す。

(4.7)$\{\begin{array}{l}F_{i} = f_{i_{0}}T_{i_{0}}+f_{i_{0}+1}T_{i_{0}+1}+f_{i_{0}}{}_{+2}T_{i_{0}+2}+\cdots, f_{i_{0}}\neq 0,G_{i} = g_{i_{0}}T_{0}+g_{i_{0}+1}T_{i_{0}+1}+g_{i_{0}}{}_{+2i_{0}+2}T+\cdots, f_{i_{0}}\neq 0,H = h_{1}T_{1}+h_{2}T_{2}+h_{3}T_{3}+\cdots\cdots, h_{1}\neq 0.\end{array}$

ここで、$T_{1_{。}}\succ T_{2_{。}}\succ\cdots\succ T_{k_{。}}$

かつ乃。

$\succ T_{1}\succ T_{2}\succ T_{3}\succ\cdots$である。

定理 4 士符号を除けば、 倉は次の簡約行列で与えられる (証明略)。

.
$(g_{2,0}f_{2,0}|\cdots|_{g_{k,0}}f_{k,0}|^{f_{1,0}}g_{1,0}$$g_{2,0}g_{1,1}f_{2,0}f_{1,1}h_{1}$$.\cdot\cdot)$$g_{2,1}f_{2,1}g_{1,2}f_{1,.2}g_{k,0}f_{k,0}g_{2,2}g_{1,3}f_{2,2}f_{1,3}h_{k}$$h_{k+1}g_{k,1}f_{k,1}g_{2,3}f_{2,3}$$h_{k+2}g_{k,2}f_{k,2}$$\theta$

(4.8)

54
Buchberger 算法における項キャンセルの一般論

5

本章では、多重多項式剰余列を少し拡張する形で Buchberger 算法を捉えることにより、多重多項式剰余列理論をベースに Buchberger 算法における項簡約を定式化する。ただし、多重多項式剰余列理論は複雑なので理論の詳細は省き、定理とその証明の概要を述べる。
その定理に基づき、 Buchberger 算法における項キャンセルの一般論を展開する。

定義 1(多重多項式剰余列型の項簡約) 与えられた多項式集合を$s\geq 3$ , とする。 第番目の集合 (初期集合でもよい)$\{F_{1}^{(0)}, F_{2}^{(0)}, \ldots, F_{s}^{(0)}\},$を計算したとを選んで他の要素を簡約し、 第 $(i+1)$ 番目の集合$\{F_{1}^{(i)}, F_{2}^{(i)}, \ldots, F_{S}^{(i)}\}$$i$するとき、 その中から一つの要素$\{F_{1}^{(i+1)}, F_{2}^{(i+1)}, \ldots, F_{s}^{(i+1)}\}$$F_{r}^{(i)}$を次の算式で計算する。

(5.1)$F_{j}^{(i)}arrow F_{j}F_{r}^{(:)}(i+1) (\forall j\neq r) , F_{r}^{(i)}=F_{r}^{(i+1)}$

当然、$F_{j}^{(i)}=F_{j}^{(i+1)}$のこともあり得る。 最後の集合を$\{F_{1}^{(\lambda)}, F_{2}^{(\lambda)}, \ldots, F_{S}^{(\lambda)}\}$とする。 ◇

多重多項式剰余列型の項簡約に対しても、多項式剰余列型の項簡約と同様、簡約行列が簡単に構成できそうに思えるが、そうではない。非常に稀であるが、逆簡約の過程でごく一部の列にだけ非零要素を持つ行を付加する必要が生じる。その説明が多重多項式剰余列理論の主要部分を成すが、 その仕組みはかなり複雑である。 したがって、詳細については
論文 [9] を参照して頂くとして、本稿では紙面の制約もあり割愛する。
本稿では、 Buchberger 算法を多重多項式剰余列を修正する形で次のように定式化する。
に加える。
が生成された場合には、 は集合$S=$ Spol
は集合から除去する。 そして、 最も重要なことであるが に簡約された場合には、が、別の多項式で簡約する度に、次の集合に移行するものとする。 こうすれば、簡約行列$S$$(F_{j_{1}}^{(i)}, F_{j_{2}}^{(i)})$$F_{j}^{(\iota)}$$\{F_{1}^{(i+1)}, \ldots, F_{S}^{(i+1)}\}$$F_{j}^{(i)}$$0$の構成という点では多重多項式剰余列理論がそのまま使える。
定理 5(主定理) Buchberger 算法に現れる任意の多項式に対して簡約行列を構成できる。
簡約行列は、列に関してブロック構造をしており、 その行は入力多項式とそのべき積倍の“拡張係数ベクトル” である。 ここで、列ブロックとは行列 (4.8) でいえば縦線で囲まれた列集合であり、 拡張係数ベクトルとは、 一つの行は一つの多項式の係数のみを要素とし、各ブロック内では係数が高次から低次へと並べられて、さらに余分な列に対応する係数が除かれたものである。

, (i l)、最終基底 (Gr\"obner, FS(0)}、中間基底をとする。実際は最終基底が Gr\"obner 基底であることを確認するためにも計算が必要で、上述の多重多項式剰余列との対応では、 その計算でも基底番号が増加するが、 その計算は上記定理には無関係なので無視する。

証明初期基底を {基底) を$\{F_{1}^{(i)}, \ldots, F_{s}^{(i)}\}$$F_{1}^{(0)},$$\geq$$\ldots$$\{F_{1}^{(\lambda)}, \ldots, F_{t}^{(\lambda)}\}$$i=\lambda-1$の場合 :$F_{l}^{(\lambda)}=$SPol$(F_{j_{1}}^{(\lambda-1)}, F_{j_{2}}^{(\lambda-1)})$ならば$F_{l}^{(\lambda)}$は、$F_{j_{1}}^{(\lambda-1)}$と$F_{j_{2}}^{(\lambda-1)}$

の係数

ならば
ベクトルを行とする (2.3) のような簡約行列で表される。
は (2.6) において $G_{1}=\cdots=G_{k}=F_{r}^{(\lambda-1)}$ とした式に対応する簡約行列で表される。
$F_{l}^{(\lambda-1)F_{r}^{(\lambda-1)}}arrow F_{\iota}^{(\lambda)}$$F_{l}^{(\lambda)}$

55
が
の場合 :
及びそれらのべき積倍の多項式の拡張係数ベクトルを行とする簡約行列がで表されると仮定する。証明すべきは行列の係数を要素とする簡約行列 Ml(のに変換できることである。
の場合。
の拡張係数ベクトルを、 行列 (4.4) のように、$i\leq\lambda-2$$F_{1}^{(i+1)},$$F_{l}^{(\lambda)}$$F_{s}^{(i+1)}$$\ldots,$$M_{l}^{(i+1)}$$F_{1}^{(i)},$$M_{l}^{(i+1)}$$F_{s}^{(i)}$$\ldots,$$\bullet$$F_{\iota}^{(i+1)}=Spo1(F_{j_{1}}^{(i)}, F_{j_{2}}^{(i)})$$F_{l}^{(i+1)}$の拡張係数ベクトルで置き換えればよい。 2 個以上の行ベクトルを置き換える
場合は、 行列 (4.8) のように新たな列ブロックを追加する。
と$F_{j_{1}}^{(i)}$$F_{j_{2}}^{(i)}$$F_{l}^{(i)}arrow^{F_{r}^{(i)}}F_{l}^{(i+1)}$$\bullet$

で Fr(のがから成る行を必要なだけで置き換えればよい。
$F_{l}^{(i)}arrow^{F_{r}^{(i)}}F_{l}^{(i+1)}$$\bullet$$S$

多項式でない場合。 第 3 章のように、付加し、の係数ベクトルを$F_{l}^{(i+1)}$$M_{l}^{(i+1)}l_{\overline{C}}$$F_{r}^{(i)}$$F_{l}^{(i)}$の係数ベクトルの係数ベクトル

で $F_{r}^{(i)}=Spo1(F_{j_{1}}^{(i)}, F_{j_{2}}^{(i)})$ の場合。 (4.8) が示すように、Fr(のとそのべき積倍多項式の拡張係数ベクトルを$F_{j_{1}}^{(i)}$と$F_{j_{2}}^{(i)}$換え、 必要なだけ新たな列ブロックを追加すればよい。

$M_{l}^{(i)}$におけるの拡張係数ベクトルで置き◇

これまで述べた行列式理論によれば、 項キャンセルのメカニズムは明快に理解できる。
そのためには、 多項式の生成と主項簡約のあらゆる組合せについて、 具体的に行列式の$S$振舞いを解析すればよい。本稿では典型的な二つの場合を記述するが、残る場合も同様に
簡単に解析できることを指摘しておく。
[場合 I]

乃蝕．
．
．

に対して、 $S=$ SPol
各簡約を 1 回のみにしたことに注意されたい。 当然、 $G_{i,j_{1}}=G_{i,j_{2}}$ であってもよい。 これ$F_{1}arrow\cdotsarrow G_{1,1}G_{1,r_{1}}\tilde{F}_{1\backslash }$$G_{2,r,arrow\tilde{F}_{2}}2$$(\tilde{F}_{1},\tilde{F}_{2})_{0}$は定理 1 で扱った演算を一般化したものだが、 Sylvester の恒等式では解析できない。
簡単のため、と乃にはすでに必要なべき積が掛けられ、 $F_{i}=f_{i},{}_{1}T_{1}+f_{i},{}_{2}T_{2}+\cdots$
かつかつ$(i=1,2)$ , であるとする。 ここで、である。 すると、 は次の簡約行列で表される。
$F_{1}$$\tilde{F}_{i}=\tilde{f_{i}},{}_{11}\tilde{T}+\tilde{f_{i}},{}_{22}\tilde{T}+\cdots,$$T_{1}\succ T_{2}\succ\cdots$$S$$\ovalbox{\tt\small REJECT}\succ\tilde{T}_{2}\succ\cdots$$\tilde{M}_{S}$(5.2)$\tilde{M}_{S}=(\begin{array}{llll}\tilde{f}_{2,1} \tilde{f}_{2,2} \tilde{f}_{2,3} \cdots\tilde{f}_{1,1} \tilde{f}_{1,2} \tilde{f}_{1,3} \cdots\end{array})$$\tilde{F}_{i}=$

で、

[lc

$c_{i,1},$$(G_{i,1})$$\cdots$$\ldots,$ $c_{i,r}i$lc$(G_{i,r_{i}})$は数で]$F_{i}-\mathfrak{g}_{1}U_{i,1}G_{i,1}-\cdots-c_{i,r_{i}}U_{i,r_{i}}G_{i,r_{i}},$$U_{i,1},$$\ldots,$$U_{i,r}i$はべき積である。

$(i=1,2)$ , とする。 こことが定数倍$U_{1,j_{1}}G_{1,j_{1}}$$U_{2,j_{2}}G_{2,j_{2}}$を除き等しい場合は両者を同一視して、 $\{G_{1}’, G_{2}’, \ldots, G_{s}’\}:=俺_{}i=1^{2}\{U_{i,j}G_{i,j}|j=1, \ldots, r_{i}\},$とする。 行列 (3.3) から (3.5) への変換のように、 上記行列にとの係数ベクトルを付加し、の係数ベクトルをそれぞれと乃の係数ベクトルで置き換える。 すると、は次の簡約行列に変換される。
$G_{1}’\succ G_{2}’\succ\cdots\succ G_{s}’$$G_{1}’,$$G_{2}’,$$\ldots,$$\tilde{M}_{S}$$\tilde{F}_{1}$$G_{s}’$$\tilde{F}_{2}$$F_{1}$$M_{S}$$M_{S}= (\begin{array}{llll}g_{1,1}’ g_{1,2}’ \cdots \cdots \ddots \ddots g_{s,1}’ g_{s,2}’f_{2,1} \cdots f_{2,s} \cdots f_{1,1} \cdots f_{1,s} \cdots\end{array})$

(5.3)

56
lc
と乃にそれぞれ lc
を掛ける必要がある。したがって、次の関係式を得る。
上記変換においては、

DetPol$(G_{1,1})$$F_{1}$$(\tilde{M}_{S})$

$C$

$=$

DetPol$(M_{S})$,$\cdots$$(G_{1,r1})$と lc $(G_{2,1})$$\cdots$

lc

where

$(G_{2,r2})$(5.4)$C= [ \prod_{i=1}^{2}1c(G_{i,1})\cdots 1c(G_{i,r_{i}})]/[1c(G_{1}’)\cdots 1c(G_{s}’)]$

等は上で定義されたものとする。 $r_{1}+r_{2}>s$ ならば、と lc $(G_{2,j}),$ $(j=1,2, \ldots)$ , を独立なパラメータ$S=$ Spolの計算において、 lcとみなすとき、 $C$ を含まない全ての項は互いにキャンセルする。

命題 2$\tilde{F}_{1},\tilde{F}_{2},$$G_{1,j},$ $G_{2,j},$$r_{2},$$r_{1},$

$C$

$s,$

$(G_{1,j})$$(\tilde{F}_{1},\tilde{F}_{2})$

初めに、 $r_{1}+r_{2}>s$ なので、 $C$ の分母は分子を割り切ることを指摘しておく。
の係数なので、 命題は$S=DetPo1(\tilde{M}_{S})$ であり DetPol $(M_{S})$ 各要素は◇(5.4) から直ちに得られる。

証明$F_{1},$ $F_{2},$ $G_{1}’,$【場合 II】$Farrow\cdotsarrow H_{0},{}_{1}H_{0,r}0\tilde{F}$$G_{i}arrow\cdotsarrow\tilde{G}_{i}H_{i},{}_{1}H_{i,r_{i}},$$G_{s}’$$\ldots,$$(i=1, \ldots, q)$、$R=\tilde{q}\tilde{F}-\tilde{c}_{1}\tilde{U}_{1}\tilde{G}_{1}-\cdots-\tilde{c}_{q}\tilde{U}_{q}\tilde{G}_{q}$とする。 ここで、$\tilde{c}_{0},\tilde{c}_{1},$, に対し、 $\tilde{F}A$ . . .
$\ldots,\tilde{c}_{q}$は数で$\tilde{U}_{1},$$arrow^{G_{q}^{\tilde{}}}R$。

$\ldots,\tilde{U}_{q}$はべき積である。 $R$ は次の簡約行列で表される。

coeffi.cientve.ctorof$\tilde{M}_{R}=$および砧$\tilde{F}=c_{0,0}F-\sum_{j=1}^{r_{0}}c_{0,j}U_{0},{}_{j0,j}H$(5.5)$\tilde{U}_{1}\tilde{G}_{1}coefficientvectorof\tilde{F}coefficientvectorof\tilde{U}_{q}\tilde{G}_{q})$$($$=c_{i_{\}}0}G_{i}- \sum_{j=1}^{r_{i}}c_{i,j}U_{i},{}_{ji,j}H,$$(1\leq i\leq q)$, とする。

はべき積である。場合 I と同様、 $\{H_{1}’, \ldots, H_{s}’\}:=$に$1pp(H_{1}’)\succ\cdots\succ 1pp(H_{S}’)$ , とする。上記行列の係数ベクトルでの係数ベクトルをそれぞれ $F$ との係数ベクトルを付加し、 とを得る。
置き換えると、 次の簡約行列
ここで、$\mathcal{C}_{i,0},$$\ldots,$$Q_{r}t$は数で$U_{i,1},$$\ldots,$$U_{i,r_{i}}$$\tilde{M}_{R}$$\bigcup_{i=0}^{q}\{U_{i,j}H_{i,j}|j=1, \ldots, r_{i}\},$$\tilde{F}$$H_{1}’,$$H_{s}’$$\ldots,$$G_{i}$$\tilde{G}_{i}$$M_{R}$$M_{R}= (\begin{array}{lllllll}coeffi cient\ddots coeffi cient \ddots vector of \ddots \ddots \ddots coeffi cient \ddots vector of H_{S}’ \ddots \ddots of\tilde{U}_{1}G_{1} \ddots \ddots of\tilde{U}_{q}G_{q}vector F \end{array})$

場合 I と同様、 簡約行列$\tilde{M}_{R}$$DetPo1(\tilde{M}_{R})$(5.6)と $M_{R}$ の問には次の関係式が成立する。

$=$$CDetPo1(M_{R})$ ,where$C = [ \prod^{q}1c(H_{i,1})\cdots 1c(H_{i,r})]/[1c(H_{1}’)\cdots 1c(H_{s}’)]$

(5.7)

57
命題 3 $F,$$G_{1},$$\ldots,$$G_{q},$ $r_{0},$ $r_{1},$$\ldots,$$r_{q},$$C$

等は上で定義されたものとする。 $r_{0}+r_{1}+\cdots+r_{q}>s$

...
ならば、
の計算において、 lc $(H_{i,j}),$ $(i=0,1, \ldots, q;j=1, \ldots, r_{i})$ , を独立なパラメータとみなすとき、 $C$ を含まない全ての項は互いにキャンセルする。
$\tilde{F}arrow^{G_{1}^{\tilde{}}}$

証明$arrow^{G_{q}^{\overline{}}}R$$r_{0}+r_{1}+\cdots+r_{q}>s$$R=$ DetPol$(\tilde{M}_{R})$なので、 $C$ の分母は分子を割り切ることを指摘しておく。

であり DetPol $(M_{R})$ の各要素は$F_{1},$ $F_{2},$ $H_{1}’,$$\ldots,$$H_{s}’$の係数なので、 命題

は (5.7) から直ちに得られる。

◇

第 3 章において、 項キャンセルに対する命題 1 から桁落ちを規定する系 1 が得られた。
同様に、 命題 2 と 3 から 【場合 I】 と【場合 II】 における桁落ちを規定する系が得られる
が、紙面の制約のため記述を割愛する。

参考文献[1] B. Buchberger. Gr\"obner Bases: An algorithmic method in polynomial ideal theory. Multidimensional
Systems Theory, N.K. Bose (Ed.), Chap. 6, Reidel Publ., 1985.

[2] J.E. Collins. Subresultant and reduced polynomial remainder sequence.
[3] D. Cox, J. Little and D.

$O$

$J.$

$ACM,$ $14,128-142$ ,1967.

’Shea. Ideals, Varieties, and Algonthms. Springer Verlag New York, 1997.

[4] D. Lazard. Gr\"obner bases, Gaussian elimination and resolution of systems of algebraic equations.
Proceedings of EUROCAL 1983; $Sp_{7}nnger-$ レセ rlag LNCS 162, 146-156, 1983.
[5] R. Loos. Generalized polynomial remainder sequences. Computer Algebra, Symbolic and Algebmic
Computation, B. Buchberger, G.E. Collins and R. Loos (Eds.), Springer-Verlag, 1983.

[6] A.M. Mandache. The Gr\"obner basis algorithm and subresultant theory. Proceedings of ISSA C’94
(Intn’l Symposium on Symbolic and Algebraic Computation), 123-128, ACM Press, 1994.
[7] K. Nagasaka. A Study on Gr\"obner basis with inexact input. Proceedings of CASC2009 (Computer
Algebra in Scientific Computing): Springer LNCS 5743, 248-258, 2009.

[8] T. Sasaki and A. Furukawa. Secondary polynomial remainder sequence and an extension of subresultant theory. J. Inf. Proces., 7, 175-184, 1984.
[9] T. Sasaki and A. Furukawa. Theory of multiple polynomial remainder sequence. Publ. RIMS (Research Inst. for Mathemat. Sci., 20, 367-399, 1984.
[10] T. Sasaki and F. Kako. Computing floating-point Grobner base stably. Proceedings of SNC2007(Symbolic Numeric Computation), 180-189, London, Canada, 2007.

[11] T. Sasaki and F. Kako. Floating-point Gr\"obner basis computation with ill-conditionedness estimation. Proceedings of ASCM2007 (Asian Symposium on Computer Mathematics): Springer LNAI
5081, 278-292, Deepak Kapur (Ed.), 2008.
[12] T. Sasaki and F. Kako. Term cancellations in computing floating-point Gr\"obner bases. Proceedingsof CASC2010 (Computer Algebra in Scientific Computing): Springer LNCS 6244, to appear.