数理解析研究所講究録
1199 巻 2001 年 43-50$\mathrm{R}\mathrm{i}s\mathrm{a}/\mathrm{A}s\mathrm{i}\mathrm{r}$43における Weyl Algebra 上のグレブナ基底計算およびその応用
神戸大学

1

正行 (Masayuki NORO) *野呂

Weyl Algebra
さまざまな計算機代数システム上で Weyl Algebra に関する演算が実装されている. 代表

的なものとして,$\mathrm{K}\mathrm{a}\mathrm{n}/\mathrm{S}\mathrm{m}\mathrm{l}[9]$どがある. 以下では$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{S}\mathrm{i}\mathrm{r}$, Macaulay2 $[1][3]$ , Maple Ore algebra package, Singular [2] なにおける Weyl Algebra 関連機能の実装について述べるが, ここで述べられている改良その他は, 文献として参照することはできないものの, 上記システムそれぞれにおいて採り入れられていると考えられる.

1.1 Leibnitz rule
体 $K$ 上の$n$

次元 Weyl Algebra$D_{n}=K\langle x_{1}, \cdots, x_{n}, \partial_{1}, \cdots, \partial_{n}\rangle$

における積の計算は, よく知られているように Leibnitz rule で計算できる. すなわち, $2n$ 変数多項式環 $K[x, \xi]=K[x_{1}, \cdots, x_{n}, \xi_{1}, \cdots, \xi_{n}]$ から$x^{\alpha}\partial^{\beta}$$D_{n}$

への $K$ 線形写像$\Psi$を$\Psi(x^{\alpha}\xi^{\beta})=$で定義するとき,$\Psi(f)\Psi(g)=\Psi(1kn\sum_{k,\ldots,\geq 0}\frac{1}{k_{1}!\cdots k_{n}!}\frac{\partial^{k}f}{\partial\xi^{k}}\frac{\partial^{k}g}{\partial x^{k}})$$(f, g\in K[X, \xi])$となる. Weyl Algebra における計算の効率化のためには積の効率化が重要であり, そのためには Leibnitz rule をどう使うかが鍵となる. 特に, グレブナ基底計算を考える場合, monomial*noro@math kobe-u .

$\mathrm{a}\mathrm{c}$$\cross \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{a}\mathrm{l}$.jpの高速化が必要である.

44
1.2 Asir における実装
Asir における初期の実装では, これを$m$:monomial, $f= \sum f_{j}$ ($f_{j}$: monomial) に対し $mf= \sum mf_{j}$として計算していた. ここで monomial どうしの積は$x^{k}D^{l}\cdot x^{a_{D^{b}}}=(x_{1}^{k_{1}}(D_{1}x\iota_{1}a_{1}1)D_{1}^{b_{1}})\cdots(x_{n}^{k_{n}}(D_{n^{n}}^{\iota}x_{n})a_{n}D_{n^{n}}^{b})$として, 右辺の$D_{i}^{k_{i}}X_{i}^{a_{i}}$を Leibnitz rule により$D_{i}^{l_{i}}X_{i}^{a}i= \sum_{j=0}^{i}j!XiiMin(\iota_{i},a)Da_{i}-jli-j$とし, これらの積を, 通常の可換な多項式として展開する, という方法を採っていた. しかし,この monomial の積自体が多項式となるため, これらを足し合わせる際にに項の比較およびリストのつなぎ換えが多数生じ, 特に $f$ の項数が多い場合に効率が悪いことが分かった.

1.3 改良Leibnitz rule に現れる微分を $f\in K[x, \xi]$ に作用させても monomial の順序は変わらないことに注意すれば, 左からかける monomial $m$ を固定したとき, 前項の monomial どうしの積において

1.

$D_{i}^{\iota_{i}}xia_{i}$を変形して得られる和を常に$\sum_{j=0}^{l_{i}}$とする孟$>{\rm Min}(\iota_{i}, a_{i})$の場合, 係数は$0$としておく.

2. 適当な順序を定めて, 積を構成する monomial を整列し, 対応する位置の monomial どうしの和をまず作る. これは既に整列されているみと同順でよい.

3. 最後にそれらを足し合わせる.
要するに, Leibnitz rule において, 微分に関する和を先に計算するということだが, これで $m$の$\partial$に関する次数がよほど高くない限り効率化する. (これは,$\mathrm{K}\mathrm{a}\mathrm{n}/_{\mathrm{S}\mathrm{m}}$]

で既に行われていた. ) さらに, 次の改良が考えられる.
$\bullet$$(x_{1}^{k_{1}}(D_{1}x\iota_{1}a_{1}1)D_{1}^{b_{1}})\cdots(x_{n}^{k_{n}}(D_{n^{n}}^{la}x_{n^{n}})D_{n}^{b}n)$これは$\frac{1}{k_{1}!\cdots k_{n}!}$の計算を incremental に行う.に現れる共通の部分積を重複して計算しないということであり, 次数が高い場合に有効かもしれない.
$\bullet$$l_{i},$$a_{i}$

が$0$の場合の shortcut.

一般に次数が$0$になる部分が多いでこれは重要である.

45
exponent vector, monomial などを表す構造体のメモリ管理を自前で行う.

$\bullet$

これは, Weyl に限らず, 有限体上の場合には–般に用いている. これも効率に大きく影響する.
以上の改良を加えることで, 初期実装に比較して十分効率化することができた.

1.4 Weyl Algebra における Buchberger アルゴリズム
多項式環上の Buchberger アルゴリズム実装においては, 種々の criteria および selectionstrategy が考案され実用化されているが, Weyl Algebra においても Buchberger’s criterion (Spolynomial を構成する多項式の頭項の GCD が 1 の場合にはその -polynomial は に正規$0$$\mathrm{S}$化される) 以外はそのまま使える. よって, あとは積を前節のものに換えれば, 多項式環用のドライバ, サブルーチンが使え, 容易に Weyl Algebra 上の Buchberger アルゴリズムの実装が得られる.

2 b-function の計算
2.1 b-function’$D=D_{n}=K\langle x_{1}, \cdots, x_{n}, \partial_{1}, \cdots, \partial_{n}\rangle(\partial_{i}=\partial/\partial x_{i}),$$f\in K[x_{1}, \cdots, x_{n}]$とするとき

なる $P(s)\in D[s]$ が存在するような最小次数の $b_{f}(s)\in K[s]$ を $f$ の$P(s)fs+1=b_{f}(s)f^{s}$(global) -function と呼ぶ 1). 大阿久 [5] により b-function は以下のように計算できる. まず,$b$$n+1$ 次元の Weyl Algebra $D_{n+1}=K\langle t, x_{1}, \cdots, x_{n}, \partial_{t}, \partial_{1}, \cdots, \partial_{n}\rangle$ を考える.

定義 1 $D_{n+1}$ の元$P= \sum c_{\mu\nu}\alpha\beta t^{\mu}x\partial^{\nu}\alpha\partial^{\beta}t$$\mathrm{o}\mathrm{r}\mathrm{d}_{F(P)}:=\max$

{

に対し,

$I^{\ovalbox{\tt\small REJECT}}-\mu|$ある$\alpha,$$\beta$に対し$c_{\mu\nu\alpha\beta}\neq 0$$\hat{\sigma}(P):=\sum_{P\nu-\mu=\mathrm{o}\mathrm{r}\mathrm{d}F()}c\nu\alpha\iota\mu\beta t\mu_{X}\alpha_{\partial\partial}\nu\beta$

定義 2$\mathrm{o}\mathrm{r}\mathrm{d}_{F(P)=m}$

なる $P\in D_{n+1}$ に対し, $\psi(P)\in D[s]$ を$\hat{\sigma}(t^{m}P)$$(m\geq 0)$$\psi(P)(t\partial t)=\{$$\hat{\sigma}(\partial_{t}^{-}$$m_{P)}$$(m<0)$で定義する.

1)

本来は$\overline{b}(s)$と書くべきだが, 本稿では $b(s)$ と書くことにする.

}

46
定理 3
$I=Id(t-y1f, \partial 1+y1(\partial f/\partial x_{1})\partial_{t},$に対し,$G_{1}$$\cdots,$$\partial_{n}+y_{1}(\partial f/\partial x_{n})\partial_{t})$を $I_{1}=I\cap D$ のグレブナ基底とする. この時,$Id(\psi(G_{1}))\cap K[s]=Id(b(-s-1))$

大阿久 [5] では$(Id(\psi(G_{1}))\cap K[x, s])\cap K[s]$なる二段階の elimination による計算を提案している. これは, local な -function の計算に$\mathrm{b}$$(Id(\psi(G1))\cap K[x, s])$が必要となるためと考えられるが, global -function のみを求める場$\mathrm{b}$合には, 直接 $K[s]$ との交わりを求めて構わない. よって, 任意の順序に関する $Id(\psi(G_{1}))$ のグレブナ基底が求まっていれば, $b(s)$ は可換多項式環の場合と同様に, 未定係数法より求めることができる.

2.2$D$$\mathbb{Q}$を上の Weyl Algebra における最小多項式の modular 計算$\mathbb{Q}$

上の Weyl Algebra, $J$ を $D$ の ideal, $P\in D$ かつ $P$ は整数係数とし, $J\cap \mathbb{Q}[P]\neq\{0\}$とする. この時, $J\cap \mathbb{Q}[P]=Id(b(P))$ とすれば $b(s)$ は $D/J$ における $P$ の項式となる. ここで, $b(s)\in \mathbb{Z}[s]$ かっ$J$$\mathbb{Z}$$\mathbb{Q}$上の最小多上原始的と取れる.の, 順序 $<$ に関するグレブナ基底で, 各元の頭係数が 1 であるものを $G$ とし, $G$ の各元の係数が$\mathbb{Z}_{(p)}=\{a/b|a\in \mathbb{Z}, b\not\in p\mathbb{Z}\}$に属するような$P$を選ぶ.

$\phi_{P}$を$\mathbb{Z}_{(p)}$から $GF(p)$ への標準的射影 (およびその $D$ への拡張) とする.
補題 4 $\phi_{p}(G)$ は $Id(\phi_{p}(G))$ の $<$ に関するグレブナ基底で, $\phi_{p}(b(P))\in Id(\phi_{p}(G))$ .
証明 $G$ から作られるて, その$\phi_{P}$$\mathrm{S}$-polynomial の$G$

によるへの reduction が $Z_{(p)}$ 上で行える.

よっによる像がそのまま $\phi_{p}(G)$ による reduction になるから, $\phi_{p}(G)$ は $Id(\phi_{p}(G))$のグレブナ基底となる. 後半も同様である.
仮定により$b_{p}(s)$$0$$\phi_{p}(b(s))$

は$0$でないから, $\phi_{p}(P)$Iの $\phi_{p}(D)/Id(\phi_{p}(G))$ における最小多項式が存在して $b_{p}(s)|\phi_{p}(b(s))$ が成り立つ. 特に $\deg(b_{p}(s))\leq\deg(b(s))$ .

定理 5 $b_{p}(s)$ を $\phi_{p}(D)/Id(\phi_{p}(G))$ における$\deg(b_{p}(S)),$$\phi_{p}(P)$の最小多項式とするとき, $\deg(f(s))=$$f(P)\in Id(G)$ なる $f\in \mathbb{Z}[s]$ が存在すれば, $f(s)=b(s)$ .

証明仮定より $b(s)|f(s)$ .-方で $\deg(f(s))=\deg(b_{p}(s))\leq\deg(b(s))$ だから $b(s)=f(S)$ .

I47
アルゴリズム 6

Input: 項順序$<,$$<$

に関するグレブナ基底 $G\subset D$ 傾係数が 1),$Id(G)\cap \mathbb{Q}[P]\neq\{0\}$なる $P\in D$ (整数係数)

Output: $Id(G)\mathrm{n}\mathbb{Q}[P1=Id(b(P))$ なるdo$b(s)\in \mathbb{Q}[s]$$\{$$parrow G\in \mathbb{Z}_{(p)}$$b_{p}arrow\phi_{p}(P)$なる未使用の素数の $\phi_{p}(D)/Id(\phi_{p}(G))$

における最小多項式$darrow deg(b_{p})$$c arrow NF(P^{d}, G)+\sum_{i=0^{C_{i}}}^{d-1}NF(\mathrm{p}i, G)$$Carrow${$C_{t}(c0,$ $\cdots,$ $c_{d-1})=0|C_{t}$if が\hslash 垣 c0
$C$returnは$c$(ci は未定係蜘の各 monomial の係数}$=a_{0},$ $\cdots,$ $c_{d-1}=a_{d-1}$} を持つ$\{$$s^{d}+ \sum_{i=0}^{d-}1a_{i}S^{i}$$\}$

$\}$

法

$P$

での最小多項式は, $NF(\phi_{p}(P^{k}), Id(\phi_{p}(G)))$ を順に計算して線形関係を探すことで得られる. $b(s)\in \mathbb{Z}[s]$ とした時の主係数を割らない$P$に対しては定理 5 の D は存在するから,アルゴリズム 6 は停止する. また, $C$ が解を持つなら, 法決まる. $C$ の求解は, 法$P$$P$での–意性よりそれは–意的にでの–意性を利用して, Hensel 構成により効率よく求めることができる. 詳細は [4] を参照.

2.3

ホロノミックな ideal に対する b-function

ideal$I\subset D_{n},w\in \mathbb{R}^{n}\backslash \{0\}$に対し, weight $(-w, w)$ に関する initial ideal $in_{(-w,w)}(I)$ が,Weyl Algebra におけるグレブナ基底計算により求まる ([8] Theorem 1.16).

variety の次元が$n$であるとき$I$$I$の characteristicはホロノミックと呼ばれるが, このとき [8] Theorem 5.12

により$in_{(-w,w)}(I)\cap K[s]=Id(b(s))$$(s=w_{1}\theta_{1}+\cdots+wn\theta n’\theta i=Xi\partial i)$なる$0$でない多項式 $b(s)$ が存在する. この $b(s)$ を,$I$の(global) -function と呼ぶ. 特に, 多項式 $f$ に対し,$b$$I_{f}=Id(t^{-} - f, \partial_{1}+(\partial f/\partial x_{1})\partial_{t},$とおく時,$I_{f}$はホロノミックで,$t$$\cdots,$$\partial_{n}+(\partial f/\partial x_{n})\partial_{t})$を先頭の変数とする時 If の $w=(1,0, \cdots, 0)$ に関する

global b-function を $B(s)$ とすれば, $b_{f}(s)=B(-S-1)$ が成り立つ. よって, $D/in_{()(I_{f})}-w,w$

48における$t\partial_{t}$の最小多項式から $b_{f}(s)$ を求めることもできる. ここで, $in_{()(I_{f})}-w,w$ の計算には non-term order によるグレブナ基底計算が必要となるが, [8] で述べられている斉次化によりある term order のもとでのグレブナ基底計算に帰着できる.

2.4

タイミングデータ

Section 2 で紹介した, 二段階の消去による方法 (方法 1) と, $Id(\psi(G1))\mathrm{n}K[s]$ を Section
22 で述べたように最小多項式として求める方法 (方法 2), および Section 23 で述べた方法(方法 3) による計算時間をさまざまな多項式に対して比較する. いずれも, -function の計$b$

算は modular 計算で最小多項式求める方法により行った. 例題は [5], [10] から採った. 表2 の $x^{a}+xy^{b-1}+y^{b}$ に関しては, 本講究録中の大阿久, 高山両氏による稿を参照. 計算は,PentiumIII lGHz 上で行った. 単位は秒でガーベッジコレクション時間は除いてある. “-,, は,他の方法と比較して時間がかかり過ぎるため中断したことを意味する. 表 1 では計算が比較的容易なものが扱われており, 各方法で大差はないが, 表 2 では, 方法 1 では計算が困難なものが, 方法 2, 3 により計算できている. また, 次数が上がるにつれ, 方法 3 が優位となる. これは, 方法 2 に現れるグレブナ基底計算が, 方法 3. における $in_{(-}w,w$ ) $(I_{f})$ の計算に比べて困難となるためである. これは表 3 においてさらに顕著となり, 方法 2 では計算できない例も出て来る. 実際には, 方法 3 では, 最小多項式の計算が dominant となる例もしばしば見られる.

表 3: [5] からの例題

3

おわりに$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{S}\mathrm{i}\Gamma$

における, Weyl Algebra 関連機能の実装および, その応用として b-function の計算方法の改良について述べた. -function 計算は$b$$\mathrm{K}\mathrm{a}\mathrm{n}/\mathrm{S}\mathrm{m}\mathrm{l}$, Macaulay 2 にも実装されいてるが, 本稿で述べたような, 最小多項式を未定係数法で求める方法を用いた例はないようであ49

表 4: [10] からの例題表 5: [10] からの例題 (non-isolated singularities)
る. –方で b-function は $f$ の局所モノドロミーと関係することが知られているが, Singularにおいては, 全く異なる立場から isolated singularity でのモノドロミー行列を求める機能を提供している. これについて, 効率の面からの比較も必要と考えられるが, 得られる結果が異なることもありまだ詳細な比較は行っていない.

本稿で述べた方法により, より広い範囲の多項式およびイデアルに対して -function が計算できるようになったととは確かである. しかし, 既に他の方法で結果が知られているもの$b$でも計算不可能な問題は存在し, またいわゆる多重 -function に対しては, 最小多項式によ$b$る方法は無力である. これらに対処するためにはさらなる改良, あるいは新しい方法が必要であろう.

参考文献[1]Grayson, D., Stillman, M.: Macaulay 2, a software system for research in algebraic geometry. http:$//\mathrm{w}\mathrm{w}\mathrm{w}$. math. ucuc.

$\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{a}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{y}2$.

[2] Greuel, G.-M., Pfister, G., Sch\"onemann, H.: SINGULAR, A Computer Algebra System for

Polynomial Computations. http:$//\mathrm{w}\mathrm{w}\mathrm{w}$. ingular. uni-kl.
$\mathrm{S}$$\mathrm{d}\mathrm{e}/$.

50[3] Leykin,

http:A.,$//\mathrm{w}\mathrm{w}\mathrm{w}$H.:

Tsai,D-module. math. cornell.

$\mathrm{e}\mathrm{d}\mathrm{u}/\sim \mathrm{t}\mathrm{s}\mathrm{a}\mathrm{i}$packageforMacaulay

2.

.

[4] Noro, M., Yokoyama, K.: A Modular Method to Compute the Rational Univariate Repre-sentation of Zero-Dimensional Ideals. J. Symb. Comp., 28,1 (1999) 243-263.
[5] Oaku, T.: Algorithm for the$b$-function and $D$ -modules associated to a polynomial. J. Pure

Appl. Algebra, $117$ & $118$ (1997) 495-518.
[6] Oaku, T., Takayama, N.: An algorithm for de Rham cohomology groups of the complementof an affine variety via $D$ -module computation. J. Pure Appl. Algebra, 139 (1999), 201-233.
[7] Oaku, T., Takayama, N.: Algorithms for D-modules–restriction, tensor product, localiza-tion, and local cohomology groups. J. Pure Appl. Algebra (in press).
[8] Saito, M., Sturmfels, B., Takayama, N.: Gr\"obner Deformations of Hypergeometric Differ-ential Equations. Algorithms and Computation in Mathematics 6, Springer (2000).
[9] Takayama,

http:N.:$//\mathrm{w}\mathrm{w}\mathrm{w}$Kan

A system for doing algebraic analysis by computer.
.math. kobe-u.
.
.)–$\mathrm{a}\mathrm{c}$$\mathrm{p}/\mathrm{K}R\mathrm{N}$[10] Yano, T.: On the theory of -functions. Publ. RIMS Kyoto Univ. 14 (1978), 111-202.
$b$