% $OpenXM: OpenXM/src/k097/lib/minimal/example-ja.tex,v 1.3 2000/08/09 03:45:27 takayama Exp $ \documentclass[12pt]{jarticle} \newtheorem{example}{Example} \def\pd#1{ \partial_{#1} } %% [2] should be replaced by \cite{....} \begin{document} \section{例} 我々が $(u,v)$-極小自由分解の構成に興味をもった動機の 一つは, $D$ 加群 $M$ の制限コホモロジの計算の効率化である. [2] では, $M$ の Schreyer resolution が $(-{\bf 1},{\bf 1})$ に適合した $M$ の自由分解であることを証明し, これを用いた制限コホモロジの計算法を与えた. この方法を適用するには $(-w,w)$ に適合した $M$ の自由分解ならなんでもよく, Schreyer resolution をとる必然性はない. [2] の方法では, 1 点への制限を計算するのに次元 $$O\left( (\mbox{ 自由分解の betti 数}) \times \left(\mbox{$b$関数の最大整数根}\right)^n\right)$$ のベクトル空間の複体の ${\rm Ker}/{\rm Im}$ を 計算する必要が生じる. ( 部分多様体への制限には $D_m$, $(m < n)$ 自由加群の複体 のコホモロジを計算する必要がある.) したがって, betti 数が大きくなると, 計算すべき ベクトル空間の次元が 大きくなり, メモリ不足をまねいていた. $(-w,w)$-極小自由分解の betti 数は Schreyer resolution の betti 数に 比較してかなり小さくいままで制限が計算できなかった例も計算できるように なった. Schreyer resolution の betti 数と $(-w,w)$-極小自由分解の betti 数を いくつかの例について比較してみよう. 比較の前にいくつか記号と予備知識を導入する. \begin{enumerate} \item Schreyer resolution の betti 数は $(-w,w)$ だけでなく tie-breaking order にも依存する. 以下 tie-breaking order として, graded reverse lexicographic order を用いる. \item 多項式 $f$ の $b$-関数の最小整数根を $-r$ とするとき ${\rm Ann}(D f^{-1})$ で $1/f^r$ を零化する $D$ のイデアルのある生成元の集合をあらわす. 下の実例の場合では関数 {\tt Sannfs(f,v)} の出力をあらわす. \item $F(G)$ で $G$ の formal Laplace 変換をあらわす. \item $F^h(G)$ で $G$ の formal Laplace 変換を homogenize したものをあらわす. \item Grothendieck の比較定理によれば $I = F({\rm Ann} D f^{-1})$ とおくとき $D/I$ の原点への制限コホモロジ が空間 $ {\bf C}^n \setminus V(f)$ の ${\bf C}$-係数コホモロジ群に一致する. ( "An algorithm for de Rham cohomology groups of the complement of an affine variety via D-module computation", Journal of pure and applied algebra, 139 (1999), 201--233. を参照) \end{enumerate} \begin{example} \rm \label{example:cusp} %Prog: minimal-test.k test18() $I = F^h\left[{\rm Ann}\left( D \frac{1}{x^3-y^2} \right) \right]$ の場合. イデアル $I$ は $$ -2x\pd{x}-3y\pd{y}+h^2 , -3y\pd{x}^2+2x\pd{y}h $$ で生成される. \begin{tabular}{|l|l|} \hline Resolution type & Betti numbers \\ \hline Schreyer & 1, 4, 4, 1 \\ \hline $(-{\bf 1},{\bf 1})$-minimal & 1, 2, 1 \\ \hline minimal & 1, 2, 1 \\ \hline \end{tabular} \noindent $(-{\bf 1},{\bf 1})$-minimal resolution {\footnotesize \begin{verbatim} [ [ [ -2*x*Dx-3*y*Dy+h^2 ] [ -3*y*Dx^2+2*x*Dy*h ] ] [ [ -3*y*Dx^2+2*x*Dy*h , 2*x*Dx+3*y*Dy ] ] ] Degree shifts [ [ 0 ] , [ 0 , 1 ] ] \end{verbatim}} Schreyer Resolution %%Prog: a=test18(); sm1_pmat(a[3]); {\footnotesize \begin{verbatim} [ [ [ -2*x*Dx-3*y*Dy+h^2 ] [ -3*y*Dx^2+2*x*Dy*h ] [ 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h ] [ 27*y^3*Dy^2+27*y^2*Dy*h^2-3*y*h^4-8*x^3*Dy*h ] ] [ [ 9*y^2*Dy+3*y*h^2 , 0 , 2*x , 1 ] [ -4*x^2*Dy*h , 0 , -3*y*Dy+4*h^2 , Dx ] [ 2*x*Dy*h , 3*y*Dy-2*h^2 , Dx , 0 ] [ 3*y*Dx , -2*x , 1 , 0 ] ] [ [ -Dx , 1 , 2*x , 3*y*Dy-2*h^2 ] ] ] \end{verbatim}} \end{example} \begin{example} \rm %Prog: minimal-test.k test17b() $I = F^h\left[{\rm Ann}\left( D \frac{1}{x^3-y^2z^2} \right) \right]$ の場合. \begin{tabular}{|l|l|} \hline Resolution type & Betti numbers \\ \hline Schreyer & 1, 8, 16, 11, 2 \\ \hline $(-{\bf 1},{\bf 1})$-minimal & 1, 4, 5, 2 \\ \hline minimal & 1, 4, 5, 2 \\ \hline \end{tabular} \noindent $(-{\bf 1},{\bf 1})$-minimal resolution {\footnotesize \begin{verbatim} [ [ [ y*Dy-z*Dz ] [ -2*x*Dx-3*z*Dz+h^2 ] [ 2*x*Dy*Dz^2-3*y*Dx^2*h ] [ 2*x*Dy^2*Dz-3*z*Dx^2*h ] ] [ [ 0 , 2*x*Dy^2*Dz-3*z*Dx^2*h , 0 , 2*x*Dx+3*z*Dz ] [ 2*x*Dx+3*z*Dz-h^2 , y*Dy-z*Dz , 0 , 0 ] [ 3*Dx^2*h , 0 , Dy , -Dz ] [ 6*x*Dy*Dz^2-9*y*Dx^2*h , -2*x*Dy*Dz^2+3*y*Dx^2*h , -2*x*Dx-3*y*Dy , 0 ] [ 2*x*Dy*Dz , 0 , z , -y ] ] [ [ y , -2*x*Dy*Dz , 3*y*z , z , 2*x*Dx ] [ Dz , -3*Dx^2*h , 2*x*Dx+3*y*Dy+3*z*Dz+6*h^2 , Dy , -3*Dy*Dz ] ] ] Degree shifts [ [ 0 ] , [ 0 , 0 , 2 , 2 ] , [ 2 , 0 , 3 , 2 , 1 ] ] \end{verbatim}} \end{example} \begin{example} \rm %Prog: minimal-test.k test22(); $I = F^h\left[{\rm Ann}\left( D \frac{1}{x^3+y^3+z^3} \right) \right]$ の場合. %% Uli Walther の 論文 (MEGA 2000) の例と betti 数を比較せよ. \begin{tabular}{|l|l|} \hline Resolution type & Betti numbers \\ \hline Schreyer & 1, 12, 44, 75, 70, 39, 13, 2 \\ \hline $(-1,-2,-3,1,2,3)$-minimal & 1, 4, 5, 2 \\ \hline minimal & 1, 4, 5, 2 \\ \hline \end{tabular} \noindent $(-1,-2,-3,1,2,3)$-minimal resolution {\footnotesize \begin{verbatim} [ [ [ x*Dx+y*Dy+z*Dz-3*h^2 ] [ y*Dz^2-z*Dy^2 ] [ x*Dz^2-z*Dx^2 ] [ x*Dy^2-y*Dx^2 ] ] [ [ 0 , -x , y , -z ] [ -x*Dz^2+z*Dx^2 , x*Dy , x*Dx+z*Dz-3*h^2 , z*Dy ] [ -x*Dy^2+y*Dx^2 , -x*Dz , y*Dz , x*Dx+y*Dy-3*h^2 ] [ -y*Dz^2+z*Dy^2 , x*Dx+y*Dy+z*Dz-2*h^2 , 0 , 0 ] [ 0 , Dx^2 , -Dy^2 , Dz^2 ] ] [ [ -x*Dx+3*h^2 , y , -z , -x , 0 ] [ -Dz^3-Dy^3 , -Dy^2 , Dz^2 , Dx^2 , -x*Dx-y*Dy-z*Dz ] ] ] Degree shifts [ [ 0 ] , [ 0 , 4 , 5 , 3 ] , [ 3 , 5 , 6 , 4 , 9 ] ] \end{verbatim}} \end{example} \begin{example} \rm %Prog: minimal-test.k test21(); $I = F^h\left[{\rm Ann}\left( D \frac{1}{x^3-y^2z^2+y^2+z^2} \right) \right]$ の場合. \begin{tabular}{|l|l|} \hline Resolution type & Betti numbers \\ \hline Schreyer & 1, 13, 43, 50, 21, 2 \\ \hline $(-{\bf 1},{\bf 1})$-minimal & 1, 7, 10, 4 \\ \hline minimal & 1, 7, 10, 4 \\ \hline \end{tabular} \noindent $f=x^3-y^2z^2+y^2+z^2$ とおいた場合, 空間 ${\bf C}^3 \setminus V(f)$ の コホモロジ群の次元は ${\rm dim}\, H^i = 1$, $(i=0, 1)$, ${\rm dim}\, H^i = 0$, $(i=2, 3)$, となる. この場合 $D/I$ の $b$-関数の最大整数根は $2$ となり, コホモロジを計算するために 考える線形空間の複体の次元は, $10, 12, 9, 4$ である. %%Prog: Srestall.sm1 一方 Schreyer resolution からスタートして, 線形空間の複体を考えると, その次元は 130, 1078, 1667, 749, 40 となる. %%Prog: test21b() \end{example} \begin{example} \rm %Prog: minimal-test.k test20() $I = D\cdot\{ x_1\pd{1}+2x_2\pd{2}+3x_3\pd{3} , \pd{1}^2-\pd{2}h, -\pd{1}\pd{2}+\pd{3}h, \pd{2}^2-\pd{1}\pd{3} \} $ の場合. これは $A=(1,2,3)$, $\beta=0$ に付随する GKZ 超幾何系の homogenization. \begin{tabular}{|l|l|} \hline Resolution type & Betti numbers \\ \hline Schreyer & 1, 10, 25, 23, 8, 1 \\ \hline $(-{\bf 1},{\bf 1})$-minimal & 1, 4, 5, 2 \\ \hline minimal & 1, 4, 5, 2 \\ \hline \end{tabular} \noindent $(-{\bf 1},{\bf 1})$-minimal resolution {\footnotesize \begin{verbatim} [ [ [ x1*Dx1+2*x2*Dx2+3*x3*Dx3 ] [ Dx1^2-Dx2*h ] [ -Dx1*Dx2+Dx3*h ] [ Dx2^2-Dx1*Dx3 ] ] [ [ Dx1*Dx2-Dx3*h , -x1*Dx2 , 2*x2*Dx2+3*x3*Dx3+3*h^2 , -x1*h ] [ Dx1^2-Dx2*h , -x1*Dx1-3*x3*Dx3-2*h^2 , 2*x2*Dx1 , 2*x2*h ] [ Dx2^2-Dx1*Dx3 , x1*Dx3 , x1*Dx2 , -2*x2*Dx2-3*x3*Dx3-4*h^2 ] [ 0 , Dx3 , Dx2 , Dx1 ] [ 0 , -Dx2 , -Dx1 , -h ] ] [ [ Dx2 , -Dx3 , -Dx1 , -2*x2*Dx2-3*x3*Dx3-4*h^2 , -x1*Dx2-2*x2*Dx3 ] [ -Dx1 , Dx2 , h , -x1*h , -3*x3*Dx3-h^2 ] ] ] Degree shifts [ [ 0 ] , [ 0 , 2 , 2 , 2 ] , [ 2 , 2 , 2 , 3 , 3 ] ] \end{verbatim}} %%Prog:test23() of minimal-test.k この極小自由分解は実は 行列 $(1,2,3)$ できまる affine toric ideal の極小自由分解の Koszul complex になってる. Gel'fand, Kapranov, Zelevinsky によって導入された $D/I$ の resolution を自然に延長した次の 2 重複体を考えよう. $$ \begin{array}{ccccccccc} 0 & \longrightarrow & D^2 & \stackrel{d^1}{\longrightarrow} & D^3 & \stackrel{d^2}{\longrightarrow} & D & \longrightarrow & 0 \\ & & u^1 \downarrow & & u^2 \downarrow & & u^3 \downarrow & \\ 0 & \longrightarrow & D^2 & \stackrel{d^1}{\longrightarrow} & D^3 & \stackrel{d^2}{\longrightarrow} & D & \longrightarrow & 0 \end{array} $$ ここでは, (誤解もないと思うので) $D$ で同次化ワイル代数, $d^i$ で affine toric ideal の同次化の多項式環での極小自由分解 $$ d^2 = \pmatrix{ \pd{1}^2 - \pd{2}^2 h \cr -\pd{1} \pd{2} + \pd{3} h \cr \pd{2}^2 - \pd{1} \pd{3} \cr }, \ d^1 = \pmatrix{ -\pd{2} & -\pd{1} & -h \cr \pd{3} & \pd{2} & \pd{1} \cr } $$ をあらわすものとする. また $\ell = x_1 \pd{1} + 2 x_2 \pd{2} + 3 x_3 \pd{3}$ とおくとき $u^i$ を 次のようにきめる. $$ u^1=\pmatrix{ \ell + 4 h^2 & 0 \cr 0 & \ell+5 h^2 \cr}, \quad u^2=\pmatrix{\ell+2 h^2 & 0 & 0 \cr 0 & \ell + 3 h^2 & 0 \cr 0 & 0 & \ell+ 4 h^2 \cr}, \quad u^3 = \pmatrix{ \ell \cr}. $$ このとき付随する 1 重複体は $$L^1 \ni f \mapsto (-d^1(f), u^1(f)) \in L^2 \oplus L^1, $$ $$ L^2\oplus L^1 \ni (f,g)\mapsto (-d^2(f), u^2(f)+d^1(g)) \in L^3\oplus L^2, $$ $$ L^3\oplus L^2 \ni (f,g)\mapsto u^3(f)+d^2(g) \in L^3. $$ であたえられる. ここで $L^1 = D^2$, $L^2 = D^3$, $L^3 = D$ である. この 1 重複体の具体形は以下のとうり. \footnotesize{ \begin{verbatim} [ [ [ x1*Dx1+2*x2*Dx2+3*x3*Dx3 ] [ Dx1^2-Dx2*h ] [ -Dx1*Dx2+Dx3*h ] [ Dx2^2-Dx1*Dx3 ] ] [ [ -Dx1^2+Dx2*h , x1*Dx1+2*x2*Dx2+3*x3*Dx3+2*h^2 , 0 , 0 ] [ Dx1*Dx2-Dx3*h , 0 , x1*Dx1+2*x2*Dx2+3*x3*Dx3+3*h^2 , 0 ] [ -Dx2^2+Dx1*Dx3 , 0 , 0 , x1*Dx1+2*x2*Dx2+3*x3*Dx3+4*h^2 ] [ 0 , -Dx2 , -Dx1 , -h ] [ 0 , Dx3 , Dx2 , Dx1 ] ] [ [ Dx2 , Dx1 , h , x1*Dx1+2*x2*Dx2+3*x3*Dx3+4*h^2 , 0 ] [ -Dx3 , -Dx2 , -Dx1 , 0 , x1*Dx1+2*x2*Dx2+3*x3*Dx3+5*h^2 ] ] ] \end{verbatim} } \end{example} \section{実装} ここでは \begin{verbatim} /* OpenXM: OpenXM/src/k097/lib/minimal/minimal.k,v 1.25 2000/08/02 05:14:31 takayama Exp */ \end{verbatim} 版の {\tt minimal.k} に準拠して実装の概略を解説する. 実装の説明のための例としてイデアル $$ I = D \cdot \{ -2x\pd{x}-3y\pd{y}+h^2, -3y\pd{x}^2+2x\pd{y}h \} $$ の $(u,v) = (-1,-1,1,1)$-極小分解の構成 を考えよう. %%Prog: minimal-note-ja.txt 6/9 (Fri) および以後の bug fix の記録を参照. %%例として, イデアル %%$$ I = D \cdot \{ x^2 + y^2, x y \} $$ %%の $(u,v) = (-1,-1,1,1)$-極小分解の構成 %%を考えよう. %%(この場合は多項式環の同次式で生成されるので, 多項式環での %% 極小自由分解の計算と同じことになる.) この場合, $I$ のグレブナ基底 $G$ は {\footnotesize \begin{verbatim} [ [ -2*x*Dx-3*y*Dy+h^2 ] [ -3*y*Dx^2+2*x*Dy*h ] [ 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h ] [ 27*y^3*Dy^2+27*y^2*Dy*h^2-3*y*h^4-8*x^3*Dy*h ] ] \end{verbatim} } \noindent となっており, Schreyer resolution は {\footnotesize \begin{verbatim} [ [ [ -2*x*Dx-3*y*Dy+h^2 ] [ -3*y*Dx^2+2*x*Dy*h ] [ 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h ] [ 27*y^3*Dy^2+27*y^2*Dy*h^2-3*y*h^4-8*x^3*Dy*h ] ] [ [ 9*y^2*Dy+3*y*h^2 , 0 , 2*x , 1 ] [ -4*x^2*Dy*h , 0 , -3*y*Dy+4*h^2 , Dx ] [ 2*x*Dy*h , 3*y*Dy-2*h^2 , Dx , 0 ] [ 3*y*Dx , -2*x , 1 , 0 ] ] [ [ -Dx , 1 , 2*x , 3*y*Dy-2*h^2 ] ] ] \end{verbatim} } \noindent である. $1$ がたくさん Schreyer resolution の中にはあることに 注意. $1$ は極小自由分解には必要ない元であることを意味する. 極小自由分解は, 例 \ref{example:cusp} に具体形を書いておいた. \medbreak この実装では極小自由分解を LaScala のアルゴリズムをもとにして 構成する (LaScala and Stillman [??] および数理科学の記事 ??? を参照). このアルゴリズムは既知として, 違いのみを説明しよう. LaScala のアルゴリズムは, reduction したときに $0$ になった場合, その reduction に付随した syzygy を 極小自由分解の元とし, reduction したときに $0$ にならなかった場合, その元を グレブナ基底の元として加え, 付随した syzygy は極小自由分解では余計なものと みなす. われわれは $(u,v)$-極小な自由分解をもとめたい. そこで上の手続きを次のように変える. \begin{center} \begin{minipage}{10cm} Reduction したときに modulo $(u,v)$-フィルターで $0$ になった場合, その reduction に付随した syzygy を 極小自由分解の元とし, さらに その元が $0$ でなければグレブナ基底に加える. reduction したときに modulo $(u,v)$-フィルターで $0$ にならなかった場合, その元をグレブナ基底の元として加え, 付随した syzygy は極小自由分解では余計なものとみなす. \end{minipage} \end{center} ちなみに, $(-w,w)$-極小自由分解と 極小自由分解がことなる例をさがしているが これはまだ見つかっていない. ちょっと不思議である. \bigbreak {\tt minimal.k} のソースコードではこの部分は次のようになっている. {\footnotesize \begin{verbatim} def SlaScala(g,opt) { ... ... f = SpairAndReduction(skel,level,i,freeRes,tower,ww); if (f[0] != Poly("0")) { place = f[3]; if (Sordinary) { redundantTable[level-1,place] = redundant_seq; redundant_seq++; }else{ if (f[4] > f[5]) { (い) /* Zero in the gr-module */ Print("v-degree of [org,remainder] = "); Println([f[4],f[5]]); Print("[level,i] = "); Println([level,i]); redundantTable[level-1,place] = 0; }else{ (ろ) redundantTable[level-1,place] = redundant_seq; redundant_seq++; } } redundantTable_ordinary[level-1,place] =redundant_seq_ordinary; ... ... } \end{verbatim} } 少々長くなるが, この部分にあらわれる変数の説明をしよう. LaScala のアルゴリズムでは, 最初に計算すべき S-pair の計算手順, および Schreyer frame を作成する. Schreyer frame は Schreyer resolution の initial である. これらはあらかじめ {\tt SresolutionFrameWithTower(g,opt);} で計算されて, {\tt tower} および {\tt skel} に格納されている. これらの変数の値は, 関数 {\tt Sminimal()} の戻り値として 見ることができる. 関数 {\tt Sminimal()} の戻り値が変数 $a$ に格納されているとすると, {\tt a[0]} が極小自由分解 {\tt a[3]} が Schreyer 自由分解(とくに {\tt a[3,0]} が $I$ のグレブナ基底), {\tt a[4]} が, 関数 {\tt SlaScala()} の 変数 {\tt [rf[0], tower, skel, rf[3]]} の値である. したがって, {\tt tower} は {\tt a[4,1]} に格納されている. $I$ の場合の {\tt tower} は以下のとうり. {\footnotesize \begin{verbatim} In(25)=sm1_pmat(a[4,1]); [ [ -2*x*Dx , -3*y*Dx^2 , -9*y^2*Dx*Dy , -27*y^3*Dy^2 ] [ -9*y^2*Dy , -3*es^2*y*Dy , -3*es*y*Dy , -3*y*Dx ] [ -Dx ] ] \end{verbatim} } \noindent ここで ${\tt es}^i$ はベクトルの 第 $i$ 成分であることをしめしている. たとえば, \verb# -3*es^2*y*Dy # は \verb# [0, 0, -3*y*Dy, 0] # を意味する. 変数 {\tt skel} には S-pair (sp) の計算手順がはいっている. $I$ の場合には以下のとうり. {\footnotesize \begin{verbatim} In(16)=sm1_pmat(a[4,2]); [ [ ] [ [ [ 0 , 2 ] G'[0] と G'[2] の sp を計算 (0) [ -9*y^2*Dy , 2*x ] ] [ [ 2 , 3 ] G'[2] と G'[3] の sp を計算 (1) [ -3*y*Dy , Dx ] ] [ [ 1 , 2 ] G'[1] と G'[2] の sp を計算 (2) [ -3*y*Dy , Dx ] ] [ [ 0 , 1 ] G'[0] と G'[1] の sp を計算 (3) [ -3*y*Dx , 2*x ] ] ] [ [ [ 0 , 3 ] G''[0] と G''[3] の sp を計算 [ -Dx , 3*y*Dy ] ] ] [ ] ] \end{verbatim} } \noindent ここで $G'$ は Schreyer order で得られた $G$ の syzygy の生成元, $G''$ は Schreyer order で得られた $G'$ の syzygy の生成元をあらわす. たとえば上の例では, $G'[0]$ は $G[0]$ と $G[2]$ の sp の計算により得られた syzygy, $G'[1]$ は $G[2]$ と $G[3]$ の sp の計算により得られた syzygy, ... を意味する. {\footnotesize \begin{verbatim} f = SpairAndReduction(skel,level,i,freeRes,tower,ww); \end{verbatim} } \noindent では {\tt skel[level,i]} に格納された S-pair を計算して, {\tt freeRes[level-1]} で reduction をおこなう. Reduction のための Schreyer order は \\ {\tt StowerOf(tower,level-1)} を用いる. たとえば, ${\tt [level,i] = [1,3]}$ のときに 関数 {\tt SpairAndReduction} で どのような計算がなされているか $I$ の場合にみてみよう. {\tt SpairAndReduction} の実行時 に次のようなメッセージがでてくる. {\footnotesize \begin{verbatim} reductionTable= [ [ 1 , 2 , 3 , 4 ] [ 3 , 4 , 3 , 2 ] [ 3 ] ] [ 0 , 0 ] Processing [level,i]= [ 0 , 0 ] Strategy = 1 [ 0 , 1 ] Processing [level,i]= [ 0 , 1 ] Strategy = 2 [ 1 , 3 ] Processing [level,i]= [ 1 , 3 ] Strategy = 2 SpairAndReduction: [ p and bases , [ [ 0 , 1 ] , [ -3*y*Dx , 2*x ] ] , [-2*x*Dx-3*y*Dy+h^2 , -3*y*Dx^2+2*x*Dy*h , %[null] , %[null] ] ] [ level= , 1 ] [ tower2= , [ [ ] ] ] [ -3*y*Dx , 2*es*x ] [gi, gj] = [ -2*x*Dx-3*y*Dy+h^2 , -3*y*Dx^2+2*x*Dy*h ] 1 Reduce the element 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h by [ -2*x*Dx-3*y*Dy+h^2 , -3*y*Dx^2+2*x*Dy*h , %[null] , %[null] ] result is [ 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h , 1 , [ 0 , 0 , 0 , 0 ] ] vdegree of the original = 0 vdegree of the remainder = 0 [ 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h , [ -3*y*Dx , 2*x , 0 , 0 ] , 3 , 2 , 0 , 0 ] \end{verbatim} } \noindent 最初に表示される {\tt reductionTable} の意味はあとで説明する. 次の行に注目しよう. ここでは {\tt skel[0,4]} の S-pair を計算してreduction している. {\footnotesize \begin{verbatim} SpairAndReduction: [ p and bases , [ [ 0 , 1 ] , [ -3*y*Dx , 2*x ] ] , [-2*x*Dx-3*y*Dy+h^2 , -3*y*Dx^2+2*x*Dy*h , %[null] , %[null] ] ] \end{verbatim} } \noindent {\tt [0, 1]} は $G'[0]$ と $G'[1]$ の sp を計算 せよという意味である. ${\tt level} = 0$ で既にもとまっている ブレブナ基底は $G[0]$ と $G[1]$ のみであり, それらはそれぞれ, \verb# -2*x*Dx-3*y*Dy+h^2 , -3*y*Dx^2+2*x*Dy*h # である. {\tt SpairAndReduction} は $G[0]$, $G[1]$ のみを用いて, S-pair \\ \verb# 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h # を reduction する. 結局 reduction の結果は 0 ではなくて, \\ \verb# 9*y^2*Dx*Dy+3*y*Dx*h^2+4*x^2*Dy*h # となる. LaScala のアルゴリズムの 2 倍お得システムで, これが新しいグレブナ基底の元 {\tt G[place]} となり, reduction の過程より syzygy も得られる. さて, $(u,v)$-極小分解を作るには, reduction した余りが $(u,v)$-フィルターで modulo して $0$ かどうか調べないといけない. このため, 関数 {\tt Sdegree()} を用いて, reduction する前の元, および余りの シフト付き $(u,v)$-order を計算する. この例では, 両方とも $0$ である. {\footnotesize \begin{verbatim} vdegree of the original = 0 vdegree of the remainder = 0 \end{verbatim} } したがって, modulo $(u,v)$-フィルターでも $0$ でない. 準備説明がおわった. 最初のプログラム {\tt SlaScala()} の説明に戻る. {\tt SpairAndReduction()} の戻り値 {\tt f[0]} には, reduction した余り, {\tt f[4]}, {\tt f[5]} には, reduction する前の元, および余りの シフト付き $(u,v)$-order が格納されている. この例の場合には (ろ) の場合が実行されて, 付随した syzygy は 極小自由分解には不要なものとして {\tt redundantTable} に登録される: {\footnotesize \begin{verbatim} redundantTable[level-1,place] = redundant_seq; \end{verbatim} } \noindent 余り {\tt f[0]} は, laScala のアルゴリズムの 2 倍お得現象で得られた, 新しいブレブナ基底の元であるが, これを保存すべき場所のインデックスは, 戻り値 {\tt f[3]}({\tt place}) に格納されている: {\footnotesize \begin{verbatim} bases[place] = f[0]; freeRes[level-1] = bases; reducer[level-1,place] = f[1]; \end{verbatim} } \noindent この reduction で得られた syzygy (の本質的部分)は, 変数 {\tt reducer} に登録される. 以上で $(u,v)$-極小自由分解特有の処理の部分の解説を終える. \bigbreak 以下では, LaScala のアルゴリズムのわれわれの実装の概略と問題点を 述べる. まず, 変数 {\tt reductionTable} の意味を説明しよう. LaScala のアルゴリズムでは, {\tt level - Sdegree(s)} の小さい S-pair から計算していく. 関数 {\tt Sdegree} は次のように再帰的に定義されている. {\footnotesize \begin{verbatim} /* f is assumed to be a monomial with toes. */ def Sdegree(f,tower,level) { local i,ww, wd; /* extern WeightOfSweyl; */ ww = WeightOfSweyl; f = Init(f); if (level <= 1) return(StotalDegree(f)); i = Degree(f,es); return(StotalDegree(f)+Sdegree(tower[level-2,i],tower,level-1)); } \end{verbatim} } \noindent ここで {\tt StotalDegree(f)} は $f$ の全次数である. \noindent さて, LaScala のアルゴリズムでは, Resolution を下から順番に計算していくのではない. これが本質的な点である. この順番は変数 {\tt reductionTable} にはっている. $I$ の例では {\footnotesize \begin{verbatim} reductionTable= [ [ 1 , 2 , 3 , 4 ] [ 3 , 4 , 3 , 2 ] skel[0] に対応 [ 3 ] skel[1] に対応 ] \end{verbatim} } \noindent となる. 現在の実装での計算速度, メモリ使用量のボトルネックを 指摘しておく. LaScala のアルゴリズムでは, Schreyer Frame を構成してから, 極小自由分解を構成する. 下記のプログラムの変数 {\tt redundantTable[level,q]} には, 対応する syzygy と グレブナ基底の元が何回目の reduction で生成 されたかの数がはいっている. 極小自由分解の構成では, 最後の reduction の syzygy から始めて, Schreyer resolution から極小自由分解にとって余分な元を取り除いて いく ({\tt seq} を $1$ づつ減らしていく). {\footnotesize \begin{verbatim} def Sminimal(g,opt) { .... while (seq > 1) { seq--; for (level = 0; level < maxLevel; level++) { betti = Length(freeRes[level]); for (q = 0; q