数理解析研究所講究録
第 1666 巻 2009 年 106-116

106

局所

関数に付随する$b$

stratification アルゴリズムの実装および応用
西山絢太

野呂正行

KENTA NISHIYAMAMASAYUKI NORO

神戸大学大学院理学研究科*

神戸大学大学院理学研究科\dagger

Abstract$n$変数多項式 $f\in \mathbb{C}[x]$ の localb 関数 $b_{f,p}(s)$ は各 stratum で一定であるという性質でを stratify する . Oaku [12] は準素イデアル分解を用いて, このような stratification と各
stratum の上の $b_{f,p}(s)$ を計算するアルゴリズムを提案した. 我々は準素イデアル分解を用い$\mathbb{C}^{n}$ない新たなアルゴリズムを提案し, その実装および応用について詳しく述べる.

1

はじめに$\mathcal{D}$の $b$を $n$ 変数 $x=$ $(x_{1}, \ldots , x_{n})$ の微分作用素環とするとき, 多項式 $f(x)\in \mathbb{C}[x]=\mathbb{C}[x_{1}, . . . , x_{n}]$関数は,$L(x, \partial_{x}, s)f^{s+1}=b(s)f^{s}$を満たす微分作用素定義される. ここで,く. また,$\mathcal{D}$

変数多項式 $b(s)$ のペアに対し, $b(s)$ の次数が最小のものとしてが Weyl algebraの場合は global関数と呼び $b_{f}(s)$ と書$L\in \mathcal{D}[s],$$1$$D=\mathbb{C}\langle x,$$\mathcal{D}$$b$$\partial_{x}\rangle$が,$\mathbb{C}[x]_{p}=\{f(x)/g(x)|f(x),g(x)\in \mathbb{C}[x],g(p)\neq 0\}$(における localb 関数と呼び,における局所化) を係数とする微分作用素環 [x]p のの場合,$b_{f,p}(s)$と書く. 定義から直ち , 任意のに対し $b_{f,p}(s)|b_{f}(s)$ であり, $b_{f}(s)=$ LCM $(b_{j,p}(s);p\in$$\mathbb{C}$$p$$\langle\partial$$_{}$$\mathbb{C}^{n})$

2

$P$

$P$

が成り立っことが分かる.

$b$関数の計算アルゴリズム

この章では, 既に知られている 関数の計算アルゴリズムについて簡単に述べる.
global 関数の計算は $D[s]$ 上で Ann $D[s]^{f^{s}}:=\{P\in D[s]|Pf^{s}=0\}$ を計算し, Ann $D[s]^{f^{s}}+$$D[s]f)\cap \mathbb{C}[s]$ の生成元として $b_{f}(s)$ を計算する方法 [13] と, 新たな変数を追加した $n+1$ 変数の
$b$

$b$

$($

$t$

の $(t,$
上で $I_{f}:=\langle t-f,$Weyl algebra $D\{t,$に対する weight $(-w, w)$ $:=(-1,0, \ldots, 0|1,0, \ldots, 0)$ に関する先頭項イデアル in $(-w,w)$ (If) を計の生成元として $b_{j}(-t\partial_{t}-1)$ を計算する方法 [16] の 2 つの方法がある.
算し,これらの方法は次の定理による密接な関係がある.
$\partial_{t}\}$$in_{(-w,w)}(I_{j})\cap \mathbb{C}[t\partial_{t}]$’nisiyama@math.kobe-u.ac.jp’noro@math.kobe-u.ac.jp$\partial q+\neq_{x_{1}}^{\partial}\partial_{t},$$\ldots\partial_{n}+\neq_{x_{n}}^{\partial}\partial_{t}\rangle$$x_{1},$$\ldots,$$x_{n}|\partial_{t},$$\partial_{n})$$\partial_{1},$$\ldots,$107
定理 1([15] 定理 534)
$D[s]$

におけるの零化イデアル Ann $D[s]f^{s}$ は$f^{s}$$I_{f}\cap D[t\partial_{t}]$において $t\partial_{t}\mapsto-s-1$ と変換したものに等しい.

与えられた 1 点における localb 関数を計算するアルゴリズムは Oaku[11] による方法と Nakayama[7] による Mora division を用いる方法, 近似割り算を用いる方法の合わせて 3 種類が知られているが, ここでは深く言及しない. 一方, localを関数の関数として与える方法は
Oaku[12] により与えられた. それは次のようなアルゴリズムである.
$b$$b_{f_{;}p}(s)$$p\in \mathbb{C}$

アルゴリズム 1$L_{f}arrow(Ann_{D[s]}f^{s}+D[s]f)\cap \mathbb{C}[x, s]$$L_{f}$の準素イデアル分解 $L_{f}=Q_{1}\cap\cdots\cap Q_{r}$ を計算$V_{i}arrow V(Q_{i}\cap \mathbb{C}[x])(i=1, \ldots, r)$$b_{i}(s)arrow Q_{i}\cap \mathbb{C}[s](i=1, \ldots, r)$$Sarrow\emptyset$

for each$Z\subset\{1, \ldots, 7^{\cdot}\}$do$V_{Z} arrow\bigcap_{i\in Z}V_{i}\backslash \bigcup_{i\not\in Z}V_{i}$if$V_{Z}\neq\emptyset$

then$b_{Z}(s)arrow$

LCM $(b_{i}(s);i\in Z)$$Sarrow S\cup\{(V_{Z},$ $b_{Z}(s))\}$

end ifend for
retum$S$

このアルゴリズムは $(V_{Z}, b_{Z}(s))$ というペアの集合を返し, 点 $p\in V_{Z}$ に対して $b_{f_{\}}p}(s)=b_{Z}(s)$であることを意味する. また, 各はボトルネックになり得る点がある.
$V_{Z}$$\bullet$$L_{f}$$\mathbb{C}^{n}$の構成可能集合になっている. この方法には次のようなの計算を計算し, その消去イデアルとしてを計算しているが, 定理 1 により
in $(-w,w)(I_{f})$ の計算をしてから消去イデアルの計算をしてもよい. 実際に Ann $D[s]^{f^{s}+D[s|f}$の計算より in $(-w,w)(I_{f})$ の計算の方が速く計算できることが多かったことから後者を採用した方が効率面で有利であると思われる.
$Ann_{D[s]}f^{s}+D[s]f$$\bullet$$L_{f}$

準素イデアル分解
最終的に点$p\in \mathbb{C}$における local

$b$

関数

$b_{f_{)}p}(s)$を定めるためには $p$ が $V(Q_{i}\cap \mathbb{C}[x])$ に属するかどうかを調べる必要がある. これには零点の情報があれば十分であるが, 準素分解は零点の情報より多くの情報を持っている. 実際に, 準素分解による方法は, 同一の local 関$b$数を与える成分を更に分解した結果を出力する場合がある. また, 準素分解はアルゴリズム,
実装ともに複雑であり, 入力によっては計算が困難になる場合もある.

3

新しい計算アルゴリズム
以下では $J_{j}=$ in $(-w,w)$ (If) とする.

108
定理 2
$p\in \mathbb{C}^{n}$と$b(s)\in \mathbb{C}[s]$に対して以下は同値.

1. $Lf^{s+1}=b(s)f^{s}$ を満たすような L

2.

$a(x)\in(J_{f}\cap \mathbb{C}[x, t\partial_{t}])$証明$\in \mathbb{C}$[x]p のが存在する.
$\langle\partial$: $b(-t\partial_{t}-1)),$ $a(p)\neq 0$ を満たす $a(x)\in \mathbb{C}[x]$ が存在する.

$L(s, x, \partial_{x})\in \mathbb{C}[x]_{p}\langle\partial_{x}\}$から $L=1/a(x)\cdot\tilde{L}$ を満たす $\tilde{L}(s, x, \partial_{x})\in D$ と$a(x)\in \mathbb{C}[x]$が存在して,$(a(p)\neq 0)$$1/a(x)\cdot\tilde{L}(s, x, \partial_{x})f^{s+1}=b(s)f^{s}$$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$$\tilde{L}(s, x, \partial_{x})f^{s+1}=a(x)b(s)f^{s}$$\tilde{L}(s, x, \partial_{x})f-a(x)b(s)\in$Ann$D[s]^{f^{s}}$$\tilde{L}(-t\partial_{t}-1, x, \partial_{x})t-a(x)b(-t\partial_{t}-1)\in I_{f}$$a(x)b(-t\partial_{t}-1)\in$

in $(-w,w)(I_{f})$$a(x)\in$ in $(-w,w)(I_{f}):b(-t\partial_{t}-1)$

3 行目の同値は定理 1 と $t\equiv fmod$ If から, 4 行目の同値は $(-w, w)$ が重みが付いた weight であることからそれぞれ従う.
この定理と local 関数の定義から次の系が従う.

$t,$$\partial_{t}$.

にのみ $-1,1$ という

I

$b$

系3
次の 2 つは同値.

1.

$c(s)\in \mathbb{C}[s]$が $b_{f,p}(s)|c(s)$ を満たす.

2. $a(p)\neq 0,$ $a(x)\in(J_{f}\cap \mathbb{C}[x, ta])$ : $c(-t\partial_{t}-1))$ を満たす $a(x)\in \mathbb{C}[x]$ が存在する.

globalb 関数は柏原の定理により
こで$b_{f}(s)$$\mathbb{Q}$

上で 1 次式の積に因数分解されることが知られている. そが $b_{f}(s)= \prod_{i=1}^{r}g_{i}(s)^{d_{i}}$ と分解されているとしよう.

$b_{f_{)}p}(s)|b_{f}(s)$なので $b_{f,p}(s)= \prod_{i=1}^{r}g\iota(s)^{e_{i}(p)}$$(0\leq e_{i}(p)\leq d_{i})$このとき, local$b$

関数 $b_{f_{)}p}(s)\}$は

と書ける.

定義 4
$i=1,$$\ldots,$

多様体

$r,$

$V_{i,j}$$j=0,$$d_{i}$$\ldots,$に対して $b_{i,j}(s):=b_{f}(s)/g_{i}(s)^{d_{i}-j}$ と定義する. 更$_{arrow}$, イデアルを$I_{i,j}:=$$((J_{f}\cap \mathbb{C}[x, t\partial_{t}]):b_{i,j}(-t\partial_{t}-1))\cap \mathbb{C}[x],$で定義する.

定理 51.

$\mathbb{C}[x]=I_{i,d_{\mathfrak{i}}}\supset I_{i,d_{i}-1}\supset\cdots\supset I_{i,0}\supset I_{i,-1}=\{0\}$2.

$\emptyset=V_{i,d_{i}}\subset V_{i,d_{i}-1}\subset\cdots\subset V_{i,0}\subset V_{i,-1}=\mathbb{C}^{n}$3.

$p\in V_{i,j-1}\backslash V_{i,j}\Leftrightarrow e_{i}(p)=j$.

$I_{i,-1}:=\{0\},$$V_{i,j}:=V(I_{i,j})\subset \mathbb{C}^{n}$$I_{i,j}$

と,

109

(3) のみ示す. $p\in V_{i,j-i}$ とすると, $\tilde{L}f^{s+1}=a(x)b_{i,j-1}(s)f^{s}$ を満たす $\tilde{L}\in D[s],$ $a(x)\in$が存在すれば $a(p)=0$ となる. 系 3 より $b_{f,p}1^{b_{i,j-1}}\cdot P\not\in V_{i,j}$ とすると, $a(x)\in \mathbb{C}[x]$$(a(p)\neq 0)$ が存在して $a(x)\in I_{i,j}$ . よって, 系 3 より $b_{f,p}|b_{i,j}$ . 故に $e_{i}(p)=j$ . 逆に $e_{i}(p)=j$ とすよりある $a(x)\in \mathbb{C}[x],$ $a(p)\neq 0$ が存在して $a(x)\in I_{i,j}$ . よって
.
ると,
証明

$\mathbb{C}[x]$$p\not\in V_{i,j}$$b_{f,p}|b_{i,j}$より$b_{f,p} \int b_{i,j-1}$

ならば $a(p)=0$ すなわち $p\in V_{i,j-1}$ .

$a(x)\in I_{i,j-1}$1

系6$i=(j_{1,\ldots,\dot{j}r})(0\leq j_{i}\leq d_{i})$に対して, $V^{j}=( \bigcap_{i=1}^{r}V_{i,j_{i}-1}),$$p \in V^{j}\backslash V_{j}\Leftrightarrow b_{f,p}(s)=\prod_{i=1}^{r}g_{i}(s)^{j_{i}}$$V_{j}=( \bigcup_{i=1}^{r}V_{i,j_{i}})$

とおく.

このとき,

.

以上の議論から次のアルゴリズムが得られたことになる.
アルゴリズム 2 (local 関数に付随する stratification)
Input : 多項式
Output :local 関数に付随する stratification $\{(C_{j},$ $b_{j}(s))\}$$b$$f\in \mathbb{C}[x]$$b$$J_{f}arrow$in $(-w,w)(I_{j})$ ;$L_{f}arrow J_{f}\cap \mathbb{C}[x, t\partial_{t}]$の$b_{f}(s)= \prod_{i=1}^{r}g_{i}(s)^{d_{i}}arrow f$

for $i=1,$
for $j=0,$$\ldots,$$r$

global$b$関数

do$d_{i}$$\ldots,$do$b_{i,j}(s)arrow b_{f}(s)/g_{i}(s)^{d_{i}-j}$;$I_{i,j}arrow(L_{f)}:b_{ij}(-t\partial_{t}-1))\cap \mathbb{C}[x]$end forend for$Sarrow\emptyset$

for all $j=(j_{1}, \ldots,j_{r})(0\leq j_{i}\leq d_{i})$ do$V^{j} arrow\bigcap_{i=1}^{r}V(I_{i,j_{i}-1})$

if$V^{j}\backslash V_{j}\neq\emptyset$;$V_{j} arrow\bigcup_{i=1}^{r}V(I_{i,j_{i}})$

.

then

$b_{j}(s) arrow\prod_{i=1}^{r}g_{i}(s)^{j_{i}}$;$Sarrow S\cup\{(V^{j}\backslash V_{j},$ $b_{j}(s))\}$

end ifend for
注意 1

1点$p\in \mathbb{C}^{n}$における local$b$て $p\in V_{i_{\dagger}j-}1\backslash V_{i,j}$ となる $i$

4を全て計算する必要はなく, 各を見つけた時点で計算を止めればよい.
関数を計算したいときは$I_{i,j}$実装についてアルゴリズム 2 の各ステップの実装の詳細や改良点を述べる.

$i$

}こつい

110

4.1

$J_{f}$$J_{f}$

および $b_{f}(s)$ の計算

は $(-w, \tau v)$ が負の数を含む weight であるため homogenization を行ってグレブナー基底を計算をする必要がある. ここでは, ある特殊な homogenization を行うことにより modular changeof ordering を利用した高速化について述べる.

4.1.1

modular change of ordering$Z_{\langle p\rangle}:=\{a/b|a, b\in b\not\in p\mathbb{Z}\},$$\phi_{p}$:$Z_{\langle p\rangle}arrow F_{p}$を標数 $p$ の有限体

$F_{p}$

への標準射影とする.

アルゴリズム 3 (trace lifting によるグレブナー基底計算 [8])Input :モニックな多項式を含む $<0$ に関するグレブナ基底$G_{0}\subset \mathbb{Q}\langle x,$$\partial_{x}\rangle$

項順序 $<$

Output $:<$ に関する簡約グレブナー基底 {Go}do$parrow G0\subset Z_{(p\rangle}\{x, \partial_{x}\}$$G_{p}arrow<$

を満たす新たな素数に関する簡約グレブナー基底

If $\phi_{p}(G)=G_{p}$ を満たす $G\subset\{Go\}$ が存在 thenreturn $G$

end do上の -簡約の手
このアルゴリズムにおいて, $G$ の計算を trace algorithm [17] により行うと,間と $G$ がグレブナー基底であるかどうかの最終チェックの手間が, 有限体上のグレブナ基底計算の手間に置き換わる. これは計算途中に巨大な係数が現れる場合に非常に効果的である.
$\mathbb{Q}$

4.1.2

$0$

Weighted homogenization

Noro [9] は globalb 関数の計算に適する weighted homogenization を次のように定義していの weight
をる.
に関する全次数とし, $\delta=(t\deg_{\gamma}(f)-\gamma_{1}+$の weight
をそれぞれ $(t, x)$ ,$\ldots,t\deg_{\gamma}(f)-\gamma_{n}+1)$ とする.
,
ベクトルとし $d=t\deg_{\gamma}(f)+1$ とおく. このとき, weighted homogenized Weyl algebra$f$$t\deg_{\gamma}(f)$$\gamma=(\gamma_{1}, \ldots, \gamma_{n})\in \mathbb{R}_{>0}^{n}$$1,$$\hat{\gamma}=(t\deg_{\gamma}(f), \gamma)$$\hat{\delta}=(1, \delta)$$(\partial_{t}, \partial_{x})$$D\langle t,$で生成され,
は全て可換な基本関係を持つものとする.
を$x_{1},$$\ldots,$ $x_{n},$$\partial_{n},$$\partial_{1},$$\ldots,$$t,$$\partial_{t},$$h$$P= \sum C_{k)\alpha)l_{:}\beta}t^{k}x^{\alpha}\partial_{t}^{l}\partial_{x}^{\beta}\in D\{t,$$\partial_{t}\rangle$$\partial_{i^{X}i}-x_{i}\partial_{i}=h^{d}(i=1, \ldots, n),$$\partial_{t}t-t\partial_{t}=h^{d}$のを$H_{(\hat{\gamma},\hat{\delta})}(P)= \sum c_{k_{:}\alpha_{2}l,\beta}t^{k}x^{\alpha}\partial_{t}^{l}\partial_{x}^{\beta}h^{\deg_{(\gamma,\delta)}(P)-(k\cdot t\deg_{\gamma}(f)+l+\gamma\alpha+\delta\beta)}$で定義し, $D\{t,$$\partial_{t}\rangle$

における単項式順序$\prec$に対して $D\{t,$$uh^{k}\prec_{(\hat{\gamma},\hat{\delta})}^{h}vh^{l}\Leftrightarrow t\deg_{(\hat{\gamma},\hat{\delta})}(uh^{k})<$$(t\deg_{(\hat{\gamma},\hat{\delta})}(uh^{k})=$で定義する.

tdeg$\partial_{t},$$h\rangle$tdegにおける単項式順序$(\hat{\gamma},\hat{\delta})(vh^{l})$$(\hat{\gamma},\hat{\delta})(vh^{l})$orand $u\prec v)$$\prec_{(\hat{\gamma},\hat{\delta})}h$を$\partial_{t},$

$h\}$

以外

111

命題 7
$F= \{t-f, \partial_{1}+\frac{\partial f}{\partial x_{1}}\partial_{t}, \ldots, \partial_{n}+\frac{\partial f}{\partial x_{n}}\partial_{t}\},\hat{f}=H_{(\hat{\gamma},\hat{\delta})}(f)k$

任意の項順序レブナー基底.

$\prec 0$に対して,する. in $\prec o(F)=\{t, \partial_{1}, \ldots, \partial_{n}\}$ となる$H_{(\hat{\gamma},\hat{\delta})}(F):= \{t-\hat{f}, \partial_{1}+\tau_{x1}^{\hat{f}_{-\partial_{t},\ldots,\partial_{n}}}\partial+\frac{\partial\hat{f}}{\partial x_{n}}\partial_{t}\}$は$\{H_{(\hat{\gamma},\hat{\delta})}(F)\}$のグの計算にアルゴリズム 3 を適用
この命題により, 上の weighted homogenization を用いればを適切に選べばの計算に限らず, このすることができる. いくつかの実験によれば, weight
はヒューリスティックに選択するしかな
後の計算も効率的に行えることが分かった. 今のところ
いが, $f$ が weighted homogeneous である場合はそうなるような weight を選択すると良いようで$J_{f}$$J_{f}$$\gamma$$\gamma$

ある.

413

Jf

$b_{f}(s)$の計算[峨] の生成元の計算はグレブナー基底計算による消去法ではなく, 幕を順に上げて未定係数法を行う方法での最小多項式として計算する.
$\cap \mathbb{C}$$J_{f}$

アルゴリズム 4(最小多項式の計算アルゴリズム)

Input : イデアル $J\subset R$ のグレブナー基底 $G$ , $u\in R$のに関する最小多項式
Output :$J$$u$$iarrow 0$

do
If NF

$c(u^{i})+ \sum_{j=0}^{i-1}aj$

retum

NF $G(u^{j})=0$ となる$a_{i-1},$ $\ldots,$$a0\in K$ が存在 then$s^{i}+ \sum_{j=0}^{i-1}ajS^{j}$else$iarrow i+1$

end do4.2$J_{f}\cap \mathbb{C}[x, t\partial_{t}]$

の計算

から変数
を計算するために, 一旦グレブナー基底計算による消去法でを計算する. その後, Oaku[13] による方法を消去したイデアルとして計算する. ord $(-w,w)(h)=d$ を満たす $(-w, w)$ -homogeneous な元$L=J_{f}\cap \mathbb{C}[x, t\partial_{t}]$$\partial_{n}$$\partial_{1},$$\ldots,$

で $L$ を

$J_{f}$$\tilde{L}=J_{f}\cap \mathbb{C}[x]\{t, \partial_{t}\}$$\tilde{L}\cap \mathbb{C}[x, t\partial_{t}]$$h\in \mathbb{C}[x]\langle t,$ $\partial_{t}\}$に対して$\psi$(ん) を次で定義する.
$\psi(h)=\{\begin{array}{ll}t^{d}h d>0\partial_{t}^{-d}h d\leq 0\end{array}$

このとき, $\psi(h)$ {は $(-w, w)$ -homogeneous かつ ord $(-w,w)(\psi(h))=0$ であるので $\psi(h)\in \mathbb{C}[x,$である.

$t\partial_{t}]$

112
定理 8

の生成元とし, 各ているとする. このとき,$\{g_{1}, \ldots , g_{r}\}$を$\tilde{L}$$g_{i}$

が $(-w, w)$ -homogeneous かつ ord $(-w,w)(g_{i})=d_{i}$ を満たし$\tilde{L}\cap \mathbb{C}[t\partial_{t}]=\{\psi(g_{1}), \ldots, \psi(g_{r})\}$

43$I_{i,j}$.

の計算のイデアルとみなす事で, これ以降の計算は可換環上で行うことができる. コロンイデアル $I_{i,j}=L$ : $b_{i,j}(-s-1)$ の生成元は $L\cap\langle b_{i,j}(-s-1)\}$の生成元を $b_{i,j}(-s-1)$ で割ることによって得ることができる. 更に, $b_{i,j+}i(s)=g_{i}(s)b_{i,j}(s)$ で$L=J_{f}\cap \mathbb{C}[x, t\partial_{t}]$$\mathbb{C}[x,$を $s=t\partial_{t}$ とおいて$\mathbb{C}[x, s]$

$s]$

あったので

$L:b_{i,j+1}(-s-1)=(L:b_{i,j}(-s-1))$ : $g_{i}(-s-1)$という関係が成り立っ. 従って, $L:b_{i,0}$ から計算を始めてインクリメンタルに $L:b_{i}$ A まで計算すれば効率的であろう.

44
各$V^{j}$$i$と$V_{j}$の計算に対して次のような多様体の列霧が得られる.

:$T_{i}$$\emptyset=V_{i,d_{i}}\subset V_{i,d_{i}-1}\subset$$\subset V_{i,0}\subset V_{i,-1}=\mathbb{C}^{n}$が一致したならば, 各 localb 関数に現れる因子 $9i$ と $9k$ の指数がいつも一致することが分かるので探索の組み合わせを減らすことができる. 2 つの多様体の一致,$V(I)=V(J)$ を調べるには双方向の包含関係を見ればよい. 例えば, $V(I)\subset V(J)$ を調べたいなら
このとき, 2 つの列$J$$T_{i}$と$T_{k}$の全ての生成元が鞭の元であるかどうかを調べればよい. つまり, 根基所属判定を行えばよい.

この操作を行った後, 各列から 1 っずっ選んでイデアルの和と交わりを取って順にとを構成していく. このとき, 交わりや差集合
が空集合であるかどうかを調べて空集合でない
もののみ残していけば更に組み合わせを減らすことができる. また,
陽なので, これも根基所属判定によって分かる.
$V^{j}$$V_{j}$$V^{j}\backslash V_{j}$$V^{j}\backslash V_{j}=\emptyset\Leftrightarrow V^{j}\subset$

45$b_{f_{1}p}(s)$を与える作用素の計算

各 stratum の情報から $Lf^{s+1}=b_{f,p}(s)f^{s}$ を満たすような作用素$L\in \mathbb{C}[x]_{p}\langle\partial_{x}\}[s]$を以下のアルゴリズムで計算することができる.

アルゴリズム 5 (local

Input :

$P\in \mathbb{C}^{n}$関数を与える作用素の計算アルゴリズム)
における $f$ の local
関数 $b_{f,p}(s)= \prod_{i=1}g_{i}(s)^{e_{i}(p)}$ , イデアル$b$

Output : $L(x, \partial_{x}, s)f^{s+1}=b_{f_{\dagger}p}(s)f^{s}$ を満たす作用素$a(x)arrow a(p)\neq 0$ を満たす
$Garrow I_{f}$

の

$r$

$b$

$I_{p}= \bigcap_{i=1}I_{i,e_{t}(p)}$$L(x, \partial_{x}, s)\in \mathbb{C}[x]_{p}\{\partial_{x}\rangle[s]$に含まれる多項式$\prec(-w,w)$ に関するグレブナー基底 $\{g_{1}, \ldots, g_{k}\}$$a(x)b_{f,p}(-t \partial_{t}-1)=\sum_{i=1}^{k}$$I_{p}$ん in $(-w,w)(g_{k})$ を満たす $(-w, w)$ -homogeneous な $h_{i}\in D\{t,$$t$$\partial_{t}\rangle$

を計算.

113

$R arrow a(x)b_{f)p}(-t\partial_{t}-1)-\sum_{i=1}^{k}h_{i}g_{k}$$R$を$u_{k,t}(x, \partial_{x})(t\partial_{t})^{l}t^{k}$$\sum_{k\geq 1,l\geq 0}$という形に書き直す.

$uk,l(x, \partial_{x})(-s-1)^{l}f^{k-1}$$\hat{L}arrow$$\sum_{k\geq 1,\downarrow\geq 0}$

retun $1/a(x)\cdot\hat{L}$はアルゴリズム 2 の実行中であれば保持している情報であこのアルゴリズムにおける, $G$ やる. したがって, 1 つの作用素を計算するために生じる新たな手間は尻を計算すること, っまり$D(t,$
上の割り算を 1 回実行する程度である.
$I_{p}$$\partial_{t}\}$5

実験
アルゴリズム 2 を Risa/Asir[10] において実装した. この章ではいくつかの例について計算を行った結果を示す. 使用したのは Linux OS, Intel Xeon X5450 (3GHz) 搭載マシンである.

5.1

計算例

入力として $f(x, y, z)=x^{3}-y^{2}z^{2}$ を用いると (Oaku[12] の例) アルゴリズム 2 は次のような結果を返す.
$(\langle x^{2}, -y, -z\}, \langle 1\}, (s+1)(3s+4)(3s+5)(6s+5)^{2}(6s+7)^{2})$$(\langle zy, x^{2}\}, \langle-x^{2}, -z^{2}, -y^{2}\rangle, (s+1)(6s+5)(6s+7))$$(\langle x^{3}-z^{2}y^{2}\rangle,$$\{-x^{2},$$(\langle 0\rangle, \{x^{3}-z^{2}y^{2}\}, 1)$$-z^{2}y,$ $zy^{2}\rangle,$$s+1)$.

各 $(I, J, b(s))1$ ま $p\in V(I)\backslash V(J)$ における local$b$

関数が $b(s)$ であることを表している. 出力されたこれらのイデアルの根基を計算して整理すると,$\mathbb{C}^{3}$$=$$\{(0,0,0)\}\cup S_{1}\cup S_{2}\cup(\mathbb{C}^{3}\backslash V(f))$という stratification が得られる.

ただし, $S_{1}=(V(x, z)\cup V(y, z))\backslash \{(0,0,0)\},$ま関数$(V(x, z)\cup V(y, z))$ とする. また, 各 stratum に対応する local$b$$b_{f_{)}p}(s)$$S_{2}=V(f)\backslash$$|$$b_{f,p}(s)=\{\begin{array}{l}(s+1)(3s+4)(3s+5)(6s+5)^{2}(6s+7)^{2} , p=(O, 0,0)(s+1)(6s+5)(6s+7) p\in S_{1}(s+1) p\in S_{2}1 p\not\in V(f)\end{array}$stratification の計算には weight (4, 3, 3) に関して weighted homogeneous であり, この weight をであることが分かる. 更に, $k\leq 6$ の1 ま 340 秒を要した. $f$
設定すると 194 秒で計算が完了した.

$f^{k}$

についても計算を行った.

$f^{6}$

の

114

5.2

$A_{k}$

型特異点 $x^{k+1}$ の versal deformation

1 点における local

関数は解析的な不変量であり, local 関数に付随する stratification は超曲面における特異点の分類の情報を与えている.
$f_{k}(x, u_{1}, \ldots, u_{k})$ を
型特異点 $x^{k+1}$ の versal deformation
$b$

$b$

$A_{k}$$f_{k}(x, u_{1}, \ldots , u_{k})=x^{k+1}+u_{1}+u_{2}x+\cdots+u_{k}x^{k-1}$$(k\geq 1)$とし, その判別式 disc $(f_{k})=$ resultant $x(f_{k}(x), f_{k}’(x))$ を考える. これは残が重根をもつ条件を表しており, $V$ (disc $(f_{k})$ ) は根の重複の様子によって自然に stratify される. $k=3$ の場合を考えてみる.

disc $(f_{3})=256u_{1}^{3}-128u_{1}^{2}u_{3}^{2}+144u_{1}u_{2}^{2}u_{3}+16u_{1}u_{3}^{4}-27u_{2}^{4}-4u_{2}^{2}u_{3}^{3}$の曲面で, とく ’swallowtail と呼ばれるものである.
,
とおく. このとき, $V(I_{2,2})\cap V(I_{3,1})=\{(0,0,0)\}$ であり, $V(disc(f_{3}))$ の local
関数に付随する stratification l ま(は$\mathbb{R}^{3}$$I_{2,2}=\{u_{21}4\uparrow x-u_{3}^{2}\rangle$$_{L}$$I_{3,1}=\langle 27\tau x_{2}^{2}+$$8u_{3}^{3},12u_{1}+u_{3}^{2}\rangle$$b$$\mathbb{C}^{3}=S_{4}\cup S_{2,2}\cup S_{3,1}\cup S_{2,1,1}\cup S_{1,1,1,1}$で与えられる. ただし, $S_{4}=\{(0,0,0)\},$ $S_{2,2}=V(I_{2,2})\backslash \{(0,0,0)\},$$S_{2,1,1}=V$ (disc$(f_{3})$)$\backslash (V(I_{2,2})\cup V(I_{3,1})),$ $S_{1,1,1,1}=\mathbb{C}^{3}\backslash V$

重根の取り方と対応するようにとってある. 例えば,

$S_{3,1}$

(disc

は

$(f_{3})$$S_{3,1}=V(I_{3,1})\backslash \{(0,0,0)\}$,) である. 各 $S$ の添字は $fs$ の$(u_{1}, u_{2}, u_{3})\in S_{3,1}$なら$f_{3}$

は 3 重根を 1 つ, 単根を 1 っ持っという意味である. 計算機による実験で $k=5$ までのとき, 重根の取り方
による stratification と一致することが確かめられた. また, この例では $(u_{1}, u_{2\cdots\prime}.u_{k})$ に対する

weight を $(k+1, k, \ldots, 2)$ と取ると disc$(f_{3})$は weighted homogeneous となる. この weight を用

いない場合は計算が非常に困難になる. 例えば, $k=5$ のときは in $(-w,w)$ (disc
基底計算が 1 時間以上経っても終わらなかった.

5.3$D_{k}$

次に,$(f_{5})$) のグレブナー型特異点 $x^{2}y-y^{k-1}$ の versal deformation$D_{k}$

型特異点 $x^{2}y-y^{k-1}$ の versal deformation$f_{k}(x, y, u_{1}, \ldots, uk)=x^{2}y-y^{k-1}+u_{1}+u_{2}x+u_{3}x^{2}+u_{4}y+\cdots+uky^{k-3}$

について考える.

$f_{k}$$(k\geq 4)$

を $(u_{1}, \ldots, u_{k})$ をパラメータとする $(x, y)$ -平面の曲線と見なして, 特異点集合を満たすよのパラメータ空間への射影を考えると, それから
$g_{k}(u_{1},\ldots,uk)$
を入力として用いる.
うな多項式が得られる. このは 7 つの stratum に stratify される. 計算にかかに対して stratification を計算するとる時間は $(u_{1}, u2, u_{3}, u4)$ に対する weight を (6, 4, 2, 4) と設定すれば 4 秒程度しかかからない.
}ま 12 個の stratum にされる. $(u_{1}, u_{2}, u_{3}, u_{4}, u_{5})_{-}$ 対する weight を$g5$ に対しては(8, 5, 2, 6, 4) とすると 8937 秒を要した. 表 1 はこの計算の各ステップにかかった時間を示したも$\langle f_{k},\partial_{x}\neq k_{-},\partial_{y}\neq\}\cap \mathbb{C}[u_{1}, \ldots, uk]=\langle g_{k}\rangle$$g_{k}$$\mathbb{C}^{4}$$g_{4}$$\mathbb{C}^{5}$

のである.

115

表 1: $V(g_{5})$ に対する stratification の計算時間 (秒)

6

まとめ
local

関数に付随する strati 丘 cation を計算する従来の方法は準素分解を必要とするものであったが, その計算は困難である場合も多い. ここで提案した方法は準素分解を用いず, コロンイデア$b$ルの計算やイデアルの包含関係を調べるといった基本的な計算のみを用いるものである. 2 つの方と法におけるの計算は本質的に同じものであるから相互に入れ替えることができる. そのため, 計算効率を考えるにはその後の計算で比較するのが妥当である. 例えば, $V(g_{5})$ に, 巧の計算に 2762 秒を要する. 一方, SINGULAR [2] の関数 primdecGTZ に対してはろ,j との計
よって準素分素を計算させたところ, 5 日以上経過しても結果は返ってこなかった. また,算は各 $it$ こ対して独立であるので, マルチコア環境であれば比較的簡単に並列計算を行うこともで$J_{f}\cap \mathbb{C}[x, t\partial_{t}]$$L_{f}$$V^{j}$$I_{i,j}$

きる.

我々のアルゴリズムは localb 関数が global$b$

関数を割り切るという性質を用いて, 有限個の候補に対してチェックを行うというものである. 最近, Oaku, Bahloul [14] によって local Bernstein-Sato
付随する stratification を計算するアルゴリズムが提案された. local Bemstein-Sato
イデアル?2 local 関数の一般化であり, その計算アルゴリズムも準素分解を用いる方法を拡張しイデアル$l^{\underline{\prime}}$$b$

たものである. しかし, 今のところ local Bernstein-Sato イデアルの候補を有限個にとる方法は分

かっていない. 従って, 今回提案したアルゴリズムを適用することはできない.

参考文献[1] Briangon, J., Granger, M., Maisonobe, Ph., Miniconi, M., Algorithme de calcul du polyn\^ome
de Bemstein: cas non d\’eg\’en\’er\’e. Ann. Inst. Fourier 39, 553-610.
[2] Greuel, G.-M., Pfister, G., Schonemann, H., 2001. SINGULAR 3.0 -A Computer Algebra
System for Polynomial Computations. In M. Kerber and M. Kohlhase: Symbolic Computation and Automated Reasoning, The Calculemus-2000 Symposium, 227-233.
[3] Greuel, G.-M., Lossen, C., Shustin, E., 2007. Introduction to Singularities and Deformations. Springer Monographs in Mathematics.
[4] Kashiwara, M., 1976. B-functions and holonomic systems, Invent. Math. 38, 33-53.

[5] Levandovskyy, V., Morales, J. M., 2008. Computational D-module Theory with SINGULAR, Comparison with Other Systems and Two New Algorithms. Proceedings of ISSAC
2008, ACM Press, 173-180.
[6] Malgrange, B., 1974. Int\’egrales asymptotiques et monodromie, Ann. Sci. $ENS4,405-430$ .

[7] Nakayama, H., 2008. Algorithm computing thegorithm in , To appear in J. Symb. Comp..
$\hat{D}$$b$function by an approximate division al-

116[8] Noro. M., Yokoyama, K., 1999. A Modular Method to Compute the Rational Univariate
Representation of Zero-Dimensional Ideals, J. Symb. Comp. 28, 1, 243-263.
[9] Noro. M., 2002. An Efficient Modular Algorithm for Computing the Global BFunction,

Mathematical Software, Proceedings of the first international congress of mathematicalsoftware, Beijing, Edited by A. M. Cohen, X. S. Gao, N. Takayama, World Scientific, 147157.
[10] Noro, M., 2002. A Computer Algebra System: Risa/Asir, Algebra, Geometry and Software,
M. Joswig and N. Takayama (eds.), Springer, 147-162.
[11] Oaku, T., 1997. Algorithms of computing b-functions. Duke Math. J. 87, 115-132.
[12] Oaku, T., 1997. Algorithms for b-Functions, Restrictions, and Algebraic Local Cohomology
Groups of D-Modules. Advances in Applied Mathematics 19, 61-105.

[13] Oaku, T., 1997. Algorithm for the b-function and D-modules associated to a polynomial.
J. Pure Appl. Algebra 117&118, 495-518.

[14] Oaku, T., Bahloul, R., 2008. Algorithm for Computing Local Bernstein-Sato Ideals, preprint
arXiv $:math/0806.4869vl$ , 2008.
[15] Saito, M., Sturmfels, B., Takayama, N., 2000. Gr\"obner deformations of hypergeometricdifferential equations, Algorithms and Computation in Mathematics 6, Springer-Verlag.

[16] Sato, M., Kashiwara, M., Kimura, T., Oshima, T., 1980. Micro-local analysis of prehomogeneous vector spaces, Invent. Math. 62, 117-179.
[17] Traverso, C., 1988. Groebner trace algorithms, Proceedings of ISSAC’88, LNCS 358,
Springer-Verlag, 125-138.

[18] Yano, T., 1978. On the Holonomic System of
12 Suppl., 469-480.

$f^{s}$

and b-functions. Publ. RIMS Kyoto Univ.

[19] Yano, T., 1978. On the theory of b-functions, Publ. RIMS Kyoto Univ. 14, 111-202.