Annotation of OpenXM/src/asir-doc/parts/groebner.texi, Revision 1.6
1.6 ! noro 1: @comment $OpenXM: OpenXM/src/asir-doc/parts/groebner.texi,v 1.5 2003/04/20 08:01:25 noro Exp $
1.2 noro 2: \BJP
1.1 noro 3: @node $B%0%l%V%J4pDl$N7W;;(B,,, Top
4: @chapter $B%0%l%V%J4pDl$N7W;;(B
1.2 noro 5: \E
6: \BEG
7: @node Groebner basis computation,,, Top
8: @chapter Groebner basis computation
9: \E
1.1 noro 10:
11: @menu
1.2 noro 12: \BJP
1.1 noro 13: * $BJ,;6I=8=B?9`<0(B::
14: * $B%U%!%$%k$NFI$_9~$_(B::
15: * $B4pK\E*$JH!?t(B::
16: * $B7W;;$*$h$SI=<($N@)8f(B::
17: * $B9`=g=x$N@_Dj(B::
18: * $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B::
19: * $B4pDlJQ49(B::
1.5 noro 20: * Weyl $BBe?t(B::
1.1 noro 21: * $B%0%l%V%J4pDl$K4X$9$kH!?t(B::
1.2 noro 22: \E
23: \BEG
24: * Distributed polynomial::
25: * Reading files::
26: * Fundamental functions::
27: * Controlling Groebner basis computations::
28: * Setting term orderings::
29: * Groebner basis computation with rational function coefficients::
30: * Change of ordering::
1.5 noro 31: * Weyl algebra::
1.2 noro 32: * Functions for Groebner basis computation::
33: \E
1.1 noro 34: @end menu
35:
1.2 noro 36: \BJP
1.1 noro 37: @node $BJ,;6I=8=B?9`<0(B,,, $B%0%l%V%J4pDl$N7W;;(B
38: @section $BJ,;6I=8=B?9`<0(B
1.2 noro 39: \E
40: \BEG
41: @node Distributed polynomial,,, Groebner basis computation
42: @section Distributed polynomial
43: \E
1.1 noro 44:
45: @noindent
1.2 noro 46: \BJP
1.1 noro 47: $BJ,;6I=8=B?9`<0$H$O(B, $BB?9`<0$NFbIt7A<0$N0l$D$G$"$k(B. $BDL>o$NB?9`<0(B
48: (@code{type} $B$,(B 2) $B$O(B, $B:F5"I=8=$H8F$P$l$k7A<0$GI=8=$5$l$F$$$k(B. $B$9$J$o(B
49: $B$A(B, $BFCDj$NJQ?t$r<gJQ?t$H$9$k(B 1 $BJQ?tB?9`<0$G(B, $B$=$NB>$NJQ?t$O(B, $B$=$N(B 1 $BJQ(B
50: $B?tB?9`<0$N78?t$K(B, $B<gJQ?t$r4^$^$J$$B?9`<0$H$7$F8=$l$k(B. $B$3$N78?t$,(B, $B$^$?(B,
51: $B$"$kJQ?t$r<gJQ?t$H$9$kB?9`<0$H$J$C$F$$$k$3$H$+$i:F5"I=8=$H8F$P$l$k(B.
1.2 noro 52: \E
53: \BEG
54: A distributed polynomial is a polynomial with a special internal
55: representation different from the ordinary one.
56:
57: An ordinary polynomial (having @code{type} 2) is internally represented
58: in a format, called recursive representation.
59: In fact, it is represented as an uni-variate polynomial with respect to
60: a fixed variable, called main variable of that polynomial,
61: where the other variables appear in the coefficients which may again
62: polynomials in such variables other than the previous main variable.
63: A polynomial in the coefficients is again represented as
64: an uni-variate polynomial in a certain fixed variable,
65: the main variable. Thus, by this recursive structure of polynomial
66: representation, it is called the `recursive representation.'
67: \E
1.1 noro 68:
69: @iftex
70: @tex
1.2 noro 71: \JP $(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
72: \EG $(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
1.1 noro 73: @end tex
74: @end iftex
75: @ifinfo
76: @example
77: (x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))
78: @end example
79: @end ifinfo
80:
81: @noindent
1.2 noro 82: \BJP
1.1 noro 83: $B$3$l$KBP$7(B, $BB?9`<0$r(B, $BJQ?t$NQQ@Q$H78?t$N@Q$NOB$H$7$FI=8=$7$?$b$N$rJ,;6(B
84: $BI=8=$H8F$V(B.
1.2 noro 85: \E
86: \BEG
87: On the other hand,
88: we call a representation the distributed representation of a polynomial,
89: if a polynomial is represented, according to its original meaning,
90: as a sum of monomials,
91: where a monomial is the product of power product of variables
92: and a coefficient. We call a polynomial, represented in such an
93: internal format, a distributed polynomial. (This naming may sounds
94: something strange.)
95: \E
1.1 noro 96:
97: @iftex
98: @tex
1.2 noro 99: \JP $(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz +1 \cdot z^2$
100: \EG $(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz +1 \cdot z^2$
1.1 noro 101: @end tex
102: @end iftex
103: @ifinfo
104: @example
105: (x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$
106: @end example
107: @end ifinfo
108:
109: @noindent
1.2 noro 110: \BJP
1.1 noro 111: $B%0%l%V%J4pDl7W;;$K$*$$$F$O(B, $BC19`<0$KCmL\$7$FA`:n$r9T$&$?$aB?9`<0$,J,;6I=8=(B
112: $B$5$l$F$$$kJ}$,$h$j8zN($N$h$$1i;;$,2DG=$K$J$k(B. $B$3$N$?$a(B, $BJ,;6I=8=B?9`<0$,(B,
113: $B<1JL;R(B 9 $B$N7?$H$7$F(B @b{Asir} $B$N%H%C%W%l%Y%k$+$iMxMQ2DG=$H$J$C$F$$$k(B.
114: $B$3$3$G(B, $B8e$N@bL@$N$?$a$K(B, $B$$$/$D$+$N8@MU$rDj5A$7$F$*$/(B.
1.2 noro 115: \E
116: \BEG
117: For computation of Groebner basis, efficient operation is expected if
118: polynomials are represented in a distributed representation,
119: because major operations for Groebner basis are performed with respect
120: to monomials.
121: From this view point, we provide the object type distributed polynomial
122: with its object identification number 9, and objects having such a type
123: are available by @b{Asir} language.
124:
125: Here, we provide several definitions for the later description.
126: \E
1.1 noro 127:
128: @table @b
1.2 noro 129: \BJP
1.1 noro 130: @item $B9`(B (term)
131: $BJQ?t$NQQ@Q(B. $B$9$J$o$A(B, $B78?t(B 1 $B$NC19`<0$N$3$H(B. @b{Asir} $B$K$*$$$F$O(B,
1.2 noro 132: \E
133: \BEG
134: @item term
135: The power product of variables, i.e., a monomial with coefficient 1.
136: In an @b{Asir} session, it is displayed in the form like
137: \E
1.1 noro 138:
139: @example
140: <<0,1,2,3,4>>
141: @end example
142:
1.2 noro 143: \BJP
1.1 noro 144: $B$H$$$&7A$GI=<($5$l(B, $B$^$?(B, $B$3$N7A$GF~NO2DG=$G$"$k(B. $B$3$NNc$O(B, 5 $BJQ?t$N9`(B
145: $B$r<($9(B. $B3FJQ?t$r(B @code{a}, @code{b}, @code{c}, @code{d}, @code{e} $B$H$9$k$H(B
146: $B$3$N9`$O(B @code{b*c^2*d^3*e^4} $B$rI=$9(B.
1.2 noro 147: \E
148: \BEG
149: and also can be input in such a form.
150: This example shows a term in 5 variables. If we assume the 5 variables
151: as @code{a}, @code{b}, @code{c}, @code{d}, and @code{e},
152: the term represents @code{b*c^2*d^3*e^4} in the ordinary expression.
153: \E
1.1 noro 154:
1.2 noro 155: \BJP
1.1 noro 156: @item $B9`=g=x(B (term order)
157: $BJ,;6I=8=B?9`<0$K$*$1$k9`$O(B, $B<!$N@-<A$rK~$?$9A4=g=x$K$h$j@0Ns$5$l$k(B.
1.2 noro 158: \E
159: \BEG
160: @item term order
161: Terms are ordered according to a total order with the following properties.
162: \E
1.1 noro 163:
164: @enumerate
165: @item
1.2 noro 166: \JP $BG$0U$N9`(B @code{t} $B$KBP$7(B @code{t} > 1
167: \EG For all @code{t} @code{t} > 1.
1.1 noro 168:
169: @item
1.2 noro 170: \JP @code{t}, @code{s}, @code{u} $B$r9`$H$9$k;~(B, @code{t} > @code{s} $B$J$i$P(B @code{tu} > @code{su}
171: \EG For all @code{t}, @code{s}, @code{u} @code{t} > @code{s} implies @code{tu} > @code{su}.
1.1 noro 172: @end enumerate
173:
1.2 noro 174: \BJP
1.1 noro 175: $B$3$N@-<A$rK~$?$9A4=g=x$r9`=g=x$H8F$V(B. $B$3$N=g=x$OJQ?t=g=x(B ($BJQ?t$N%j%9%H(B)
176: $B$H9`=g=x7?(B ($B?t(B, $B%j%9%H$^$?$O9TNs(B) $B$K$h$j;XDj$5$l$k(B.
1.2 noro 177: \E
178: \BEG
179: Such a total order is called a term ordering. A term ordering is specified
180: by a variable ordering (a list of variables) and a type of term ordering
181: (an integer, a list or a matrix).
182: \E
1.1 noro 183:
1.2 noro 184: \BJP
1.1 noro 185: @item $BC19`<0(B (monomial)
186: $B9`$H78?t$N@Q(B.
1.2 noro 187: \E
188: \BEG
189: @item monomial
190: The product of a term and a coefficient.
191: In an @b{Asir} session, it is displayed in the form like
192: \E
1.1 noro 193:
194: @example
195: 2*<<0,1,2,3,4>>
196: @end example
197:
1.2 noro 198: \JP $B$H$$$&7A$GI=<($5$l(B, $B$^$?(B, $B$3$N7A$GF~NO2DG=$G$"$k(B.
199: \EG and also can be input in such a form.
1.1 noro 200:
1.2 noro 201: \BJP
1.1 noro 202: @itemx $BF,C19`<0(B (head monomial)
203: @item $BF,9`(B (head term)
204: @itemx $BF,78?t(B (head coefficient)
205: $BJ,;6I=8=B?9`<0$K$*$1$k3FC19`<0$O(B, $B9`=g=x$K$h$j@0Ns$5$l$k(B. $B$3$N;~=g(B
206: $B=x:GBg$NC19`<0$rF,C19`<0(B, $B$=$l$K8=$l$k9`(B, $B78?t$r$=$l$>$lF,9`(B, $BF,78?t(B
207: $B$H8F$V(B.
1.2 noro 208: \E
209: \BEG
210: @itemx head monomial
211: @item head term
212: @itemx head coefficient
213:
214: Monomials in a distributed polynomial is sorted by a total order.
215: In such representation, we call the monomial that is maximum
216: with respect to the order the head monomial, and its term and coefficient
217: the head term and the head coefficient respectively.
218: \E
1.1 noro 219: @end table
220:
1.2 noro 221: \BJP
1.1 noro 222: @node $B%U%!%$%k$NFI$_9~$_(B,,, $B%0%l%V%J4pDl$N7W;;(B
223: @section $B%U%!%$%k$NFI$_9~$_(B
1.2 noro 224: \E
225: \BEG
226: @node Reading files,,, Groebner basis computation
227: @section Reading files
228: \E
1.1 noro 229:
230: @noindent
1.2 noro 231: \BJP
1.1 noro 232: $B%0%l%V%J4pDl$r7W;;$9$k$?$a$N4pK\E*$JH!?t$O(B @code{dp_gr_main()} $B$*$h$S(B
1.5 noro 233: @code{dp_gr_mod_main()}, @code{dp_gr_f_main()}
234: $B$J$k(B 3 $B$D$NAH$_9~$_H!?t$G$"$k$,(B, $BDL>o$O(B, $B%Q%i%a%?(B
1.1 noro 235: $B@_Dj$J$I$r9T$C$?$N$A$3$l$i$r8F$S=P$9%f!<%6H!?t$rMQ$$$k$N$,JXMx$G$"$k(B.
236: $B$3$l$i$N%f!<%6H!?t$O(B, $B%U%!%$%k(B @samp{gr} $B$r(B @code{load()} $B$K$h$jFI(B
237: $B$_9~$`$3$H$K$h$j;HMQ2DG=$H$J$k(B. @samp{gr} $B$O(B, @b{Asir} $B$NI8=`(B
1.5 noro 238: $B%i%$%V%i%j%G%#%l%/%H%j$KCV$+$l$F$$$k(B.
1.2 noro 239: \E
240: \BEG
1.5 noro 241: Facilities for computing Groebner bases are
242: @code{dp_gr_main()}, @code{dp_gr_mod_main()}and @code{dp_gr_f_main()}.
243: To call these functions,
244: it is necessary to set several parameters correctly and it is convenient
245: to use a set of interface functions provided in the library file
246: @samp{gr}.
1.2 noro 247: The facilities will be ready to use after you load the package by
248: @code{load()}. The package @samp{gr} is placed in the standard library
1.5 noro 249: directory of @b{Asir}.
1.2 noro 250: \E
1.1 noro 251:
252: @example
253: [0] load("gr")$
254: @end example
255:
1.2 noro 256: \BJP
1.1 noro 257: @node $B4pK\E*$JH!?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
258: @section $B4pK\E*$JH!?t(B
1.2 noro 259: \E
260: \BEG
261: @node Fundamental functions,,, Groebner basis computation
262: @section Fundamental functions
263: \E
1.1 noro 264:
265: @noindent
1.2 noro 266: \BJP
1.1 noro 267: @samp{gr} $B$G$O?tB?$/$NH!?t$,Dj5A$5$l$F$$$k$,(B, $BD>@\(B
268: $B%0%l%V%J4pDl$r7W;;$9$k$?$a$N%H%C%W%l%Y%k$O<!$N(B 3 $B$D$G$"$k(B.
269: $B0J2<$G(B, @var{plist} $B$OB?9`<0$N%j%9%H(B, @var{vlist} $B$OJQ?t(B ($BITDj85(B) $B$N%j%9%H(B,
270: @var{order} $B$OJQ?t=g=x7?(B, @var{p} $B$O(B @code{2^27} $BL$K~$NAG?t$G$"$k(B.
1.2 noro 271: \E
272: \BEG
273: There are many functions and options defined in the package @samp{gr}.
274: Usually not so many of them are used. Top level functions for Groebner
275: basis computation are the following three functions.
276:
277: In the following description, @var{plist}, @var{vlist}, @var{order}
278: and @var{p} stand for a list of polynomials, a list of variables
279: (indeterminates), a type of term ordering and a prime less than
280: @code{2^27} respectively.
281: \E
1.1 noro 282:
283: @table @code
284: @item gr(@var{plist},@var{vlist},@var{order})
285:
1.2 noro 286: \BJP
1.1 noro 287: Gebauer-Moeller $B$K$h$k(B useless pair elimination criteria, sugar
288: strategy $B$*$h$S(B Traverso $B$K$h$k(B trace-lifting $B$rMQ$$$?(B Buchberger $B%"%k(B
289: $B%4%j%:%`$K$h$kM-M}?t78?t%0%l%V%J4pDl7W;;H!?t(B. $B0lHL$K$O$3$NH!?t$rMQ$$$k(B.
1.2 noro 290: \E
291: \BEG
292: Function that computes Groebner bases over the rationals. The
293: algorithm is Buchberger algorithm with useless pair elimination
294: criteria by Gebauer-Moeller, sugar strategy and trace-lifting by
295: Traverso. For ordinary computation, this function is used.
296: \E
1.1 noro 297:
298: @item hgr(@var{plist},@var{vlist},@var{order})
299:
1.2 noro 300: \BJP
1.1 noro 301: $BF~NOB?9`<0$r@F<!2=$7$?8e(B @code{gr()} $B$N%0%l%V%J4pDl8uJd@8@.It$K$h$j8u(B
302: $BJd@8@.$7(B, $BHs@F<!2=(B, interreduce $B$7$?$b$N$r(B @code{gr()} $B$N%0%l%V%J4pDl(B
303: $B%A%'%C%/It$G%A%'%C%/$9$k(B. 0 $B<!85%7%9%F%`(B ($B2r$N8D?t$,M-8B8D$NJ}Dx<07O(B)
304: $B$N>l9g(B, sugar strategy $B$,78?tKDD%$r0z$-5/$3$9>l9g$,$"$k(B. $B$3$N$h$&$J>l(B
305: $B9g(B, strategy $B$r@F<!2=$K$h$k(B strategy $B$KCV$-49$($k$3$H$K$h$j78?tKDD%$r(B
306: $BM^@)$9$k$3$H$,$G$-$k>l9g$,B?$$(B.
1.2 noro 307: \E
308: \BEG
309: After homogenizing the input polynomials a candidate of the \gr basis
310: is computed by trace-lifting. Then the candidate is dehomogenized and
311: checked whether it is indeed a Groebner basis of the input. Sugar
312: strategy often causes intermediate coefficient swells. It is
313: empirically known that the combination of homogenization and supresses
314: the swells for such cases.
315: \E
1.1 noro 316:
317: @item gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
318:
1.2 noro 319: \BJP
1.1 noro 320: Gebauer-Moeller $B$K$h$k(B useless pair elimination criteria, sugar
321: strategy $B$*$h$S(B Buchberger $B%"%k%4%j%:%`$K$h$k(B GF(p) $B78?t%0%l%V%J4pDl7W(B
322: $B;;H!?t(B.
1.2 noro 323: \E
324: \BEG
325: Function that computes Groebner bases over GF(@var{p}). The same
326: algorithm as @code{gr()} is used.
327: \E
1.1 noro 328:
329: @end table
330:
1.2 noro 331: \BJP
1.1 noro 332: @node $B7W;;$*$h$SI=<($N@)8f(B,,, $B%0%l%V%J4pDl$N7W;;(B
333: @section $B7W;;$*$h$SI=<($N@)8f(B
1.2 noro 334: \E
335: \BEG
336: @node Controlling Groebner basis computations,,, Groebner basis computation
337: @section Controlling Groebner basis computations
338: \E
1.1 noro 339:
340: @noindent
1.2 noro 341: \BJP
1.1 noro 342: $B%0%l%V%J4pDl$N7W;;$K$*$$$F(B, $B$5$^$6$^$J%Q%i%a%?@_Dj$r9T$&$3$H$K$h$j7W;;(B,
343: $BI=<($r@)8f$9$k$3$H$,$G$-$k(B. $B$3$l$i$O(B, $BAH$_9~$_H!?t(B @code{dp_gr_flags()}
344: $B$K$h$j@_Dj;2>H$9$k$3$H$,$G$-$k(B. $BL50z?t$G(B @code{dp_gr_flags()} $B$r<B9T$9$k(B
345: $B$H(B, $B8=:_@_Dj$5$l$F$$$k%Q%i%a%?$,(B, $BL>A0$HCM$N%j%9%H$GJV$5$l$k(B.
1.2 noro 346: \E
347: \BEG
348: One can cotrol a Groebner basis computation by setting various parameters.
349: These parameters can be set and examined by a built-in function
350: @code{dp_gr_flags()}. Without argument it returns the current settings.
351: \E
1.1 noro 352:
353: @example
354: [100] dp_gr_flags();
1.5 noro 355: [Demand,0,NoSugar,0,NoCriB,0,NoGC,0,NoMC,0,NoRA,0,NoGCD,0,Top,0,
356: ShowMag,1,Print,1,Stat,0,Reverse,0,InterReduce,0,Multiple,0]
1.1 noro 357: [101]
358: @end example
359:
1.2 noro 360: \BJP
1.1 noro 361: $B0J2<$G(B, $B3F%Q%i%a%?$N0UL#$r@bL@$9$k(B. on $B$N>l9g$H$O(B, $B%Q%i%a%?$,(B 0 $B$G$J$$>l9g$r(B
362: $B$$$&(B. $B$3$l$i$N%Q%i%a%?$N=i4|CM$OA4$F(B 0 (off) $B$G$"$k(B.
1.2 noro 363: \E
364: \BEG
365: The return value is a list which contains the names of parameters and their
366: values. The meaning of the parameters are as follows. `on' means that the
367: parameter is not zero.
368: \E
1.1 noro 369:
370: @table @code
371: @item NoSugar
1.2 noro 372: \BJP
1.1 noro 373: on $B$N>l9g(B, sugar strategy $B$NBe$o$j$K(B Buchberger$B$N(B normal strategy $B$,MQ(B
374: $B$$$i$l$k(B.
1.2 noro 375: \E
376: \BEG
377: If `on', Buchberger's normal strategy is used instead of sugar strategy.
378: \E
1.1 noro 379:
380: @item NoCriB
1.2 noro 381: \JP on $B$N>l9g(B, $BITI,MWBP8!=P5,=`$N$&$A(B, $B5,=`(B B $B$rE,MQ$7$J$$(B.
382: \EG If `on', criterion B among the Gebauer-Moeller's criteria is not applied.
1.1 noro 383:
384: @item NoGC
1.2 noro 385: \JP on $B$N>l9g(B, $B7k2L$,%0%l%V%J4pDl$K$J$C$F$$$k$+$I$&$+$N%A%'%C%/$r9T$o$J$$(B.
386: \BEG
387: If `on', the check that a Groebner basis candidate is indeed a Groebner basis,
388: is not executed.
389: \E
1.1 noro 390:
391: @item NoMC
1.2 noro 392: \BJP
1.1 noro 393: on $B$N>l9g(B, $B7k2L$,F~NO%$%G%"%k$HF1Ey$N%$%G%"%k$G$"$k$+$I$&$+$N%A%'%C%/(B
394: $B$r9T$o$J$$(B.
1.2 noro 395: \E
396: \BEG
397: If `on', the check that the resulting polynomials generates the same ideal as
398: the ideal generated by the input, is not executed.
399: \E
1.1 noro 400:
401: @item NoRA
1.2 noro 402: \BJP
1.1 noro 403: on $B$N>l9g(B, $B7k2L$r(B reduced $B%0%l%V%J4pDl$K$9$k$?$a$N(B
404: interreduce $B$r9T$o$J$$(B.
1.2 noro 405: \E
406: \BEG
407: If `on', the interreduction, which makes the Groebner basis reduced, is not
408: executed.
409: \E
1.1 noro 410:
411: @item NoGCD
1.2 noro 412: \BJP
1.1 noro 413: on $B$N>l9g(B, $BM-M}<078?t$N%0%l%V%J4pDl7W;;$K$*$$$F(B, $B@8@.$5$l$?B?9`<0$N(B,
414: $B78?t$N(B content $B$r$H$i$J$$(B.
1.2 noro 415: \E
416: \BEG
417: If `on', content removals are not executed during a Groebner basis computation
418: over a rational function field.
419: \E
1.1 noro 420:
421: @item Top
1.2 noro 422: \JP on $B$N>l9g(B, normal form $B7W;;$K$*$$$FF,9`>C5n$N$_$r9T$&(B.
423: \EG If `on', Only the head term of the polynomial being reduced is reduced.
1.1 noro 424:
1.2 noro 425: @comment @item Interreduce
426: @comment \BJP
427: @comment on $B$N>l9g(B, $BB?9`<0$r@8@.$9$kKh$K(B, $B$=$l$^$G@8@.$5$l$?4pDl$r$=$NB?9`<0$K(B
428: @comment $B$h$k(B normal form $B$GCV$-49$($k(B.
429: @comment \E
430: @comment \BEG
431: @comment If `on', intermediate basis elements are reduced by using a newly generated
432: @comment basis element.
433: @comment \E
1.1 noro 434:
435: @item Reverse
1.2 noro 436: \BJP
1.1 noro 437: on $B$N>l9g(B, normal form $B7W;;$N:]$N(B reducer $B$r(B, $B?7$7$/@8@.$5$l$?$b$N$rM%(B
438: $B@h$7$FA*$V(B.
1.2 noro 439: \E
440: \BEG
441: If `on', the selection strategy of reducer in a normal form computation
442: is such that a newer reducer is used first.
443: \E
1.1 noro 444:
445: @item Print
1.2 noro 446: \JP on $B$N>l9g(B, $B%0%l%V%J4pDl7W;;$NESCf$K$*$1$k$5$^$6$^$J>pJs$rI=<($9$k(B.
447: \BEG
448: If `on', various informations during a Groebner basis computation is
449: displayed.
450: \E
1.1 noro 451:
452: @item Stat
1.2 noro 453: \BJP
1.1 noro 454: on $B$G(B @code{Print} $B$,(B off $B$J$i$P(B, @code{Print} $B$,(B on $B$N$H$-I=<($5(B
455: $B$l$k%G!<%?$NFb(B, $B=87W%G!<%?$N$_$,I=<($5$l$k(B.
1.2 noro 456: \E
457: \BEG
458: If `on', a summary of informations is shown after a Groebner basis
459: computation. Note that the summary is always shown if @code{Print} is `on'.
460: \E
1.1 noro 461:
462: @item ShowMag
1.2 noro 463: \BJP
1.1 noro 464: on $B$G(B @code{Print} $B$,(B on $B$J$i$P(B, $B@8@.$,@8@.$5$l$kKh$K(B, $B$=$NB?9`<0$N(B
465: $B78?t$N%S%C%HD9$NOB$rI=<($7(B, $B:G8e$K(B, $B$=$l$i$NOB$N:GBgCM$rI=<($9$k(B.
1.2 noro 466: \E
467: \BEG
468: If `on' and @code{Print} is `on', the sum of bit length of
469: coefficients of a generated basis element, which we call @var{magnitude},
470: is shown after every normal computation. After comleting the
471: computation the maximal value among the sums is shown.
472: \E
1.1 noro 473:
474: @item Multiple
1.2 noro 475: \BJP
1.1 noro 476: 0 $B$G$J$$@0?t$N;~(B, $BM-M}?t>e$N@55,7A7W;;$K$*$$$F(B, $B78?t$N%S%C%HD9$NOB$,(B
477: @code{Multiple} $BG\$K$J$k$4$H$K78?tA4BN$N(B GCD $B$,7W;;$5$l(B, $B$=$N(B GCD $B$G(B
478: $B3d$C$?B?9`<0$r4JLs$9$k(B. @code{Multiple} $B$,(B 1 $B$J$i$P(B, $B4JLs$9$k$4$H$K(B
479: GCD $B7W;;$,9T$o$l0lHL$K$O8zN($,0-$/$J$k$,(B, @code{Multiple} $B$r(B 2 $BDxEY(B
480: $B$H$9$k$H(B, $B5pBg$J@0?t$,78?t$K8=$l$k>l9g(B, $B8zN($,NI$/$J$k>l9g$,$"$k(B.
1.2 noro 481: \E
482: \BEG
483: If a non-zero integer, in a normal form computation
484: over the rationals, the integer content of the polynomial being
485: reduced is removed when its magnitude becomes @code{Multiple} times
486: larger than a registered value, which is set to the magnitude of the
487: input polynomial. After each content removal the registered value is
488: set to the magnitude of the resulting polynomial. @code{Multiple} is
489: equal to 1, the simiplification is done after every normal form computation.
490: It is empirically known that it is often efficient to set @code{Multiple} to 2
491: for the case where large integers appear during the computation.
492: \E
1.1 noro 493:
494: @item Demand
1.2 noro 495:
496: \BJP
1.1 noro 497: $B@5Ev$J%G%#%l%/%H%jL>(B ($BJ8;zNs(B) $B$rCM$K;}$D$H$-(B, $B@8@.$5$l$?B?9`<0$O%a%b%j(B
498: $BCf$K$*$+$l$:(B, $B$=$N%G%#%l%/%H%jCf$K%P%$%J%j%G!<%?$H$7$FCV$+$l(B, $B$=$NB?9`(B
499: $B<0$rMQ$$$k(B normal form $B7W;;$N:](B, $B<+F0E*$K%a%b%jCf$K%m!<%I$5$l$k(B. $B3FB?(B
500: $B9`<0$O(B, $BFbIt$G$N%$%s%G%C%/%9$r%U%!%$%kL>$K;}$D%U%!%$%k$K3JG<$5$l$k(B.
501: $B$3$3$G;XDj$5$l$?%G%#%l%/%H%j$K=q$+$l$?%U%!%$%k$O<+F0E*$K$O>C5n$5$l$J$$(B
502: $B$?$a(B, $B%f!<%6$,@UG$$r;}$C$F>C5n$9$kI,MW$,$"$k(B.
1.2 noro 503: \E
504: \BEG
505: If the value (a character string) is a valid directory name, then
506: generated basis elements are put in the directory and are loaded on
507: demand during normal form computations. Each elements is saved in the
508: binary form and its name coincides with the index internally used in
509: the computation. These binary files are not removed automatically
510: and one should remove them by hand.
511: \E
1.1 noro 512: @end table
513:
514: @noindent
1.2 noro 515: \JP @code{Print} $B$,(B 0 $B$G$J$$>l9g<!$N$h$&$J%G!<%?$,I=<($5$l$k(B.
516: \EG If @code{Print} is `on', the following informations are shown.
1.1 noro 517:
518: @example
519: [93] gr(cyclic(4),[c0,c1,c2,c3],0)$
520: mod= 99999989, eval = []
521: (0)(0)<<0,2,0,0>>(2,3),nb=2,nab=5,rp=2,sugar=2,mag=4
522: (0)(0)<<0,1,2,0>>(1,2),nb=3,nab=6,rp=2,sugar=3,mag=4
523: (0)(0)<<0,1,1,2>>(0,1),nb=4,nab=7,rp=3,sugar=4,mag=6
524: .
525: (0)(0)<<0,0,3,2>>(5,6),nb=5,nab=8,rp=2,sugar=5,mag=4
526: (0)(0)<<0,1,0,4>>(4,6),nb=6,nab=9,rp=3,sugar=5,mag=4
527: (0)(0)<<0,0,2,4>>(6,8),nb=7,nab=10,rp=4,sugar=6,mag=6
528: ....gb done
529: reduceall
530: .......
531: membercheck
532: (0,0)(0,0)(0,0)(0,0)
533: gbcheck total 8 pairs
534: ........
1.5 noro 535: UP=(0,0)SP=(0,0)SPM=(0,0)NF=(0,0)NFM=(0.010002,0)ZNFM=(0.010002,0)
536: PZ=(0,0)NP=(0,0)MP=(0,0)RA=(0,0)MC=(0,0)GC=(0,0)T=40,B=0 M=8 F=6
537: D=12 ZR=5 NZR=6 Max_mag=6
1.1 noro 538: [94]
539: @end example
540:
541: @noindent
1.2 noro 542: \BJP
1.1 noro 543: $B:G=i$KI=<($5$l$k(B @code{mod}, @code{eval} $B$O(B, trace-lifting $B$GMQ$$$i$l$kK!(B
544: $B$G$"$k(B. @code{mod} $B$OAG?t(B, @code{eval} $B$OM-M}<078?t$N>l9g$KMQ$$$i$l$k(B
545: $B?t$N%j%9%H$G$"$k(B.
1.2 noro 546: \E
547: \BEG
548: In this example @code{mod} and @code{eval} indicate moduli used in
549: trace-lifting. @code{mod} is a prime and @code{eval} is a list of integers
550: used for evaluation when the ground field is a field of rational functions.
551: \E
1.1 noro 552:
553: @noindent
1.2 noro 554: \JP $B7W;;ESCf$GB?9`<0$,@8@.$5$l$kKh$K<!$N7A$N%G!<%?$,I=<($5$l$k(B.
555: \EG The following information is shown after every normal form computation.
1.1 noro 556:
557: @example
558: (TNF)(TCONT)HT(INDEX),nb=NB,nab=NAB,rp=RP,sugar=S,mag=M
559: @end example
560:
561: @noindent
1.2 noro 562: \JP $B$=$l$i$N0UL#$O<!$NDL$j(B.
563: \EG Meaning of each component is as follows.
1.1 noro 564:
565: @table @code
1.2 noro 566: \BJP
1.1 noro 567: @item TNF
1.2 noro 568:
1.1 noro 569: normal form $B7W;;;~4V(B ($BIC(B)
570:
571: @item TCONT
1.2 noro 572:
1.1 noro 573: content $B7W;;;~4V(B ($BIC(B)
574:
575: @item HT
1.2 noro 576:
1.1 noro 577: $B@8@.$5$l$?B?9`<0$NF,9`(B
578:
579: @item INDEX
1.2 noro 580:
1.1 noro 581: S-$BB?9`<0$r9=@.$9$kB?9`<0$N%$%s%G%C%/%9$N%Z%"(B
582:
583: @item NB
1.2 noro 584:
1.1 noro 585: $B8=:_$N(B, $B>iD9@-$r=|$$$?4pDl$N?t(B
586:
587: @item NAB
1.2 noro 588:
1.1 noro 589: $B8=:_$^$G$K@8@.$5$l$?4pDl$N?t(B
590:
591: @item RP
1.2 noro 592:
1.1 noro 593: $B;D$j$N%Z%"$N?t(B
594:
595: @item S
1.2 noro 596:
1.1 noro 597: $B@8@.$5$l$?B?9`<0$N(B sugar $B$NCM(B
598:
599: @item M
1.2 noro 600:
1.1 noro 601: $B@8@.$5$l$?B?9`<0$N78?t$N%S%C%HD9$NOB(B (@code{ShowMag} $B$,(B on $B$N;~$KI=<($5$l$k(B. )
1.2 noro 602: \E
603: \BEG
604: @item TNF
605:
606: CPU time for normal form computation (second)
607:
608: @item TCONT
609:
610: CPU time for content removal(second)
611:
612: @item HT
613:
614: Head term of the generated basis element
615:
616: @item INDEX
617:
618: Pair of indices which corresponds to the reduced S-polynomial
619:
620: @item NB
621:
622: Number of basis elements after removing redundancy
623:
624: @item NAB
625:
626: Number of all the basis elements
627:
628: @item RP
629:
630: Number of remaining pairs
631:
632: @item S
633:
634: Sugar of the generated basis element
635:
636: @item M
637:
638: Magnitude of the genrated basis element (shown if @code{ShowMag} is `on'.)
639: \E
1.1 noro 640: @end table
641:
642: @noindent
1.2 noro 643: \BJP
1.1 noro 644: $B:G8e$K(B, $B=87W%G!<%?$,I=<($5$l$k(B. $B0UL#$O<!$NDL$j(B.
645: ($B;~4V$NI=<($K$*$$$F(B, $B?t;z$,(B 2 $B$D$"$k$b$N$O(B, $B7W;;;~4V$H(B GC $B;~4V$N%Z%"$G$"$k(B.)
1.2 noro 646: \E
647: \BEG
648: The summary of the informations shown after a Groebner basis
649: computation is as follows. If a component shows timings and it
650: contains two numbers, they are a pair of time for computation and time
651: for garbage colection.
652: \E
1.1 noro 653:
654: @table @code
1.2 noro 655: \BJP
1.1 noro 656: @item UP
1.2 noro 657:
1.1 noro 658: $B%Z%"$N%j%9%H$NA`:n$K$+$+$C$?;~4V(B
659:
660: @item SP
1.2 noro 661:
1.1 noro 662: $BM-M}?t>e$N(B S-$BB?9`<07W;;;~4V(B
663:
664: @item SPM
1.2 noro 665:
1.1 noro 666: $BM-8BBN>e$N(B S-$BB?9`<07W;;;~4V(B
667:
668: @item NF
1.2 noro 669:
1.1 noro 670: $BM-M}?t>e$N(B normal form $B7W;;;~4V(B
671:
672: @item NFM
1.2 noro 673:
1.1 noro 674: $BM-8BBN>e$N(B normal form $B7W;;;~4V(B
675:
676: @item ZNFM
1.2 noro 677:
1.1 noro 678: @code{NFM} $B$NFb(B, 0 $B$X$N(B reduction $B$K$+$+$C$?;~4V(B
679:
680: @item PZ
1.2 noro 681:
1.1 noro 682: content $B7W;;;~4V(B
683:
684: @item NP
1.2 noro 685:
1.1 noro 686: $BM-M}?t78?tB?9`<0$N78?t$KBP$9$k>jM>1i;;$N7W;;;~4V(B
687:
688: @item MP
1.2 noro 689:
1.1 noro 690: S-$BB?9`<0$r@8@.$9$k%Z%"$NA*Br$K$+$+$C$?;~4V(B
691:
692: @item RA
1.2 noro 693:
1.1 noro 694: interreduce $B7W;;;~4V(B
695:
696: @item MC
1.2 noro 697:
1.1 noro 698: trace-lifting $B$K$*$1$k(B, $BF~NOB?9`<0$N%a%s%P%7%C%W7W;;;~4V(B
699:
700: @item GC
1.2 noro 701:
1.1 noro 702: $B7k2L$N%0%l%V%J4pDl8uJd$N%0%l%V%J4pDl%A%'%C%/;~4V(B
703:
704: @item T
1.2 noro 705:
1.1 noro 706: $B@8@.$5$l$?%Z%"$N?t(B
707:
708: @item B, M, F, D
1.2 noro 709:
1.1 noro 710: $B3F(B criterion $B$K$h$j=|$+$l$?%Z%"$N?t(B
711:
712: @item ZR
1.2 noro 713:
1.1 noro 714: 0 $B$K(B reduce $B$5$l$?%Z%"$N?t(B
715:
716: @item NZR
1.2 noro 717:
1.1 noro 718: 0 $B$G$J$$B?9`<0$K(B reduce $B$5$l$?%Z%"$N?t(B
719:
720: @item Max_mag
1.2 noro 721:
1.1 noro 722: $B@8@.$5$l$?B?9`<0$N(B, $B78?t$N%S%C%HD9$NOB$N:GBgCM(B
1.2 noro 723: \E
724: \BEG
725: @item UP
726:
727: Time to manipulate the list of critical pairs
728:
729: @item SP
730:
731: Time to compute S-polynomials over the rationals
732:
733: @item SPM
734:
735: Time to compute S-polynomials over a finite field
736:
737: @item NF
738:
739: Time to compute normal forms over the rationals
740:
741: @item NFM
742:
743: Time to compute normal forms over a finite field
744:
745: @item ZNFM
746:
747: Time for zero reductions in @code{NFM}
748:
749: @item PZ
750:
751: Time to remove integer contets
752:
753: @item NP
754:
755: Time to compute remainders for coefficients of polynomials with coeffieints
756: in the rationals
757:
758: @item MP
759:
760: Time to select pairs from which S-polynomials are computed
761:
762: @item RA
763:
764: Time to interreduce the Groebner basis candidate
765:
766: @item MC
1.1 noro 767:
1.2 noro 768: Time to check that each input polynomial is a member of the ideal
769: generated by the Groebner basis candidate.
770:
771: @item GC
772:
773: Time to check that the Groebner basis candidate is a Groebner basis
774:
775: @item T
776:
777: Number of critical pairs generated
778:
779: @item B, M, F, D
780:
781: Number of critical pairs removed by using each criterion
782:
783: @item ZR
784:
785: Number of S-polynomials reduced to 0
786:
787: @item NZR
788:
789: Number of S-polynomials reduced to non-zero results
790:
791: @item Max_mag
792:
793: Maximal magnitude among all the generated polynomials
794: \E
1.1 noro 795: @end table
796:
1.2 noro 797: \BJP
1.1 noro 798: @node $B9`=g=x$N@_Dj(B,,, $B%0%l%V%J4pDl$N7W;;(B
799: @section $B9`=g=x$N@_Dj(B
1.2 noro 800: \E
801: \BEG
802: @node Setting term orderings,,, Groebner basis computation
803: @section Setting term orderings
804: \E
1.1 noro 805:
806: @noindent
1.2 noro 807: \BJP
1.1 noro 808: $B9`$OFbIt$G$O(B, $B3FJQ?t$K4X$9$k;X?t$r@.J,$H$9$k@0?t%Y%/%H%k$H$7$FI=8=$5$l(B
809: $B$k(B. $BB?9`<0$rJ,;6I=8=B?9`<0$KJQ49$9$k:](B, $B3FJQ?t$,$I$N@.J,$KBP1~$9$k$+$r(B
810: $B;XDj$9$k$N$,(B, $BJQ?t%j%9%H$G$"$k(B. $B$5$i$K(B, $B$=$l$i@0?t%Y%/%H%k$NA4=g=x$r(B
811: $B;XDj$9$k$N$,9`=g=x$N7?$G$"$k(B. $B9`=g=x7?$O(B, $B?t(B, $B?t$N%j%9%H$"$k$$$O(B
812: $B9TNs$GI=8=$5$l$k(B.
1.2 noro 813: \E
814: \BEG
815: A term is internally represented as an integer vector whose components
816: are exponents with respect to variables. A variable list specifies the
817: correspondences between variables and components. A type of term ordering
818: specifies a total order for integer vectors. A type of term ordering is
819: represented by an integer, a list of integer or matrices.
820: \E
1.1 noro 821:
822: @noindent
1.2 noro 823: \JP $B4pK\E*$J9`=g=x7?$H$7$F<!$N(B 3 $B$D$,$"$k(B.
824: \EG There are following three fundamental types.
1.1 noro 825:
826: @table @code
1.2 noro 827: \JP @item 0 (DegRevLex; @b{$BA4<!?t5U<-=q<0=g=x(B})
828: \EG @item 0 (DegRevLex; @b{total degree reverse lexicographic ordering})
1.1 noro 829:
1.2 noro 830: \BJP
1.1 noro 831: $B0lHL$K(B, $B$3$N=g=x$K$h$k%0%l%V%J4pDl7W;;$,:G$b9bB.$G$"$k(B. $B$?$@$7(B,
832: $BJ}Dx<0$r2r$/$H$$$&L\E*$KMQ$$$k$3$H$O(B, $B0lHL$K$O$G$-$J$$(B. $B$3$N(B
833: $B=g=x$K$h$k%0%l%V%J4pDl$O(B, $B2r$N8D?t$N7W;;(B, $B%$%G%"%k$N%a%s%P%7%C%W$d(B,
834: $BB>$NJQ?t=g=x$X$N4pDlJQ49$N$?$a$N%=!<%9$H$7$FMQ$$$i$l$k(B.
1.2 noro 835: \E
836: \BEG
837: In general, computation by this ordering shows the fastest speed
838: in most Groebner basis computations.
839: However, for the purpose to solve polynomial equations, this type
840: of ordering is, in general, not so suitable.
841: The Groebner bases obtained by this ordering is used for computing
842: the number of solutions, solving ideal membership problem and seeds
843: for conversion to other Groebner bases under different ordering.
844: \E
1.1 noro 845:
1.2 noro 846: \JP @item 1 (DegLex; @b{$BA4<!?t<-=q<0=g=x(B})
847: \EG @item 1 (DegLex; @b{total degree lexicographic ordering})
1.1 noro 848:
1.2 noro 849: \BJP
1.1 noro 850: $B$3$N=g=x$b(B, $B<-=q<0=g=x$KHf$Y$F9bB.$K%0%l%V%J4pDl$r5a$a$k$3$H$,$G$-$k$,(B,
851: @code{DegRevLex} $B$HF1MMD>@\$=$N7k2L$rMQ$$$k$3$H$O:$Fq$G$"$k(B. $B$7$+$7(B,
852: $B<-=q<0=g=x$N%0%l%V%J4pDl$r5a$a$k:]$K(B, $B@F<!2=8e$K$3$N=g=x$G%0%l%V%J4pDl(B
853: $B$r5a$a$F$$$k(B.
1.2 noro 854: \E
855: \BEG
856: By this type term ordering, Groebner bases are obtained fairly faster
857: than Lex (lexicographic) ordering, too.
858: Alike the @code{DegRevLex} ordering, the result, in general, cannot directly
859: be used for solving polynomial equations.
860: It is used, however, in such a way
861: that a Groebner basis is computed in this ordering after homogenization
862: to obtain the final lexicographic Groebner basis.
863: \E
1.1 noro 864:
1.2 noro 865: \JP @item 2 (Lex; @b{$B<-=q<0=g=x(B})
866: \EG @item 2 (Lex; @b{lexicographic ordering})
1.1 noro 867:
1.2 noro 868: \BJP
1.1 noro 869: $B$3$N=g=x$K$h$k%0%l%V%J4pDl$O(B, $BJ}Dx<0$r2r$/>l9g$K:GE,$N7A$N4pDl$rM?$($k$,(B
870: $B7W;;;~4V$,$+$+$j2a$.$k$N$,FqE@$G$"$k(B. $BFC$K(B, $B2r$,M-8B8D$N>l9g(B, $B7k2L$N(B
871: $B78?t$,6K$a$FD9Bg$JB?G\D9?t$K$J$k>l9g$,B?$$(B. $B$3$N>l9g(B, @code{gr()},
872: @code{hgr()} $B$K$h$k7W;;$,6K$a$FM-8z$K$J$k>l9g$,B?$$(B.
1.2 noro 873: \E
874: \BEG
875: Groebner bases computed by this ordering give the most convenient
876: Groebner bases for solving the polynomial equations.
877: The only and serious shortcoming is the enormously long computation
878: time.
879: It is often observed that the number coefficients of the result becomes
880: very very long integers, especially if the ideal is 0-dimensional.
881: For such a case, it is empirically true for many cases
882: that i.e., computation by
883: @code{gr()} and/or @code{hgr()} may be quite effective.
884: \E
1.1 noro 885: @end table
886:
887: @noindent
1.2 noro 888: \BJP
1.1 noro 889: $B$3$l$i$rAH$_9g$o$;$F%j%9%H$G;XDj$9$k$3$H$K$h$j(B, $BMM!9$J>C5n=g=x$,;XDj$G$-$k(B.
890: $B$3$l$O(B,
1.2 noro 891: \E
892: \BEG
893: By combining these fundamental orderingl into a list, one can make
894: various term ordering called elimination orderings.
895: \E
1.1 noro 896:
897: @code{[[O1,L1],[O2,L2],...]}
898:
899: @noindent
1.2 noro 900: \BJP
1.1 noro 901: $B$G;XDj$5$l$k(B. @code{Oi} $B$O(B 0, 1, 2 $B$N$$$:$l$+$G(B, @code{Li} $B$OJQ?t$N8D(B
902: $B?t$rI=$9(B. $B$3$N;XDj$O(B, $BJQ?t$r@hF,$+$i(B @code{L1}, @code{L2} , ...$B8D(B
903: $B$:$D$NAH$KJ,$1(B, $B$=$l$>$l$NJQ?t$K4X$7(B, $B=g$K(B @code{O1}, @code{O2},
904: ...$B$N9`=g=x7?$GBg>.$,7hDj$9$k$^$GHf3S$9$k$3$H$r0UL#$9$k(B. $B$3$N7?$N(B
905: $B=g=x$O0lHL$K>C5n=g=x$H8F$P$l$k(B.
1.2 noro 906: \E
907: \BEG
908: In this example @code{Oi} indicates 0, 1 or 2 and @code{Li} indicates
909: the number of variables subject to the correspoinding orderings.
910: This specification means the following.
911:
912: The variable list is separated into sub lists from left to right where
913: the @code{i}-th list contains @code{Li} members and it corresponds to
914: the ordering of type @code{Oi}. The result of a comparison is equal
915: to that for the leftmost different sub components. This type of ordering
916: is called an elimination ordering.
917: \E
1.1 noro 918:
919: @noindent
1.2 noro 920: \BJP
1.1 noro 921: $B$5$i$K(B, $B9TNs$K$h$j9`=g=x$r;XDj$9$k$3$H$,$G$-$k(B. $B0lHL$K(B, @code{n} $B9T(B
922: @code{m} $BNs$N<B?t9TNs(B @code{M} $B$,<!$N@-<A$r;}$D$H$9$k(B.
1.2 noro 923: \E
924: \BEG
925: Furthermore one can specify a term ordering by a matix.
926: Suppose that a real @code{n}, @code{m} matrix @code{M} has the
927: following properties.
928: \E
1.1 noro 929:
930: @enumerate
931: @item
1.2 noro 932: \JP $BD9$5(B @code{m} $B$N@0?t%Y%/%H%k(B @code{v} $B$KBP$7(B @code{Mv=0} $B$H(B @code{v=0} $B$OF1CM(B.
933: \BEG
934: For all integer verctors @code{v} of length @code{m} @code{Mv=0} is equivalent
935: to @code{v=0}.
936: \E
1.1 noro 937:
938: @item
1.2 noro 939: \BJP
1.1 noro 940: $BHsIi@.J,$r;}$DD9$5(B @code{m} $B$N(B 0 $B$G$J$$@0?t%Y%/%H%k(B @code{v} $B$KBP$7(B,
941: @code{Mv} $B$N(B 0 $B$G$J$$:G=i$N@.J,$OHsIi(B.
1.2 noro 942: \E
943: \BEG
944: For all non-negative integer vectors @code{v} the first non-zero component
945: of @code{Mv} is non-negative.
946: \E
1.1 noro 947: @end enumerate
948:
949: @noindent
1.2 noro 950: \BJP
1.1 noro 951: $B$3$N;~(B, 2 $B$D$N%Y%/%H%k(B @code{t}, @code{s} $B$KBP$7(B,
952: @code{t>s} $B$r(B, @code{M(t-s)} $B$N(B 0 $B$G$J$$:G=i$N@.J,$,HsIi(B,
953: $B$GDj5A$9$k$3$H$K$h$j9`=g=x$,Dj5A$G$-$k(B.
1.2 noro 954: \E
955: \BEG
956: Then we can define a term ordering such that, for two vectors
957: @code{t}, @code{s}, @code{t>s} means that the first non-zero component
958: of @code{M(t-s)} is non-negative.
959: \E
1.1 noro 960:
961: @noindent
1.2 noro 962: \BJP
1.1 noro 963: $B9`=g=x7?$O(B, @code{gr()} $B$J$I$N0z?t$H$7$F;XDj$5$l$kB>(B, $BAH$_9~$_H!?t(B
964: @code{dp_ord()} $B$G;XDj$5$l(B, $B$5$^$6$^$JH!?t$N<B9T$N:]$K;2>H$5$l$k(B.
1.2 noro 965: \E
966: \BEG
967: Types of term orderings are used as arguments of functions such as
968: @code{gr()}. It is also set internally by @code{dp_ord()} and is used
969: during executions of various functions.
970: \E
1.1 noro 971:
972: @noindent
1.2 noro 973: \BJP
1.1 noro 974: $B$3$l$i$N=g=x$N6qBNE*$JDj5A$*$h$S%0%l%V%J4pDl$K4X$9$k99$K>\$7$$2r@b$O(B
975: @code{[Becker,Weispfenning]} $B$J$I$r;2>H$N$3$H(B.
1.2 noro 976: \E
977: \BEG
978: For concrete definitions of term ordering and more information
979: about Groebner basis, refer to, for example, the book
980: @code{[Becker,Weispfenning]}.
981: \E
1.1 noro 982:
983: @noindent
1.2 noro 984: \JP $B9`=g=x7?$N@_Dj$NB>$K(B, $BJQ?t$N=g=x<+BN$b7W;;;~4V$KBg$-$J1F6A$rM?$($k(B.
985: \BEG
986: Note that the variable ordering have strong effects on the computation
987: time as well as the choice of types of term orderings.
988: \E
1.1 noro 989:
990: @example
991: [90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
992: [91] gr(B,[x,y,z,t],2);
993: [x^2-2*y^7+(-41*t^2-13*t-1)*y^2+(2*t^17-12*t^14+42*t^12+30*t^11-168*t^9
994: -40*t^8+70*t^7+252*t^6+30*t^5-140*t^4-168*t^3+2*t^2-12*t+16)*z^2*y
995: +(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
996: -167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
1.5 noro 997: (y+t^2*z^2)*x+y^7+(20*t^2+6*t+1)*y^2+(-t^17+6*t^14-21*t^12-15*t^11
998: +84*t^9+20*t^8-35*t^7-126*t^6-15*t^5+70*t^4+84*t^3-t^2+5*t-9)*z^2*y
999: +(6*t^16-36*t^13+14*t^11+90*t^10-56*t^8-120*t^7-14*t^6+64*t^5+84*t^4
1000: +27*t^3-16*t^2-30*t+7)*z^4,
1001: (t^3-1)*x-y^6+(-6*t^13+24*t^10-20*t^8-36*t^7+40*t^5+24*t^4-6*t^3-20*t^2
1002: -6*t-1)*y+(t^17-6*t^14+9*t^12+15*t^11-36*t^9-20*t^8-5*t^7+54*t^6+15*t^5
1003: +10*t^4-36*t^3-11*t^2-5*t+9)*z^2,
1.1 noro 1004: -y^8-8*t*y^3+16*z^2*y^2+(-8*t^16+48*t^13-56*t^11-120*t^10+224*t^8+160*t^7
1.5 noro 1005: -56*t^6-336*t^5-112*t^4+112*t^3+224*t^2+24*t-56)*z^4*y+(t^24-8*t^21
1006: +20*t^19+28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11
1007: -400*t^10-84*t^9+84*t^8+268*t^7+84*t^6-56*t^5-63*t^4-36*t^3+46*t^2
1008: -12*t+1)*z,2*t*y^5+z*y^2+(-2*t^11+8*t^8-20*t^6-12*t^5+40*t^3+8*t^2
1009: -10*t-20)*z^3*y+8*t^14-32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t,
1.1 noro 1010: -z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
1.5 noro 1011: 2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y
1012: +(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-t)*z,
1.1 noro 1013: z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
1014: -t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
1.5 noro 1015: -t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,z^5-t^4]
1.1 noro 1016: [93] gr(B,[t,z,y,x],2);
1017: [x^10-t,x^8-z,x^31-x^6-x-y]
1018: @end example
1019:
1020: @noindent
1.2 noro 1021: \BJP
1.1 noro 1022: $BJQ?t=g=x(B @code{[x,y,z,t]} $B$K$*$1$k%0%l%V%J4pDl$O(B, $B4pDl$N?t$bB?$/(B, $B$=$l$>$l$N(B
1023: $B<0$bBg$-$$(B. $B$7$+$7(B, $B=g=x(B @code{[t,z,y,x]} $B$K$b$H$G$O(B, @code{B} $B$,$9$G$K(B
1024: $B%0%l%V%J4pDl$H$J$C$F$$$k(B. $BBg;(GD$K$$$($P(B, $B<-=q<0=g=x$G%0%l%V%J4pDl$r5a$a$k(B
1025: $B$3$H$O(B, $B:8B&$N(B ($B=g=x$N9b$$(B) $BJQ?t$r(B, $B1&B&$N(B ($B=g=x$NDc$$(B) $BJQ?t$G=q$-I=$9(B
1026: $B$3$H$G$"$j(B, $B$3$NNc$N>l9g$O(B, @code{t}, @code{z}, @code{y} $B$,4{$K(B
1027: @code{x} $B$GI=$5$l$F$$$k$3$H$+$i$3$N$h$&$J6KC<$J7k2L$H$J$C$?$o$1$G$"$k(B.
1028: $B<B:]$K8=$l$k7W;;$K$*$$$F$O(B, $B$3$N$h$&$KA*$V$Y$-JQ?t=g=x$,L@$i$+$G$"$k(B
1029: $B$3$H$O>/$J$/(B, $B;n9T:x8m$,I,MW$J>l9g$b$"$k(B.
1.2 noro 1030: \E
1031: \BEG
1032: As you see in the above example, the Groebner base under variable
1033: ordering @code{[x,y,z,t]} has a lot of bases and each base itself is
1034: large. Under variable ordering @code{[t,z,y,x]}, however, @code{B} itself
1035: is already the Groebner basis.
1036: Roughly speaking, to obtain a Groebner base under the lexicographic
1037: ordering is to express the variables on the left (having higher order)
1038: in terms of variables on the right (having lower order).
1039: In the example, variables @code{t}, @code{z}, and @code{y} are already
1040: expressed by variable @code{x}, and the above explanation justifies
1041: such a drastic experimental results.
1042: In practice, however, optimum ordering for variables may not known
1043: beforehand, and some heuristic trial may be inevitable.
1044: \E
1.1 noro 1045:
1.2 noro 1046: \BJP
1.1 noro 1047: @node $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B,,, $B%0%l%V%J4pDl$N7W;;(B
1048: @section $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B
1.2 noro 1049: \E
1050: \BEG
1051: @node Groebner basis computation with rational function coefficients,,, Groebner basis computation
1052: @section Groebner basis computation with rational function coefficients
1053: \E
1.1 noro 1054:
1055: @noindent
1.2 noro 1056: \BJP
1.1 noro 1057: @code{gr()} $B$J$I$N%H%C%W%l%Y%kH!?t$O(B, $B$$$:$l$b(B, $BF~NOB?9`<0%j%9%H$K(B
1058: $B8=$l$kJQ?t(B ($BITDj85(B) $B$H(B, $BJQ?t%j%9%H$K8=$l$kJQ?t$rHf3S$7$F(B, $BJQ?t%j%9%H$K(B
1059: $B$J$$JQ?t$,F~NOB?9`<0$K8=$l$F$$$k>l9g$K$O(B, $B<+F0E*$K(B, $B$=$NJQ?t$r(B, $B78?t(B
1060: $BBN$N85$H$7$F07$&(B.
1.2 noro 1061: \E
1062: \BEG
1063: Such variables that appear within the input polynomials but
1064: not appearing in the input variable list are automatically treated
1065: as elements in the coefficient field
1066: by top level functions, such as @code{gr()}.
1067: \E
1.1 noro 1068:
1069: @example
1070: [64] gr([a*x+b*y-c,d*x+e*y-f],[x,y],2);
1071: [(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]
1072: @end example
1073:
1074: @noindent
1.2 noro 1075: \BJP
1.1 noro 1076: $B$3$NNc$G$O(B, @code{a}, @code{b}, @code{c}, @code{d} $B$,78?tBN$N85$H$7$F(B
1077: $B07$o$l$k(B. $B$9$J$o$A(B, $BM-M}H!?tBN(B
1078: @b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}) $B>e$N(B 2 $BJQ?tB?9`<04D(B
1079: @b{F}[@code{x},@code{y}] $B$K$*$1$k%0%l%V%J4pDl$r5a$a$k$3$H$K$J$k(B.
1080: $BCm0U$9$Y$-$3$H$O(B,
1081: $B78?t$,BN$H$7$F07$o$l$F$$$k$3$H$G$"$k(B. $B$9$J$o$A(B, $B78?t$N4V$KB?9`<0(B
1082: $B$H$7$F$N6&DL0x;R$,$"$C$?>l9g$K$O(B, $B7k2L$+$i$=$N0x;R$O=|$+$l$F$$$k(B
1083: $B$?$a(B, $BM-M}?tBN>e$NB?9`<04D>e$NLdBj$H$7$F9M$($?>l9g$N7k2L$H$O0lHL(B
1084: $B$K$O0[$J$k(B. $B$^$?(B, $B<g$H$7$F7W;;8zN(>e$NLdBj$N$?$a(B, $BJ,;6I=8=B?9`<0(B
1085: $B$N78?t$H$7$F<B:]$K5v$5$l$k$N$OB?9`<0$^$G$G$"$k(B. $B$9$J$o$A(B, $BJ,Jl$r(B
1086: $B;}$DM-M}<0$OJ,;6I=8=B?9`<0$N78?t$H$7$F$O5v$5$l$J$$(B.
1.2 noro 1087: \E
1088: \BEG
1089: In this example, variables @code{a}, @code{b}, @code{c}, and @code{d}
1090: are treated as elements in the coefficient field.
1091: In this case, a Groebner basis is computed
1092: on a bi-variate polynomial ring
1093: @b{F}[@code{x},@code{y}]
1094: over rational function field
1095: @b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}).
1096: Notice that coefficients are considered as a member in a field.
1097: As a consequence, polynomial factors common to the coefficients
1098: are removed so that the result, in general, is different from
1099: the result that would be obtained when the problem is considered
1100: as a computation of Groebner basis over a polynomial ring
1101: with rational function coefficients.
1102: And note that coefficients of a distributed polynomial are limited
1103: to numbers and polynomials because of efficiency.
1104: \E
1.1 noro 1105:
1.2 noro 1106: \BJP
1.1 noro 1107: @node $B4pDlJQ49(B,,, $B%0%l%V%J4pDl$N7W;;(B
1108: @section $B4pDlJQ49(B
1.2 noro 1109: \E
1110: \BEG
1111: @node Change of ordering,,, Groebner basis computation
1112: @section Change of orderng
1113: \E
1.1 noro 1114:
1115: @noindent
1.2 noro 1116: \BJP
1.1 noro 1117: $B<-=q<0=g=x$N%0%l%V%J4pDl$r5a$a$k>l9g(B, $BD>@\(B @code{gr()} $B$J$I$r5/F0$9$k(B
1118: $B$h$j(B, $B0lC6B>$N=g=x(B ($BNc$($PA4<!?t5U<-=q<0=g=x(B) $B$N%0%l%V%J4pDl$r7W;;$7$F(B,
1119: $B$=$l$rF~NO$H$7$F<-=q<0=g=x$N%0%l%V%J4pDl$r7W;;$9$kJ}$,8zN($,$h$$>l9g(B
1120: $B$,$"$k(B. $B$^$?(B, $BF~NO$,2?$i$+$N=g=x$G$N%0%l%V%J4pDl$K$J$C$F$$$k>l9g(B, $B4pDl(B
1121: $BJQ49$H8F$P$l$kJ}K!$K$h$j(B, Buchberger $B%"%k%4%j%:%`$K$h$i$:$K8zN(NI$/(B
1122: $B<-=q<0=g=x$N%0%l%V%J4pDl$,7W;;$G$-$k>l9g$,$"$k(B. $B$3$N$h$&$JL\E*$N$?$a$N(B
1123: $BH!?t$,(B, $B%f!<%6Dj5AH!?t$H$7$F(B @samp{gr} $B$K$$$/$D$+Dj5A$5$l$F$$$k(B.
1124: $B0J2<$N(B 2 $B$D$NH!?t$O(B, $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B @var{order} $B$G(B
1125: $B4{$K%0%l%V%J4pDl$H$J$C$F$$$kB?9`<0%j%9%H(B @var{gbase} $B$r(B, $BJQ?t=g=x(B
1126: @var{vlist2} $B$K$*$1$k<-=q<0=g=x$N%0%l%V%J4pDl$KJQ49$9$kH!?t$G$"$k(B.
1.2 noro 1127: \E
1128: \BEG
1129: When we compute a lex order Groebner basis, it is often efficient to
1130: compute it via Groebner basis with respect to another order such as
1131: degree reverse lex order, rather than to compute it directory by
1132: @code{gr()} etc. If we know that an input is a Groebner basis with
1133: respect to an order, we can apply special methods called change of
1134: ordering for a Groebner basis computation with respect to another
1135: order, without using Buchberger algorithm. The following two functions
1136: are ones for change of ordering such that they convert a Groebner
1137: basis @var{gbase} with respect to the variable order @var{vlist1} and
1138: the order type @var{order} into a lex Groebner basis with respect
1139: to the variable order @var{vlist2}.
1140: \E
1.1 noro 1141:
1142: @table @code
1143: @item tolex(@var{gbase},@var{vlist1},@var{order},@var{vlist2})
1144:
1.2 noro 1145: \BJP
1.1 noro 1146: $B$3$NH!?t$O(B, @var{gbase} $B$,M-M}?tBN>e$N%7%9%F%`$N>l9g$K$N$_;HMQ2DG=$G$"$k(B.
1147: $B$3$NH!?t$O(B, $B<-=q<0=g=x$N%0%l%V%J4pDl$r(B, $BM-8BBN>e$G7W;;$5$l$?%0%l%V%J4pDl(B
1148: $B$r?w7?$H$7$F(B, $BL$Dj78?tK!$*$h$S(B Hensel $B9=@.$K$h$j5a$a$k$b$N$G$"$k(B.
1.2 noro 1149: \E
1150: \BEG
1151: This function can be used only when @var{gbase} is an ideal over the
1152: rationals. The input @var{gbase} must be a Groebner basis with respect
1153: to the variable order @var{vlist1} and the order type @var{order}. Moreover
1154: the ideal generated by @var{gbase} must be zero-dimensional.
1155: This computes the lex Groebner basis of @var{gbase}
1156: by using the modular change of ordering algorithm. The algorithm first
1157: computes the lex Groebner basis over a finite field. Then each element
1158: in the lex Groebner basis over the rationals is computed with undetermined
1159: coefficient method and linear equation solving by Hensel lifting.
1160: \E
1.1 noro 1161:
1162: @item tolex_tl(@var{gbase},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1163:
1.2 noro 1164: \BJP
1.1 noro 1165: $B$3$NH!?t$O(B, $B<-=q<0=g=x$N%0%l%V%J4pDl$r(B Buchberger $B%"%k%4%j%:%`$K$h$j5a(B
1166: $B$a$k$b$N$G$"$k$,(B, $BF~NO$,$"$k=g=x$K$*$1$k%0%l%V%J4pDl$G$"$k>l9g$N(B
1167: trace-lifting$B$K$*$1$k%0%l%V%J4pDl8uJd$NF,9`(B, $BF,78?t$N@-<A$rMxMQ$7$F(B,
1168: $B:G=*E*$J%0%l%V%J4pDl%A%'%C%/(B, $B%$%G%"%k%a%s%P%7%C%W%A%'%C%/$r>JN,$7$F$$(B
1169: $B$k$?$a(B, $BC1$K(BBuchberger $B%"%k%4%j%:%`$r7+$jJV$9$h$j8zN($h$/7W;;$G$-$k(B.
1170: $B99$K(B, $BF~NO$,(B 0 $B<!85%7%9%F%`$N>l9g(B, $B<+F0E*$K$b$&(B 1 $B$D$NCf4VE*$J9`=g=x$r(B
1171: $B7PM3$7$F<-=q<0=g=x$N%0%l%V%J4pDl$r7W;;$9$k(B. $BB?$/$N>l9g(B, $B$3$NJ}K!$O(B,
1172: $BD>@\<-=q<0=g=x$N7W;;$r9T$&$h$j8zN($,$h$$(B. ($B$b$A$m$sNc30$"$j(B. )
1173: $B0z?t(B @var{homo} $B$,(B 0 $B$G$J$$;~(B, @code{hgr()} $B$HF1MM$K@F<!2=$r7PM3$7$F(B
1174: $B7W;;$r9T$&(B.
1.2 noro 1175: \E
1176: \BEG
1177: This function computes the lex Groebner basis of @var{gbase}. The
1178: input @var{gbase} must be a Groebner basis with respect to the
1179: variable order @var{vlist1} and the order type @var{order}.
1180: Buchberger algorithm with trace lifting is used to compute the lex
1181: Groebner basis, however the Groebner basis check and the ideal
1182: membership check can be omitted by using several properties derived
1183: from the fact that the input is a Groebner basis. So it is more
1184: efficient than simple repetition of Buchberger algorithm. If the input
1185: is zero-dimensional, this function inserts automatically a computation
1186: of Groebner basis with respect to an elimination order, which makes
1187: the whole computation more efficient for many cases. If @var{homo} is
1188: not equal to 0, homogenization is used in each step.
1189: \E
1.1 noro 1190: @end table
1191:
1192: @noindent
1.2 noro 1193: \BJP
1.1 noro 1194: $B$=$NB>(B, 0 $B<!85%7%9%F%`$KBP$7(B, $BM?$($i$l$?B?9`<0$N:G>.B?9`<0$r5a$a$k(B
1195: $BH!?t(B, 0 $B<!85%7%9%F%`$N2r$r(B, $B$h$j%3%s%Q%/%H$KI=8=$9$k$?$a$NH!?t$J$I$,(B
1196: @samp{gr} $B$GDj5A$5$l$F$$$k(B. $B$3$l$i$K$D$$$F$O8D!9$NH!?t$N@bL@$r;2>H$N$3$H(B.
1.2 noro 1197: \E
1198: \BEG
1199: For zero-dimensional systems, there are several fuctions to
1200: compute the minimal polynomial of a polynomial and or a more compact
1201: representation for zeros of the system. They are all defined in @samp{gr}.
1202: Refer to the sections for each functions.
1203: \E
1.1 noro 1204:
1.2 noro 1205: \BJP
1.6 ! noro 1206: @node Weyl $BBe?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
! 1207: @section Weyl $BBe?t(B
! 1208: \E
! 1209: \BEG
! 1210: @node Weyl algebra,,, Groebner basis computation
! 1211: @section Weyl algebra
! 1212: \E
! 1213:
! 1214: @noindent
! 1215:
! 1216: \BJP
! 1217: $B$3$l$^$G$O(B, $BDL>o$N2D49$JB?9`<04D$K$*$1$k%0%l%V%J4pDl7W;;$K$D$$$F(B
! 1218: $B=R$Y$F$-$?$,(B, $B%0%l%V%J4pDl$NM}O@$O(B, $B$"$k>r7o$rK~$?$9Hs2D49$J(B
! 1219: $B4D$K$b3HD%$G$-$k(B. $B$3$N$h$&$J4D$NCf$G(B, $B1~MQ>e$b=EMW$J(B,
! 1220: Weyl $BBe?t(B, $B$9$J$o$AB?9`<04D>e$NHyJ,:nMQAG4D$N1i;;$*$h$S(B
! 1221: $B%0%l%V%J4pDl7W;;$,(B Risa/Asir $B$K<BAu$5$l$F$$$k(B.
! 1222:
! 1223: $BBN(B @code{K} $B>e$N(B @code{n} $B<!85(B Weyl $BBe?t(B
! 1224: @code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} $B$O(B
! 1225: \E
! 1226:
! 1227: \BEG
! 1228: So far we have explained Groebner basis computation in
! 1229: commutative polynomial rings. However Groebner basis can be
! 1230: considered in more general non-commutative rings.
! 1231: Weyl algebra is one of such rings and
! 1232: Risa/Asir implements fundamental operations
! 1233: in Weyl algebra and Groebner basis computation in Weyl algebra.
! 1234:
! 1235: The @code{n} dimensional Weyl algebra over a field @code{K},
! 1236: @code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} is a non-commutative
! 1237: algebra which has the following fundamental relations:
! 1238: \E
! 1239:
! 1240: @code{xi*xj-xj*xi=0}, @code{Di*Dj-Dj*Di=0}, @code{Di*xj-xj*Di=0} (@code{i!=j}),
! 1241: @code{Di*xi-xi*Di=1}
! 1242:
! 1243: \BJP
! 1244: $B$H$$$&4pK\4X78$r;}$D4D$G$"$k(B. @code{D} $B$O(B $BB?9`<04D(B @code{K[x1,@dots{},xn]} $B$r78?t(B
! 1245: $B$H$9$kHyJ,:nMQAG4D$G(B, @code{Di} $B$O(B @code{xi} $B$K$h$kHyJ,$rI=$9(B. $B8r494X78$K$h$j(B,
! 1246: @code{D} $B$N85$O(B, @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn} $B$J$kC19`(B
! 1247: $B<0$N(B @code{K} $B@~7A7k9g$H$7$F=q$-I=$9$3$H$,$G$-$k(B.
! 1248: Risa/Asir $B$K$*$$$F$O(B, $B$3$NC19`<0$r(B, $B2D49$JB?9`<0$HF1MM$K(B
! 1249: @code{<<i1,@dots{},in,j1,@dots{},jn>>} $B$GI=$9(B. $B$9$J$o$A(B, @code{D} $B$N85$b(B
! 1250: $BJ,;6I=8=B?9`<0$H$7$FI=$5$l$k(B. $B2C8:;;$O(B, $B2D49$N>l9g$HF1MM$K(B, @code{+}, @code{-}
! 1251: $B$K$h$j(B
! 1252: $B<B9T$G$-$k$,(B, $B>h;;$O(B, $BHs2D49@-$r9MN8$7$F(B @code{dp_weyl_mul()} $B$H$$$&4X?t(B
! 1253: $B$K$h$j<B9T$9$k(B.
! 1254: \E
! 1255:
! 1256: \BEG
! 1257: @code{D} is the ring of differential operators whose coefficients
! 1258: are polynomials in @code{K[x1,@dots{},xn]} and
! 1259: @code{Di} denotes the differentiation with respect to @code{xi}.
! 1260: According to the commutation relation,
! 1261: elements of @code{D} can be represented as a @code{K}-linear combination
! 1262: of monomials @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn}.
! 1263: In Risa/Asir, this type of monomial is represented
! 1264: by @code{<<i1,@dots{},in,j1,@dots{},jn>>} as in the case of commutative
! 1265: polynomial.
! 1266: That is, elements of @code{D} are represented by distributed polynomials.
! 1267: Addition and subtraction can be done by @code{+}, @code{-},
! 1268: but multiplication is done by calling @code{dp_weyl_mul()} because of
! 1269: the non-commutativity of @code{D}.
! 1270: \E
! 1271:
! 1272: @example
! 1273: [0] A=<<1,2,2,1>>;
! 1274: (1)*<<1,2,2,1>>
! 1275: [1] B=<<2,1,1,2>>;
! 1276: (1)*<<2,1,1,2>>
! 1277: [2] A*B;
! 1278: (1)*<<3,3,3,3>>
! 1279: [3] dp_weyl_mul(A,B);
! 1280: (1)*<<3,3,3,3>>+(1)*<<3,2,3,2>>+(4)*<<2,3,2,3>>+(4)*<<2,2,2,2>>
! 1281: +(2)*<<1,3,1,3>>+(2)*<<1,2,1,2>>
! 1282: @end example
! 1283:
! 1284: \BJP
! 1285: $B%0%l%V%J4pDl7W;;$K$D$$$F$b(B, Weyl $BBe?t@lMQ$N4X?t$H$7$F(B,
! 1286: $B<!$N4X?t$,MQ0U$7$F$"$k(B.
! 1287: \E
! 1288: \BEG
! 1289: The following functions are avilable for Groebner basis computation
! 1290: in Weyl algebra:
! 1291: \E
! 1292: @code{dp_weyl_gr_main()},
! 1293: @code{dp_weyl_gr_mod_main()},
! 1294: @code{dp_weyl_gr_f_main()},
! 1295: @code{dp_weyl_f4_main()},
! 1296: @code{dp_weyl_f4_mod_main()}.
! 1297: \BJP
! 1298: $B$^$?(B, $B1~MQ$H$7$F(B, global b $B4X?t$N7W;;$,<BAu$5$l$F$$$k(B.
! 1299: \E
! 1300: \BEG
! 1301: Computation of the global b function is implemented as an application.
! 1302: \E
! 1303:
! 1304: \BJP
1.1 noro 1305: @node $B%0%l%V%J4pDl$K4X$9$kH!?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
1306: @section $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1.2 noro 1307: \E
1308: \BEG
1309: @node Functions for Groebner basis computation,,, Groebner basis computation
1310: @section Functions for Groebner basis computation
1311: \E
1.1 noro 1312:
1313: @menu
1314: * gr hgr gr_mod::
1315: * lex_hensel lex_tl tolex tolex_d tolex_tl::
1316: * lex_hensel_gsl tolex_gsl tolex_gsl_d::
1317: * gr_minipoly minipoly::
1318: * tolexm minipolym::
1.6 ! noro 1319: * dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main::
! 1320: * dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main::
1.1 noro 1321: * dp_gr_flags dp_gr_print::
1322: * dp_ord::
1323: * dp_ptod::
1324: * dp_dtop::
1325: * dp_mod dp_rat::
1326: * dp_homo dp_dehomo::
1327: * dp_ptozp dp_prim::
1328: * dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod::
1329: * dp_hm dp_ht dp_hc dp_rest::
1330: * dp_td dp_sugar::
1331: * dp_lcm::
1332: * dp_redble::
1333: * dp_subd::
1334: * dp_mbase::
1335: * dp_mag::
1336: * dp_red dp_red_mod::
1337: * dp_sp dp_sp_mod::
1338: * p_nf p_nf_mod p_true_nf p_true_nf_mod ::
1339: * p_terms::
1340: * gb_comp::
1341: * katsura hkatsura cyclic hcyclic::
1342: * dp_vtoe dp_etov::
1343: * lex_hensel_gsl tolex_gsl tolex_gsl_d::
1.3 noro 1344: * primadec primedec::
1.5 noro 1345: * primedec_mod::
1.6 ! noro 1346: * bfunction generic_bfct::
1.1 noro 1347: @end menu
1348:
1.2 noro 1349: \JP @node gr hgr gr_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1350: \EG @node gr hgr gr_mod,,, Functions for Groebner basis computation
1.1 noro 1351: @subsection @code{gr}, @code{hgr}, @code{gr_mod}, @code{dgr}
1352: @findex gr
1353: @findex hgr
1354: @findex gr_mod
1355: @findex dgr
1356:
1357: @table @t
1358: @item gr(@var{plist},@var{vlist},@var{order})
1359: @itemx hgr(@var{plist},@var{vlist},@var{order})
1360: @itemx gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
1361: @itemx dgr(@var{plist},@var{vlist},@var{order},@var{procs})
1.2 noro 1362: \JP :: $B%0%l%V%J4pDl$N7W;;(B
1363: \EG :: Groebner basis computation
1.1 noro 1364: @end table
1365:
1366: @table @var
1367: @item return
1.2 noro 1368: \JP $B%j%9%H(B
1369: \EG list
1.4 noro 1370: @item plist vlist procs
1.2 noro 1371: \JP $B%j%9%H(B
1372: \EG list
1.1 noro 1373: @item order
1.2 noro 1374: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1375: \EG number, list or matrix
1.1 noro 1376: @item p
1.2 noro 1377: \JP 2^27 $BL$K~$NAG?t(B
1378: \EG prime less than 2^27
1.1 noro 1379: @end table
1380:
1381: @itemize @bullet
1.2 noro 1382: \BJP
1.1 noro 1383: @item
1384: $BI8=`%i%$%V%i%j$N(B @samp{gr} $B$GDj5A$5$l$F$$$k(B.
1385: @item
1386: $B$$$:$l$b(B, $BB?9`<0%j%9%H(B @var{plist} $B$N(B, $BJQ?t=g=x(B @var{vlist}, $B9`=g=x7?(B
1387: @var{order} $B$K4X$9$k%0%l%V%J4pDl$r5a$a$k(B. @code{gr()}, @code{hgr()}
1388: $B$O(B $BM-M}?t78?t(B, @code{gr_mod()} $B$O(B GF(@var{p}) $B78?t$H$7$F7W;;$9$k(B.
1389: @item
1390: @var{vlist} $B$OITDj85$N%j%9%H(B. @var{vlist} $B$K8=$l$J$$ITDj85$O(B,
1391: $B78?tBN$KB0$9$k$H8+$J$5$l$k(B.
1392: @item
1393: @code{gr()}, trace-lifting ($B%b%8%e%i1i;;$rMQ$$$?9bB.2=(B) $B$*$h$S(B sugar
1394: strategy $B$K$h$k7W;;(B, @code{hgr()} $B$O(B trace-lifting $B$*$h$S(B
1395: $B@F<!2=$K$h$k(B $B6:@5$5$l$?(B sugar strategy $B$K$h$k7W;;$r9T$&(B.
1396: @item
1397: @code{dgr()} $B$O(B, @code{gr()}, @code{dgr()} $B$r(B
1398: $B;R%W%m%;%9%j%9%H(B @var{procs} $B$N(B 2 $B$D$N%W%m%;%9$K$h$jF1;~$K7W;;$5$;(B,
1399: $B@h$K7k2L$rJV$7$?J}$N7k2L$rJV$9(B. $B7k2L$OF10l$G$"$k$,(B, $B$I$A$i$NJ}K!$,(B
1400: $B9bB.$+0lHL$K$OITL@$N$?$a(B, $B<B:]$N7P2a;~4V$rC;=L$9$k$N$KM-8z$G$"$k(B.
1401: @item
1402: @code{dgr()} $B$GI=<($5$l$k;~4V$O(B, $B$3$NH!?t$,<B9T$5$l$F$$$k%W%m%;%9$G$N(B
1403: CPU $B;~4V$G$"$j(B, $B$3$NH!?t$N>l9g$O$[$H$s$IDL?.$N$?$a$N;~4V$G$"$k(B.
1.2 noro 1404: \E
1405: \BEG
1406: @item
1407: These functions are defined in @samp{gr} in the standard library
1408: directory.
1409: @item
1410: They compute a Groebner basis of a polynomial list @var{plist} with
1411: respect to the variable order @var{vlist} and the order type @var{order}.
1412: @code{gr()} and @code{hgr()} compute a Groebner basis over the rationals
1413: and @code{gr_mod} computes over GF(@var{p}).
1414: @item
1415: Variables not included in @var{vlist} are regarded as
1416: included in the ground field.
1417: @item
1418: @code{gr()} uses trace-lifting (an improvement by modular computation)
1419: and sugar strategy.
1420: @code{hgr()} uses trace-lifting and a cured sugar strategy
1421: by using homogenization.
1422: @item
1423: @code{dgr()} executes @code{gr()}, @code{dgr()} simultaneously on
1424: two process in a child process list @var{procs} and returns
1425: the result obtained first. The results returned from both the process
1426: should be equal, but it is not known in advance which method is faster.
1427: Therefore this function is useful to reduce the actual elapsed time.
1428: @item
1429: The CPU time shown after an exection of @code{dgr()} indicates
1430: that of the master process, and most of the time corresponds to the time
1431: for communication.
1432: \E
1.1 noro 1433: @end itemize
1434:
1435: @example
1436: [0] load("gr")$
1437: [64] load("cyclic")$
1438: [74] G=gr(cyclic(5),[c0,c1,c2,c3,c4],2);
1439: [c4^15+122*c4^10-122*c4^5-1,...]
1440: [75] GM=gr_mod(cyclic(5),[c0,c1,c2,c3,c4],2,31991)$
1441: 24628*c4^15+29453*c4^10+2538*c4^5+7363
1442: [76] (G[0]*24628-GM[0])%31991;
1443: 0
1444: @end example
1445:
1446: @table @t
1.2 noro 1447: \JP @item $B;2>H(B
1448: \EG @item References
1.6 ! noro 1449: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.1 noro 1450: @fref{dp_ord}.
1451: @end table
1452:
1.2 noro 1453: \JP @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1454: \EG @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, Functions for Groebner basis computation
1.1 noro 1455: @subsection @code{lex_hensel}, @code{lex_tl}, @code{tolex}, @code{tolex_d}, @code{tolex_tl}
1456: @findex lex_hensel
1457: @findex lex_tl
1458: @findex tolex
1459: @findex tolex_d
1460: @findex tolex_tl
1461:
1462: @table @t
1463: @item lex_hensel(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1464: @itemx lex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.2 noro 1465: \JP :: $B4pDlJQ49$K$h$k<-=q<0=g=x%0%l%V%J4pDl$N7W;;(B
1466: \EG:: Groebner basis computation with respect to a lex order by change of ordering
1.1 noro 1467: @item tolex(@var{plist},@var{vlist1},@var{order},@var{vlist2})
1468: @itemx tolex_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
1469: @itemx tolex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.2 noro 1470: \JP :: $B%0%l%V%J4pDl$rF~NO$H$9$k(B, $B4pDlJQ49$K$h$k<-=q<0=g=x%0%l%V%J4pDl$N7W;;(B
1471: \EG :: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis
1.1 noro 1472: @end table
1473:
1474: @table @var
1475: @item return
1.2 noro 1476: \JP $B%j%9%H(B
1477: \EG list
1.4 noro 1478: @item plist vlist1 vlist2 procs
1.2 noro 1479: \JP $B%j%9%H(B
1480: \EG list
1.1 noro 1481: @item order
1.2 noro 1482: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1483: \EG number, list or matrix
1.1 noro 1484: @item homo
1.2 noro 1485: \JP $B%U%i%0(B
1486: \EG flag
1.1 noro 1487: @end table
1488:
1489: @itemize @bullet
1.2 noro 1490: \BJP
1.1 noro 1491: @item
1492: $BI8=`%i%$%V%i%j$N(B @samp{gr} $B$GDj5A$5$l$F$$$k(B.
1493: @item
1494: @code{lex_hensel()}, @code{lex_tl()} $B$O(B,
1495: $BB?9`<0%j%9%H(B @var{plist} $B$N(B, $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B
1496: @var{order} $B$K4X$9$k%0%l%V%J4pDl$r5a$a(B, $B$=$l$r(B, $BJQ?t=g=x(B @var{vlist2}
1497: $B$N<-=q<0=g=x%0%l%V%J4pDl$KJQ49$9$k(B.
1498: @item
1499: @code{tolex()}, @code{tolex_tl()} $B$O(B,
1500: $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B @var{order} $B$K4X$9$k%0%l%V%J4pDl$G$"$k(B
1501: $BB?9`<0%j%9%H(B @var{plist} $B$rJQ?t=g=x(B @var{vlist2} $B$N<-=q<0=g=x%0%l%V%J(B
1502: $B4pDl$KJQ49$9$k(B.
1503: @code{tolex_d()} $B$O(B, @code{tolex()} $B$K$*$1$k(B, $B3F4pDl$N7W;;$r(B, $B;R%W%m%;%9(B
1504: $B%j%9%H(B @var{procs} $B$N3F%W%m%;%9$KJ,;67W;;$5$;$k(B.
1505: @item
1506: @code{lex_hensel()}, @code{lex_tl()} $B$K$*$$$F$O(B, $B<-=q<0=g=x%0%l%V%J4pDl$N(B
1507: $B7W;;$O<!$N$h$&$K9T$o$l$k(B. (@code{[Noro,Yokoyama]} $B;2>H(B.)
1508: @enumerate
1509: @item
1510: @var{vlist1}, @var{order} $B$K4X$9$k%0%l%V%J4pDl(B @var{G0} $B$r7W;;$9$k(B.
1511: (@code{lex_hensel()} $B$N$_(B. )
1512: @item
1513: @var{G0} $B$N3F85$N(B @var{vlist2} $B$K4X$9$k<-=q<0=g=x$K$*$1$kF,78?t$r3d$i$J$$(B
1514: $B$h$&$JAG?t(B @var{p} $B$rA*$S(B, GF(@var{p}) $B>e$G$N<-=q<0=g=x%0%l%V%J4pDl(B
1515: @var{Gp} $B$r7W;;$9$k(B.
1516: @item
1517: @var{Gp} $B$K8=$l$k$9$Y$F$N9`$N(B, @var{G0} $B$K4X$9$k@55,7A(B @var{NF} $B$r7W;;$9$k(B.
1518: @item
1519: @var{Gp} $B$N3F85(B @var{f} $B$K$D$-(B, @var{f} $B$N78?t$rL$Dj78?t$G(B,
1520: @var{f} $B$N3F9`$rBP1~$9$k(B @var{NF} $B$N85$GCV$-49$((B, $B3F9`$N78?t$r(B 0 $B$HCV$$$?(B,
1521: $BL$Dj78?t$K4X$9$k@~7AJ}Dx<07O(B @var{Lf} $B$r:n$k(B.
1522: @item
1523: @var{Lf} $B$,(B, $BK!(B @var{p} $B$G0l0U2r$r;}$D$3$H$rMQ$$$F(B @var{Lf} $B$N2r$r(B
1524: $BK!(B @var{p}$B$N2r$+$i(B Hensel $B9=@.$K$h$j5a$a$k(B.
1525: @item
1526: $B$9$Y$F$N(B @var{Gp} $B$N85$K$D$-@~7AJ}Dx<0$,2r$1$?$i$=$N2rA4BN$,5a$a$k(B
1527: $B<-=q<0=g=x$G$N%0%l%V%J4pDl(B. $B$b$7$I$l$+$N@~7AJ}Dx<0$N5a2r$K<:GT$7$?$i(B,
1528: @var{p} $B$r$H$jD>$7$F$d$jD>$9(B.
1529: @end enumerate
1530:
1531: @item
1532: @code{lex_tl()}, @code{tolex_tl()} $B$K$*$$$F$O(B, $B<-=q<0=g=x%0%l%V%J4pDl$N(B
1533: $B7W;;$O<!$N$h$&$K9T$o$l$k(B.
1534:
1535: @enumerate
1536: @item
1537: @var{vlist1}, @var{order} $B$K4X$9$k%0%l%V%J4pDl(B @var{G0} $B$r7W;;$9$k(B.
1538: (@code{lex_hensel()} $B$N$_(B. )
1539: @item
1540: @var{G0} $B$,(B 0 $B<!85%7%9%F%`$G$J$$$H$-(B, @var{G0} $B$rF~NO$H$7$F(B,
1541: @var{G0} $B$N3F85$N(B @var{vlist2} $B$K4X$9$k<-=q<0=g=x$K$*$1$kF,78?t$r3d$i$J$$(B
1542: $B$h$&$JAG?t(B @var{p} $B$rA*$S(B, @var{p} $B$rMQ$$$?(B trace-lifting $B$K$h$j<-=q<0(B
1543: $B=g=x$N%0%l%V%J4pDl8uJd$r5a$a(B, $B$b$75a$^$C$?$J$i%A%'%C%/$J$7$K$=$l$,5a$a$k(B
1544: $B%0%l%V%J4pDl$H$J$k(B. $B$b$7<:GT$7$?$i(B, @var{p} $B$r$H$jD>$7$F$d$jD>$9(B.
1545: @item
1546: @var{G0} $B$,(B 0 $B<!85%7%9%F%`$N$H$-(B, @var{G0} $B$rF~NO$H$7$F(B,
1547: $B$^$:(B, @var{vlist2} $B$N:G8e$NJQ?t0J30$r>C5n$9$k>C5n=g=x$K$h$j(B
1548: $B%0%l%V%J4pDl(B @var{G1} $B$r7W;;$7(B, $B$=$l$+$i<-=q<0=g=x$N%0%l%V%J4pDl$r(B
1549: $B7W;;$9$k(B. $B$=$N:](B, $B3F%9%F%C%W$G$O(B, $BF~NO$N3F85$N(B, $B5a$a$k=g=x$K$*$1$k(B
1550: $BF,78?t$r3d$i$J$$AG?t$rMQ$$$?(B trace-lifting $B$G%0%l%V%J4pDl8uJd$r5a$a(B,
1551: $B$b$75a$^$C$?$i%A%'%C%/$J$7$K$=$l$,$=$N=g=x$G$N%0%l%V%J4pDl$H$J$k(B.
1552: @end enumerate
1553:
1554: @item
1555: $BM-M}<078?t$N7W;;$O(B, @code{lex_tl()}, @code{tolex_tl()} $B$N$_<u$1IU$1$k(B.
1556: @item
1557: @code{homo} $B$,(B 0 $B$G$J$$>l9g(B, $BFbIt$G5/F0$5$l$k(B Buchberger $B%"%k%4%j%:%`$K(B
1558: $B$*$$$F(B, $B@F<!2=$,9T$o$l$k(B.
1559: @item
1560: @code{tolex_d()} $B$GI=<($5$l$k;~4V$O(B, $B$3$NH!?t$,<B9T$5$l$F$$$k%W%m%;%9$K(B
1561: $B$*$$$F9T$o$l$?7W;;$KBP1~$7$F$$$F(B, $B;R%W%m%;%9$K$*$1$k;~4V$O4^$^$l$J$$(B.
1.2 noro 1562: \E
1563: \BEG
1564: @item
1565: These functions are defined in @samp{gr} in the standard library
1566: directory.
1567: @item
1568: @code{lex_hensel()} and @code{lex_tl()} first compute a Groebner basis
1569: with respect to the variable order @var{vlist1} and the order type @var{order}.
1570: Then the Groebner basis is converted into a lex order Groebner basis
1571: with respect to the varable order @var{vlist2}.
1572: @item
1573: @code{tolex()} and @code{tolex_tl()} convert a Groebner basis @var{plist}
1574: with respect to the variable order @var{vlist1} and the order type @var{order}
1575: into a lex order Groebner basis
1576: with respect to the varable order @var{vlist2}.
1577: @code{tolex_d()} does computations of basis elements in @code{tolex()}
1578: in parallel on the processes in a child process list @var{procs}.
1579: @item
1580: In @code{lex_hensel()} and @code{tolex_hensel()} a lex order Groebner basis
1581: is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
1582: @enumerate
1583: @item
1584: Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
1585: (Only in @code{lex_hensel()}. )
1586: @item
1587: Choose a prime which does not divide head coefficients of elements in @var{G0}
1588: with respect to @var{vlist1} and @var{order}. Then compute a lex order
1589: Groebner basis @var{Gp} over GF(@var{p}) with respect to @var{vlist2}.
1590: @item
1591: Compute @var{NF}, the set of all the normal forms with respect to
1592: @var{G0} of terms appearing in @var{Gp}.
1593: @item
1594: For each element @var{f} in @var{Gp}, replace coefficients and terms in @var{f}
1595: with undetermined coefficients and the corresponding polynomials in @var{NF}
1596: respectively, and generate a system of liear equation @var{Lf} by equating
1597: the coefficients of terms in the replaced polynomial with 0.
1598: @item
1599: Solve @var{Lf} by Hensel lifting, starting from the unique mod @var{p}
1600: solution.
1601: @item
1602: If all the linear equations generated from the elements in @var{Gp}
1603: could be solved, then the set of solutions corresponds to a lex order
1604: Groebner basis. Otherwise redo the whole process with another @var{p}.
1605: @end enumerate
1606:
1607: @item
1608: In @code{lex_tl()} and @code{tolex_tl()} a lex order Groebner basis
1609: is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
1610:
1611: @enumerate
1612: @item
1613: Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
1614: (Only in @code{lex_tl()}. )
1615: @item
1616: If @var{G0} is not zero-dimensional, choose a prime which does not divide
1617: head coefficients of elements in @var{G0} with respect to @var{vlist1} and
1618: @var{order}. Then compute a candidate of a lex order Groebner basis
1619: via trace lifting with @var{p}. If it succeeds the candidate is indeed
1620: a lex order Groebner basis without any check. Otherwise redo the whole
1621: process with another @var{p}.
1622: @item
1623:
1624: If @var{G0} is zero-dimensional, starting from @var{G0},
1625: compute a Groebner basis @var{G1} with respect to an elimination order
1626: to eliminate variables other than the last varibale in @var{vlist2}.
1627: Then compute a lex order Groebner basis stating from @var{G1}. These
1628: computations are done by trace lifting and the selection of a mudulus
1629: @var{p} is the same as in non zero-dimensional cases.
1630: @end enumerate
1631:
1632: @item
1633: Computations with rational function coefficients can be done only by
1634: @code{lex_tl()} and @code{tolex_tl()}.
1635: @item
1636: If @code{homo} is not equal to 0, homogenization is used in Buchberger
1637: algorithm.
1638: @item
1639: The CPU time shown after an execution of @code{tolex_d()} indicates
1640: that of the master process, and it does not include the time in child
1641: processes.
1642: \E
1.1 noro 1643: @end itemize
1644:
1645: @example
1646: [78] K=katsura(5)$
1647: 30msec + gc : 20msec
1648: [79] V=[u5,u4,u3,u2,u1,u0]$
1649: 0msec
1650: [80] G0=hgr(K,V,2)$
1651: 91.558sec + gc : 15.583sec
1652: [81] G1=lex_hensel(K,V,0,V,0)$
1653: 49.049sec + gc : 9.961sec
1654: [82] G2=lex_tl(K,V,0,V,1)$
1655: 31.186sec + gc : 3.500sec
1656: [83] gb_comp(G0,G1);
1657: 1
1658: 10msec
1659: [84] gb_comp(G0,G2);
1660: 1
1661: @end example
1662:
1663: @table @t
1.2 noro 1664: \JP @item $B;2>H(B
1665: \EG @item References
1.6 ! noro 1666: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.2 noro 1667: \JP @fref{dp_ord}, @fref{$BJ,;67W;;(B}
1668: \EG @fref{dp_ord}, @fref{Distributed computation}
1.1 noro 1669: @end table
1670:
1.2 noro 1671: \JP @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1672: \EG @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, Functions for Groebner basis computation
1.1 noro 1673: @subsection @code{lex_hensel_gsl}, @code{tolex_gsl}, @code{tolex_gsl_d}
1674: @findex lex_hensel_gsl
1675: @findex tolex_gsl
1676: @findex tolex_gsl_d
1677:
1678: @table @t
1679: @item lex_hensel_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.2 noro 1680: \JP :: GSL $B7A<0$N%$%G%"%k4pDl$N7W;;(B
1681: \EG ::Computation of an GSL form ideal basis
1.1 noro 1682: @item tolex_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1683: @itemx tolex_gsl_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo},@var{procs})
1.2 noro 1684: \JP :: $B%0%l%V%J4pDl$rF~NO$H$9$k(B, GSL $B7A<0$N%$%G%"%k4pDl$N7W;;(B
1685: \EG :: Computation of an GSL form ideal basis stating from a Groebner basis
1.1 noro 1686: @end table
1687:
1688: @table @var
1689: @item return
1.2 noro 1690: \JP $B%j%9%H(B
1691: \EG list
1.4 noro 1692: @item plist vlist1 vlist2 procs
1.2 noro 1693: \JP $B%j%9%H(B
1694: \EG list
1.1 noro 1695: @item order
1.2 noro 1696: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1697: \EG number, list or matrix
1.1 noro 1698: @item homo
1.2 noro 1699: \JP $B%U%i%0(B
1700: \EG flag
1.1 noro 1701: @end table
1702:
1703: @itemize @bullet
1.2 noro 1704: \BJP
1.1 noro 1705: @item
1706: @code{lex_hensel_gsl()} $B$O(B @code{lex_hensel()} $B$N(B, @code{tolex_gsl()} $B$O(B
1707: @code{tolex()} $B$NJQ<o$G(B, $B7k2L$N$_$,0[$J$k(B.
1708: @code{tolex_gsl_d()} $B$O(B, $B4pDl7W;;$r(B, @code{procs} $B$G;XDj$5$l$k;R%W%m%;%9$K(B
1709: $BJ,;67W;;$5$;$k(B.
1710: @item
1711: $BF~NO$,(B 0 $B<!85%7%9%F%`$G(B, $B$=$N<-=q<0=g=x%0%l%V%J4pDl$,(B
1712: @code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} $B$O(B
1713: @code{x0} $B$N(B 1 $BJQ?tB?9`<0(B) $B$J$k7A(B ($B$3$l$r(B SL $B7A<0$H8F$V(B) $B$r;}$D>l9g(B,
1714: @code{[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]} $B$J$k%j%9%H(B ($B$3$l$r(B GSL $B7A<0$H8F$V(B)
1715: $B$rJV$9(B.
1.2 noro 1716: $B$3$3$G(B, @code{gi} $B$O(B, @code{di*f0'*fi-gi} $B$,(B @code{f0} $B$G3d$j@Z$l$k$h$&$J(B
1.1 noro 1717: @code{x0} $B$N(B1 $BJQ?tB?9`<0$G(B,
1718: $B2r$O(B @code{f0(x0)=0} $B$J$k(B @code{x0} $B$KBP$7(B, @code{[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]}
1719: $B$H$J$k(B. $B<-=q<0=g=x%0%l%V%J4pDl$,>e$N$h$&$J7A$G$J$$>l9g(B, @code{tolex()} $B$K(B
1720: $B$h$kDL>o$N%0%l%V%J4pDl$rJV$9(B.
1721: @item
1722: GSL $B7A<0$K$h$jI=$5$l$k4pDl$O%0%l%V%J4pDl$G$O$J$$$,(B, $B0lHL$K78?t$,(B SL $B7A<0(B
1723: $B$N%0%l%V%J4pDl$h$jHs>o$K>.$5$$$?$a7W;;$bB.$/(B, $B2r$b5a$a$d$9$$(B.
1724: @code{tolex_gsl_d()} $B$GI=<($5$l$k;~4V$O(B, $B$3$NH!?t$,<B9T$5$l$F$$$k%W%m%;%9$K(B
1725: $B$*$$$F9T$o$l$?7W;;$KBP1~$7$F$$$F(B, $B;R%W%m%;%9$K$*$1$k;~4V$O4^$^$l$J$$(B.
1.2 noro 1726: \E
1727: \BEG
1728: @item
1729: @code{lex_hensel_gsl()} and @code{lex_hensel()} are variants of
1730: @code{tolex_gsl()} and @code{tolex()} respectively. The results are
1731: Groebner basis or a kind of ideal basis, called GSL form.
1732: @code{tolex_gsl_d()} does basis computations in parallel on child
1733: processes specified in @code{procs}.
1734:
1735: @item
1736: If the input is zero-dimensional and a lex order Groebner basis has
1737: the form @code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} are
1738: univariate polynomials of @code{x0}; SL form), then this these
1739: functions return a list such as
1740: @code{[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]} (GSL form). In this list
1741: @code{gi} is a univariate polynomial of @code{x0} such that
1742: @code{di*f0'*fi-gi} divides @code{f0} and the roots of the input ideal is
1743: @code{[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]} for @code{x0}
1744: such that @code{f0(x0)=0}.
1745: If the lex order Groebner basis does not have the above form,
1746: these functions return
1747: a lex order Groebner basis computed by @code{tolex()}.
1748: @item
1749: Though an ideal basis represented as GSL form is not a Groebner basis
1750: we can expect that the coefficients are much smaller than those in a Groebner
1751: basis and that the computation is efficient.
1752: The CPU time shown after an execution of @code{tolex_gsl_d()} indicates
1753: that of the master process, and it does not include the time in child
1754: processes.
1755: \E
1.1 noro 1756: @end itemize
1757:
1758: @example
1759: [103] K=katsura(5)$
1760: [104] V=[u5,u4,u3,u2,u1,u0]$
1761: [105] G0=gr(K,V,0)$
1762: [106] GSL=tolex_gsl(G0,V,0,V)$
1763: [107] GSL[0];
1764: [u1,8635837421130477667200000000*u0^31-...]
1765: [108] GSL[1];
1766: [u2,10352277157007342793600000000*u0^31-...]
1767: [109] GSL[5];
1.5 noro 1768: [u0,11771021876193064124640000000*u0^32-...,
1769: 376672700038178051988480000000*u0^31-...]
1.1 noro 1770: @end example
1771:
1772: @table @t
1.2 noro 1773: \JP @item $B;2>H(B
1774: \EG @item References
1.1 noro 1775: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
1.2 noro 1776: \JP @fref{$BJ,;67W;;(B}
1777: \EG @fref{Distributed computation}
1.1 noro 1778: @end table
1779:
1.2 noro 1780: \JP @node gr_minipoly minipoly,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1781: \EG @node gr_minipoly minipoly,,, Functions for Groebner basis computation
1.1 noro 1782: @subsection @code{gr_minipoly}, @code{minipoly}
1783: @findex gr_minipoly
1784: @findex minipoly
1785:
1786: @table @t
1787: @item gr_minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v},@var{homo})
1.2 noro 1788: \JP :: $BB?9`<0$N(B, $B%$%G%"%k$rK!$H$7$?:G>.B?9`<0$N7W;;(B
1789: \EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
1.1 noro 1790: @item minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v})
1.2 noro 1791: \JP :: $B%0%l%V%J4pDl$rF~NO$H$9$k(B, $BB?9`<0$N:G>.B?9`<0$N7W;;(B
1792: \EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
1.1 noro 1793: @end table
1794:
1795: @table @var
1796: @item return
1.2 noro 1797: \JP $BB?9`<0(B
1798: \EG polynomial
1.4 noro 1799: @item plist vlist
1.2 noro 1800: \JP $B%j%9%H(B
1801: \EG list
1.1 noro 1802: @item order
1.2 noro 1803: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1804: \EG number, list or matrix
1.1 noro 1805: @item poly
1.2 noro 1806: \JP $BB?9`<0(B
1807: \EG polynomial
1.1 noro 1808: @item v
1.2 noro 1809: \JP $BITDj85(B
1810: \EG indeterminate
1.1 noro 1811: @item homo
1.2 noro 1812: \JP $B%U%i%0(B
1813: \EG flag
1.1 noro 1814: @end table
1815:
1816: @itemize @bullet
1.2 noro 1817: \BJP
1.1 noro 1818: @item
1819: @code{gr_minipoly()} $B$O%0%l%V%J4pDl$N7W;;$+$i9T$$(B, @code{minipoly()} $B$O(B
1820: $BF~NO$r%0%l%V%J4pDl$H$_$J$9(B.
1821: @item
1822: $B%$%G%"%k(B I $B$,BN(B K $B>e$NB?9`<04D(B K[X] $B$N(B 0 $B<!85%$%G%"%k$N;~(B,
1823: K[@var{v}] $B$N85(B f(@var{v}) $B$K(B f(@var{p}) mod I $B$rBP1~$5$;$k(B
1824: $B4D=`F17?$N3K$O(B 0 $B$G$J$$B?9`<0$K$h$j@8@.$5$l$k(B. $B$3$N@8@.85$r(B @var{p}
1825: $B$N(B, $BK!(B @var{I} $B$G$N:G>.B?9`<0$H8F$V(B.
1826: @item
1827: @code{gr_minipoly()}, @code{minipoly()} $B$O(B, $BB?9`<0(B @var{p} $B$N:G>.B?9`<0(B
1828: $B$r5a$a(B, @var{v} $B$rJQ?t$H$9$kB?9`<0$H$7$FJV$9(B.
1829: @item
1830: $B:G>.B?9`<0$O(B, $B%0%l%V%J4pDl$N(B 1 $B$D$N85$H$7$F7W;;$9$k$3$H$b$G$-$k$,(B,
1831: $B:G>.B?9`<0$N$_$r5a$a$?$$>l9g(B, @code{minipoly()}, @code{gr_minipoly()} $B$O(B
1832: $B%0%l%V%J4pDl$rMQ$$$kJ}K!$KHf$Y$F8zN($,$h$$(B.
1833: @item
1834: @code{gr_minipoly()} $B$K;XDj$9$k9`=g=x$H$7$F$O(B, $BDL>oA4<!?t5U<-=q<0=g=x$r(B
1835: $BMQ$$$k(B.
1.2 noro 1836: \E
1837: \BEG
1838: @item
1839: @code{gr_minipoly()} begins by computing a Groebner basis.
1840: @code{minipoly()} regards an input as a Groebner basis with respect to
1841: the variable order @var{vlist} and the order type @var{order}.
1842: @item
1843: Let K be a field. If an ideal @var{I} in K[X] is zero-dimensional, then, for
1844: a polynomial @var{p} in K[X], the kernel of a homomorphism from
1845: K[@var{v}] to K[X]/@var{I} which maps f(@var{v}) to f(@var{p}) mod @var{I}
1846: is generated by a polynomial. The generator is called the minimal polynomial
1847: of @var{p} modulo @var{I}.
1848: @item
1849: @code{gr_minipoly()} and @code{minipoly()} computes the minimal polynomial
1850: of a polynomial @var{p} and returns it as a polynomial of @var{v}.
1851: @item
1852: The minimal polynomial can be computed as an element of a Groebner basis.
1853: But if we are only interested in the minimal polynomial,
1854: @code{minipoly()} and @code{gr_minipoly()} can compute it more efficiently
1855: than methods using Groebner basis computation.
1856: @item
1857: It is recommended to use a degree reverse lex order as a term order
1858: for @code{gr_minipoly()}.
1859: \E
1.1 noro 1860: @end itemize
1861:
1862: @example
1863: [117] G=tolex(G0,V,0,V)$
1864: 43.818sec + gc : 11.202sec
1865: [118] GSL=tolex_gsl(G0,V,0,V)$
1866: 17.123sec + gc : 2.590sec
1867: [119] MP=minipoly(G0,V,0,u0,z)$
1868: 4.370sec + gc : 780msec
1869: @end example
1870:
1871: @table @t
1.2 noro 1872: \JP @item $B;2>H(B
1873: \EG @item References
1.1 noro 1874: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl}.
1875: @end table
1876:
1.2 noro 1877: \JP @node tolexm minipolym,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
1878: \EG @node tolexm minipolym,,, Functions for Groebner basis computation
1.1 noro 1879: @subsection @code{tolexm}, @code{minipolym}
1880: @findex tolexm
1881: @findex minipolym
1882:
1883: @table @t
1884: @item tolexm(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{mod})
1.2 noro 1885: \JP :: $BK!(B @var{mod} $B$G$N4pDlJQ49$K$h$k%0%l%V%J4pDl7W;;(B
1886: \EG :: Groebner basis computation modulo @var{mod} by change of ordering.
1.1 noro 1887: @item minipolym(@var{plist},@var{vlist1},@var{order},@var{poly},@var{v},@var{mod})
1.2 noro 1888: \JP :: $BK!(B @var{mod} $B$G$N%0%l%V%J4pDl$K$h$kB?9`<0$N:G>.B?9`<0$N7W;;(B
1889: \EG :: Minimal polynomial computation modulo @var{mod} the same method as
1.1 noro 1890: @end table
1891:
1892: @table @var
1893: @item return
1.2 noro 1894: \JP @code{tolexm()} : $B%j%9%H(B, @code{minipolym()} : $BB?9`<0(B
1895: \EG @code{tolexm()} : list, @code{minipolym()} : polynomial
1.4 noro 1896: @item plist vlist1 vlist2
1.2 noro 1897: \JP $B%j%9%H(B
1898: \EG list
1.1 noro 1899: @item order
1.2 noro 1900: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1901: \EG number, list or matrix
1.1 noro 1902: @item mod
1.2 noro 1903: \JP $BAG?t(B
1904: \EG prime
1.1 noro 1905: @end table
1906:
1907: @itemize @bullet
1.2 noro 1908: \BJP
1.1 noro 1909: @item
1910: $BF~NO(B @var{plist} $B$O$$$:$l$b(B $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B @var{order},
1911: $BK!(B @var{mod} $B$K$*$1$k%0%l%V%J4pDl$G$J$1$l$P$J$i$J$$(B.
1912: @item
1913: @code{minipolym()} $B$O(B @code{minipoly} $B$KBP1~$9$k7W;;$rK!(B @var{mod}$B$G9T$&(B.
1914: @item
1915: @code{tolexm()} $B$O(B FGLM $BK!$K$h$k4pDlJQ49$K$h$j(B @var{vlist2},
1916: $B<-=q<0=g=x$K$h$k%0%l%V%J4pDl$r7W;;$9$k(B.
1.2 noro 1917: \E
1918: \BEG
1919: @item
1920: An input @var{plist} must be a Groebner basis modulo @var{mod}
1921: with respect to the variable order @var{vlist1} and the order type @var{order}.
1922: @item
1923: @code{minipolym()} executes the same computation as in @code{minipoly}.
1924: @item
1925: @code{tolexm()} computes a lex order Groebner basis modulo @var{mod}
1926: with respect to the variable order @var{vlist2}, by using FGLM algorithm.
1927: \E
1.1 noro 1928: @end itemize
1929:
1930: @example
1931: [197] tolexm(G0,V,0,V,31991);
1932: [8271*u0^31+10435*u0^30+816*u0^29+26809*u0^28+...,...]
1933: [198] minipolym(G0,V,0,u0,z,31991);
1934: z^32+11405*z^31+20868*z^30+21602*z^29+...
1935: @end example
1936:
1937: @table @t
1.2 noro 1938: \JP @item $B;2>H(B
1939: \EG @item References
1.1 noro 1940: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
1941: @fref{gr_minipoly minipoly}.
1942: @end table
1943:
1.6 ! noro 1944: \JP @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
! 1945: \EG @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, Functions for Groebner basis computation
! 1946: @subsection @code{dp_gr_main}, @code{dp_gr_mod_main}, @code{dp_gr_f_main}, @code{dp_weyl_gr_main}, @code{dp_weyl_gr_mod_main}, @code{dp_weyl_gr_f_main}
1.1 noro 1947: @findex dp_gr_main
1948: @findex dp_gr_mod_main
1.5 noro 1949: @findex dp_gr_f_main
1.6 ! noro 1950: @findex dp_weyl_gr_main
! 1951: @findex dp_weyl_gr_mod_main
! 1952: @findex dp_weyl_gr_f_main
1.1 noro 1953:
1954: @table @t
1955: @item dp_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
1956: @itemx dp_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
1.5 noro 1957: @itemx dp_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
1.6 ! noro 1958: @itemx dp_weyl_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
! 1959: @itemx dp_weyl_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
! 1960: @itemx dp_weyl_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
1.2 noro 1961: \JP :: $B%0%l%V%J4pDl$N7W;;(B ($BAH$_9~$_H!?t(B)
1962: \EG :: Groebner basis computation (built-in functions)
1.1 noro 1963: @end table
1964:
1965: @table @var
1966: @item return
1.2 noro 1967: \JP $B%j%9%H(B
1968: \EG list
1.4 noro 1969: @item plist vlist
1.2 noro 1970: \JP $B%j%9%H(B
1971: \EG list
1.1 noro 1972: @item order
1.2 noro 1973: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
1974: \EG number, list or matrix
1.1 noro 1975: @item homo
1.2 noro 1976: \JP $B%U%i%0(B
1977: \EG flag
1.1 noro 1978: @item modular
1.2 noro 1979: \JP $B%U%i%0$^$?$OAG?t(B
1980: \EG flag or prime
1.1 noro 1981: @end table
1982:
1983: @itemize @bullet
1.2 noro 1984: \BJP
1.1 noro 1985: @item
1986: $B$3$l$i$NH!?t$O(B, $B%0%l%V%J4pDl7W;;$N4pK\E*AH$_9~$_H!?t$G$"$j(B, @code{gr()},
1987: @code{hgr()}, @code{gr_mod()} $B$J$I$O$9$Y$F$3$l$i$NH!?t$r8F$S=P$7$F7W;;(B
1.6 ! noro 1988: $B$r9T$C$F$$$k(B. $B4X?tL>$K(B weyl $B$,F~$C$F$$$k$b$N$O(B, Weyl $BBe?t>e$N7W;;(B
! 1989: $B$N$?$a$N4X?t$G$"$k(B.
1.1 noro 1990: @item
1.6 ! noro 1991: @code{dp_gr_f_main()}, @code{dp_weyl_f_main()} $B$O(B, $B<o!9$NM-8BBN>e$N%0%l%V%J4pDl$r7W;;$9$k(B
1.5 noro 1992: $B>l9g$KMQ$$$k(B. $BF~NO$O(B, $B$"$i$+$8$a(B, @code{simp_ff()} $B$J$I$G(B,
1993: $B9M$($kM-8BBN>e$K<M1F$5$l$F$$$kI,MW$,$"$k(B.
1994: @item
1.1 noro 1995: $B%U%i%0(B @var{homo} $B$,(B 0 $B$G$J$$;~(B, $BF~NO$r@F<!2=$7$F$+$i(B Buchberger $B%"%k%4%j%:%`(B
1996: $B$r<B9T$9$k(B.
1997: @item
1998: @code{dp_gr_mod_main()} $B$KBP$7$F$O(B, @var{modular} $B$O(B, GF(@var{modular}) $B>e(B
1999: $B$G$N7W;;$r0UL#$9$k(B.
2000: @code{dp_gr_main()} $B$KBP$7$F$O(B, @var{modular} $B$O<!$N$h$&$J0UL#$r;}$D(B.
2001: @enumerate
2002: @item
2003: @var{modular} $B$,(B 1 $B$N;~(B, trace-lifting $B$K$h$k7W;;$r9T$&(B. $BAG?t$O(B
2004: @code{lprime(0)} $B$+$i=g$K@.8y$9$k$^$G(B @code{lprime()} $B$r8F$S=P$7$F@8@.$9$k(B.
2005: @item
2006: @var{modular} $B$,(B 2 $B0J>e$N<+A3?t$N;~(B, $B$=$NCM$rAG?t$H$_$J$7$F(B trace-lifting
2007: $B$r9T$&(B. $B$=$NAG?t$G<:GT$7$?>l9g(B, 0 $B$rJV$9(B.
2008: @item
2009: @var{modular} $B$,Ii$N>l9g(B,
2010: @var{-modular} $B$KBP$7$F>e=R$N5,B'$,E,MQ$5$l$k$,(B, trace-lifting $B$N:G=*(B
2011: $BCJ3,$N%0%l%V%J4pDl%A%'%C%/$H%$%G%"%k%a%s%P%7%C%W%A%'%C%/$,>JN,$5$l$k(B.
2012: @end enumerate
2013:
2014: @item
2015: @code{gr(P,V,O)} $B$O(B @code{dp_gr_main(P,V,0,1,O)}, @code{hgr(P,V,O)} $B$O(B
2016: @code{dp_gr_main(P,V,1,1,O)}, @code{gr_mod(P,V,O,M)} $B$O(B
2017: @code{dp_gr_mod_main(P,V,0,M,O)} $B$r$=$l$>$l<B9T$9$k(B.
2018: @item
2019: @var{homo}, @var{modular} $B$NB>$K(B, @code{dp_gr_flags()} $B$G@_Dj$5$l$k(B
2020: $B$5$^$6$^$J%U%i%0$K$h$j7W;;$,@)8f$5$l$k(B.
1.2 noro 2021: \E
2022: \BEG
2023: @item
2024: These functions are fundamental built-in functions for Groebner basis
2025: computation and @code{gr()},@code{hgr()} and @code{gr_mod()}
1.6 ! noro 2026: are all interfaces to these functions. Functions whose names
! 2027: contain weyl are those for computation in Weyl algebra.
1.2 noro 2028: @item
1.6 ! noro 2029: @code{dp_gr_f_main()} and @code{dp_weyl_gr_f_main()}
! 2030: are functions for Groebner basis computation
1.5 noro 2031: over various finite fields. Coefficients of input polynomials
2032: must be converted to elements of a finite field
2033: currently specified by @code{setmod_ff()}.
2034: @item
1.2 noro 2035: If @var{homo} is not equal to 0, homogenization is applied before entering
2036: Buchberger algorithm
2037: @item
2038: For @code{dp_gr_mod_main()}, @var{modular} means a computation over
2039: GF(@var{modular}).
2040: For @code{dp_gr_main()}, @var{modular} has the following mean.
2041: @enumerate
2042: @item
2043: If @var{modular} is 1 , trace lifting is used. Primes for trace lifting
2044: are generated by @code{lprime()}, starting from @code{lprime(0)}, until
2045: the computation succeeds.
2046: @item
2047: If @var{modular} is an integer greater than 1, the integer is regarded as a
2048: prime and trace lifting is executed by using the prime. If the computation
2049: fails then 0 is returned.
2050: @item
2051: If @var{modular} is negative, the above rule is applied for @var{-modular}
2052: but the Groebner basis check and ideal-membership check are omitted in
2053: the last stage of trace lifting.
2054: @end enumerate
2055:
2056: @item
2057: @code{gr(P,V,O)}, @code{hgr(P,V,O)} and @code{gr_mod(P,V,O,M)} execute
2058: @code{dp_gr_main(P,V,0,1,O)}, @code{dp_gr_main(P,V,1,1,O)}
2059: and @code{dp_gr_mod_main(P,V,0,M,O)} respectively.
2060: @item
2061: Actual computation is controlled by various parameters set by
2062: @code{dp_gr_flags()}, other then by @var{homo} and @var{modular}.
2063: \E
1.1 noro 2064: @end itemize
2065:
2066: @table @t
1.2 noro 2067: \JP @item $B;2>H(B
2068: \EG @item References
1.1 noro 2069: @fref{dp_ord},
2070: @fref{dp_gr_flags dp_gr_print},
2071: @fref{gr hgr gr_mod},
1.5 noro 2072: @fref{setmod_ff},
1.2 noro 2073: \JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}.
2074: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2075: @end table
2076:
1.6 ! noro 2077: \JP @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
! 2078: \EG @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, Functions for Groebner basis computation
! 2079: @subsection @code{dp_f4_main}, @code{dp_f4_mod_main}, @code{dp_weyl_f4_main}, @code{dp_weyl_f4_mod_main}
1.1 noro 2080: @findex dp_f4_main
2081: @findex dp_f4_mod_main
1.6 ! noro 2082: @findex dp_weyl_f4_main
! 2083: @findex dp_weyl_f4_mod_main
1.1 noro 2084:
2085: @table @t
2086: @item dp_f4_main(@var{plist},@var{vlist},@var{order})
2087: @itemx dp_f4_mod_main(@var{plist},@var{vlist},@var{order})
1.6 ! noro 2088: @itemx dp_weyl_f4_main(@var{plist},@var{vlist},@var{order})
! 2089: @itemx dp_weyl_f4_mod_main(@var{plist},@var{vlist},@var{order})
1.2 noro 2090: \JP :: F4 $B%"%k%4%j%:%`$K$h$k%0%l%V%J4pDl$N7W;;(B ($BAH$_9~$_H!?t(B)
2091: \EG :: Groebner basis computation by F4 algorithm (built-in functions)
1.1 noro 2092: @end table
2093:
2094: @table @var
2095: @item return
1.2 noro 2096: \JP $B%j%9%H(B
2097: \EG list
1.4 noro 2098: @item plist vlist
1.2 noro 2099: \JP $B%j%9%H(B
2100: \EG list
1.1 noro 2101: @item order
1.2 noro 2102: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
2103: \EG number, list or matrix
1.1 noro 2104: @end table
2105:
2106: @itemize @bullet
1.2 noro 2107: \BJP
1.1 noro 2108: @item
2109: F4 $B%"%k%4%j%:%`$K$h$j%0%l%V%J4pDl$N7W;;$r9T$&(B.
2110: @item
2111: F4 $B%"%k%4%j%:%`$O(B, J.C. Faugere $B$K$h$jDs>'$5$l$??7@$Be%0%l%V%J4pDl(B
2112: $B;;K!$G$"$j(B, $BK\<BAu$O(B, $BCf9q>jM>DjM}$K$h$k@~7AJ}Dx<05a2r$rMQ$$$?(B
2113: $B;n83E*$J<BAu$G$"$k(B.
2114: @item
1.6 ! noro 2115: $B@F<!2=$N0z?t$,$J$$$3$H$r=|$1$P(B, $B0z?t$*$h$SF0:n$O$=$l$>$l(B
! 2116: @code{dp_gr_main()}, @code{dp_gr_mod_main()},
! 2117: @code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()}
1.1 noro 2118: $B$HF1MM$G$"$k(B.
1.2 noro 2119: \E
2120: \BEG
2121: @item
2122: These functions compute Groebner bases by F4 algorithm.
2123: @item
2124: F4 is a new generation algorithm for Groebner basis computation
2125: invented by J.C. Faugere. The current implementation of @code{dp_f4_main()}
2126: uses Chinese Remainder theorem and not highly optimized.
2127: @item
2128: Arguments and actions are the same as those of
1.6 ! noro 2129: @code{dp_gr_main()}, @code{dp_gr_mod_main()},
! 2130: @code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()},
! 2131: except for lack of the argument for controlling homogenization.
1.2 noro 2132: \E
1.1 noro 2133: @end itemize
2134:
2135: @table @t
1.2 noro 2136: \JP @item $B;2>H(B
2137: \EG @item References
1.1 noro 2138: @fref{dp_ord},
2139: @fref{dp_gr_flags dp_gr_print},
2140: @fref{gr hgr gr_mod},
1.2 noro 2141: \JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}.
2142: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2143: @end table
2144:
1.2 noro 2145: \JP @node dp_gr_flags dp_gr_print,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2146: \EG @node dp_gr_flags dp_gr_print,,, Functions for Groebner basis computation
1.1 noro 2147: @subsection @code{dp_gr_flags}, @code{dp_gr_print}
2148: @findex dp_gr_flags
2149: @findex dp_gr_print
2150:
2151: @table @t
2152: @item dp_gr_flags([@var{list}])
2153: @itemx dp_gr_print([@var{0|1}])
1.2 noro 2154: \JP :: $B7W;;$*$h$SI=<(MQ%Q%i%a%?$N@_Dj(B, $B;2>H(B
2155: \BEG :: Set and show various parameters for cotrolling computations
2156: and showing informations.
2157: \E
1.1 noro 2158: @end table
2159:
2160: @table @var
2161: @item return
1.2 noro 2162: \JP $B@_DjCM(B
2163: \EG value currently set
1.1 noro 2164: @item list
1.2 noro 2165: \JP $B%j%9%H(B
2166: \EG list
1.1 noro 2167: @end table
2168:
2169: @itemize @bullet
1.2 noro 2170: \BJP
1.1 noro 2171: @item
1.5 noro 2172: @code{dp_gr_main()}, @code{dp_gr_mod_main()}, @code{dp_gr_f_main()} $B<B9T;~$K$*$1$k$5$^$6$^(B
1.1 noro 2173: $B$J%Q%i%a%?$r@_Dj(B, $B;2>H$9$k(B.
2174: @item
2175: $B0z?t$,$J$$>l9g(B, $B8=:_$N@_Dj$,JV$5$l$k(B.
2176: @item
2177: $B0z?t$O(B, @code{["Print",1,"NoSugar",1,...]} $B$J$k7A$N%j%9%H$G(B, $B:8$+$i=g$K(B
2178: $B@_Dj$5$l$k(B. $B%Q%i%a%?L>$OJ8;zNs$GM?$($kI,MW$,$"$k(B.
2179: @item
2180: @code{dp_gr_print()} $B$O(B, $BFC$K%Q%i%a%?(B @code{Print} $B$NCM$rD>@\@_Dj(B, $B;2>H(B
2181: $B$G$-$k(B. $B$3$l$O(B, @code{dp_gr_main()} $B$J$I$r%5%V%k!<%A%s$H$7$FMQ$$$k%f!<%6(B
2182: $BH!?t$K$*$$$F(B, @code{Print} $B$NCM$r8+$F(B, $B$=$N%5%V%k!<%A%s$,Cf4V>pJs$NI=<((B
2183: $B$r9T$&:]$K(B, $B?WB.$K%U%i%0$r8+$k$3$H$,$G$-$k$h$&$KMQ0U$5$l$F$$$k(B.
1.2 noro 2184: \E
2185: \BEG
2186: @item
2187: @code{dp_gr_flags()} sets and shows various parameters for Groebner basis
2188: computation.
2189: @item
2190: If no argument is specified the current settings are returned.
2191: @item
2192: Arguments must be specified as a list such as
2193: @code{["Print",1,"NoSugar",1,...]}. Names of parameters must be character
2194: strings.
2195: @item
2196: @code{dp_gr_print()} is used to set and show the value of a parameter
2197: @code{Print}. This functions is prepared to get quickly the value of
2198: @code{Print} when a user defined function calling @code{dp_gr_main()} etc.
2199: uses the value as a flag for showing intermediate informations.
2200: \E
1.1 noro 2201: @end itemize
2202:
2203: @table @t
1.2 noro 2204: \JP @item $B;2>H(B
2205: \EG @item References
2206: \JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}
2207: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2208: @end table
2209:
1.2 noro 2210: \JP @node dp_ord,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2211: \EG @node dp_ord,,, Functions for Groebner basis computation
1.1 noro 2212: @subsection @code{dp_ord}
2213: @findex dp_ord
2214:
2215: @table @t
2216: @item dp_ord([@var{order}])
1.2 noro 2217: \JP :: $BJQ?t=g=x7?$N@_Dj(B, $B;2>H(B
2218: \EG :: Set and show the ordering type.
1.1 noro 2219: @end table
2220:
2221: @table @var
2222: @item return
1.2 noro 2223: \JP $BJQ?t=g=x7?(B ($B?t(B, $B%j%9%H$^$?$O9TNs(B)
2224: \EG ordering type (number, list or matrix)
1.1 noro 2225: @item order
1.2 noro 2226: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
2227: \EG number, list or matrix
1.1 noro 2228: @end table
2229:
2230: @itemize @bullet
1.2 noro 2231: \BJP
1.1 noro 2232: @item
2233: $B0z?t$,$"$k;~(B, $BJQ?t=g=x7?$r(B @var{order} $B$K@_Dj$9$k(B. $B0z?t$,$J$$;~(B,
2234: $B8=:_@_Dj$5$l$F$$$kJQ?t=g=x7?$rJV$9(B.
2235:
2236: @item
2237: $BJ,;6I=8=B?9`<0$K4X$9$kH!?t(B, $B1i;;$O0z?t$H$7$FJQ?t=g=x7?$r$H$k$b$N$H$H$i$J$$$b$N(B
2238: $B$,$"$j(B, $B$H$i$J$$$b$N$K4X$7$F$O(B, $B$=$N;~E@$G@_Dj$5$l$F$$$kCM$rMQ$$$F7W;;$,(B
2239: $B9T$o$l$k(B.
2240:
2241: @item
2242: @code{gr()} $B$J$I(B, $B0z?t$H$7$FJQ?t=g=x7?$r$H$k$b$N$O(B, $BFbIt$G(B @code{dp_ord()}
2243: $B$r8F$S=P$7(B, $BJQ?t=g=x7?$r@_Dj$9$k(B. $B$3$N@_Dj$O(B, $B7W;;=*N;8e$b@8$-;D$k(B.
2244:
2245: @item
2246: $BJ,;6I=8=B?9`<0$N;MB'1i;;$b(B, $B@_Dj$5$l$F$$$kCM$rMQ$$$F7W;;$5$l$k(B. $B=>$C$F(B,
2247: $B$=$NB?9`<0$,@8@.$5$l$?;~E@$K$*$1$kJQ?t=g=x7?$,(B, $B;MB'1i;;;~$K@5$7$/@_Dj(B
2248: $B$5$l$F$$$J$1$l$P$J$i$J$$(B. $B$^$?(B, $B1i;;BP>]$H$J$kB?9`<0$O(B, $BF10l$NJQ?t=g=x(B
2249: $B7?$K4p$E$$$F@8@.$5$l$?$b$N$G$J$1$l$P$J$i$J$$(B.
2250:
2251: @item
2252: $B%H%C%W%l%Y%kH!?t0J30$NH!?t$rD>@\8F$S=P$9>l9g$K$O(B, $B$3$NH!?t$K$h$j(B
2253: $BJQ?t=g=x7?$r@5$7$/@_Dj$7$J$1$l$P$J$i$J$$(B.
1.2 noro 2254: \E
2255: \BEG
2256: @item
2257: If an argument is specified, the function
2258: sets the current ordering type to @var{order}.
2259: If no argument is specified, the function returns the ordering
2260: type currently set.
2261:
2262: @item
2263: There are two types of functions concerning distributed polynomial,
2264: functions which take a ordering type and those which don't take it.
2265: The latter ones use the current setting.
2266:
2267: @item
2268: Functions such as @code{gr()}, which need a ordering type as an argument,
2269: call @code{dp_ord()} internally during the execution.
2270: The setting remains after the execution.
2271:
2272: Fundamental arithmetics for distributed polynomial also use the current
2273: setting. Therefore, when such arithmetics for distributed polynomials
2274: are done, the current setting must coincide with the ordering type
2275: which was used upon the creation of the polynomials. It is assumed
2276: that such polynomials were generated under the same ordering type.
2277:
2278: @item
2279: Type of term ordering must be correctly set by this function
2280: when functions other than top level functions are called directly.
2281: \E
1.1 noro 2282: @end itemize
2283:
2284: @example
2285: [19] dp_ord(0)$
2286: [20] <<1,2,3>>+<<3,1,1>>;
2287: (1)*<<1,2,3>>+(1)*<<3,1,1>>
2288: [21] dp_ord(2)$
2289: [22] <<1,2,3>>+<<3,1,1>>;
2290: (1)*<<3,1,1>>+(1)*<<1,2,3>>
2291: @end example
2292:
2293: @table @t
1.2 noro 2294: \JP @item $B;2>H(B
2295: \EG @item References
2296: \JP @fref{$B9`=g=x$N@_Dj(B}
2297: \EG @fref{Setting term orderings}
1.1 noro 2298: @end table
2299:
1.2 noro 2300: \JP @node dp_ptod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2301: \EG @node dp_ptod,,, Functions for Groebner basis computation
1.1 noro 2302: @subsection @code{dp_ptod}
2303: @findex dp_ptod
2304:
2305: @table @t
2306: @item dp_ptod(@var{poly},@var{vlist})
1.2 noro 2307: \JP :: $BB?9`<0$rJ,;6I=8=B?9`<0$KJQ49$9$k(B.
2308: \EG :: Converts an ordinary polynomial into a distributed polynomial.
1.1 noro 2309: @end table
2310:
2311: @table @var
2312: @item return
1.2 noro 2313: \JP $BJ,;6I=8=B?9`<0(B
2314: \EG distributed polynomial
1.1 noro 2315: @item poly
1.2 noro 2316: \JP $BB?9`<0(B
2317: \EG polynomial
1.1 noro 2318: @item vlist
1.2 noro 2319: \JP $B%j%9%H(B
2320: \EG list
1.1 noro 2321: @end table
2322:
2323: @itemize @bullet
1.2 noro 2324: \BJP
1.1 noro 2325: @item
2326: $BJQ?t=g=x(B @var{vlist} $B$*$h$S8=:_$NJQ?t=g=x7?$K=>$C$FJ,;6I=8=B?9`<0$KJQ49$9$k(B.
2327: @item
2328: @var{vlist} $B$K4^$^$l$J$$ITDj85$O(B, $B78?tBN$KB0$9$k$H$7$FJQ49$5$l$k(B.
1.2 noro 2329: \E
2330: \BEG
2331: @item
2332: According to the variable ordering @var{vlist} and current
2333: type of term ordering, this function converts an ordinary
2334: polynomial into a distributed polynomial.
2335: @item
2336: Indeterminates not included in @var{vlist} are regarded to belong to
2337: the coefficient field.
2338: \E
1.1 noro 2339: @end itemize
2340:
2341: @example
2342: [50] dp_ord(0);
2343: 1
2344: [51] dp_ptod((x+y+z)^2,[x,y,z]);
2345: (1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
2346: +(1)*<<0,0,2>>
2347: [52] dp_ptod((x+y+z)^2,[x,y]);
1.5 noro 2348: (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
2349: +(z^2)*<<0,0>>
1.1 noro 2350: @end example
2351:
2352: @table @t
1.2 noro 2353: \JP @item $B;2>H(B
2354: \EG @item References
1.1 noro 2355: @fref{dp_dtop},
2356: @fref{dp_ord}.
2357: @end table
2358:
1.2 noro 2359: \JP @node dp_dtop,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2360: \EG @node dp_dtop,,, Functions for Groebner basis computation
1.1 noro 2361: @subsection @code{dp_dtop}
2362: @findex dp_dtop
2363:
2364: @table @t
2365: @item dp_dtop(@var{dpoly},@var{vlist})
1.2 noro 2366: \JP :: $BJ,;6I=8=B?9`<0$rB?9`<0$KJQ49$9$k(B.
2367: \EG :: Converts a distributed polynomial into an ordinary polynomial.
1.1 noro 2368: @end table
2369:
2370: @table @var
2371: @item return
1.2 noro 2372: \JP $BB?9`<0(B
2373: \EG polynomial
1.1 noro 2374: @item dpoly
1.2 noro 2375: \JP $BJ,;6I=8=B?9`<0(B
2376: \EG distributed polynomial
1.1 noro 2377: @item vlist
1.2 noro 2378: \JP $B%j%9%H(B
2379: \EG list
1.1 noro 2380: @end table
2381:
2382: @itemize @bullet
1.2 noro 2383: \BJP
1.1 noro 2384: @item
2385: $BJ,;6I=8=B?9`<0$r(B, $BM?$($i$l$?ITDj85%j%9%H$rMQ$$$FB?9`<0$KJQ49$9$k(B.
2386: @item
2387: $BITDj85%j%9%H$O(B, $BD9$5J,;6I=8=B?9`<0$NJQ?t$N8D?t$H0lCW$7$F$$$l$P2?$G$b$h$$(B.
1.2 noro 2388: \E
2389: \BEG
2390: @item
2391: This function converts a distributed polynomial into an ordinary polynomial
2392: according to a list of indeterminates @var{vlist}.
2393: @item
2394: @var{vlist} is such a list that its length coincides with the number of
2395: variables of @var{dpoly}.
2396: \E
1.1 noro 2397: @end itemize
2398:
2399: @example
2400: [53] T=dp_ptod((x+y+z)^2,[x,y]);
1.5 noro 2401: (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
2402: +(z^2)*<<0,0>>
1.1 noro 2403: [54] P=dp_dtop(T,[a,b]);
2404: z^2+(2*a+2*b)*z+a^2+2*b*a+b^2
2405: @end example
2406:
1.2 noro 2407: \JP @node dp_mod dp_rat,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2408: \EG @node dp_mod dp_rat,,, Functions for Groebner basis computation
1.1 noro 2409: @subsection @code{dp_mod}, @code{dp_rat}
2410: @findex dp_mod
2411: @findex dp_rat
2412:
2413: @table @t
2414: @item dp_mod(@var{p},@var{mod},@var{subst})
1.2 noro 2415: \JP :: $BM-M}?t78?tJ,;6I=8=B?9`<0$NM-8BBN78?t$X$NJQ49(B
2416: \EG :: Converts a disributed polynomial into one with coefficients in a finite field.
1.1 noro 2417: @item dp_rat(@var{p})
1.2 noro 2418: \JP :: $BM-8BBN78?tJ,;6I=8=B?9`<0$NM-M}?t78?t$X$NJQ49(B
2419: \BEG
2420: :: Converts a distributed polynomial with coefficients in a finite field into
2421: one with coefficients in the rationals.
2422: \E
1.1 noro 2423: @end table
2424:
2425: @table @var
2426: @item return
1.2 noro 2427: \JP $BJ,;6I=8=B?9`<0(B
2428: \EG distributed polynomial
1.1 noro 2429: @item p
1.2 noro 2430: \JP $BJ,;6I=8=B?9`<0(B
2431: \EG distributed polynomial
1.1 noro 2432: @item mod
1.2 noro 2433: \JP $BAG?t(B
2434: \EG prime
1.1 noro 2435: @item subst
1.2 noro 2436: \JP $B%j%9%H(B
2437: \EG list
1.1 noro 2438: @end table
2439:
2440: @itemize @bullet
1.2 noro 2441: \BJP
1.1 noro 2442: @item
2443: @code{dp_nf_mod()}, @code{dp_true_nf_mod()} $B$O(B, $BF~NO$H$7$FM-8BBN78?t$N(B
2444: $BJ,;6I=8=B?9`<0$rI,MW$H$9$k(B. $B$3$N$h$&$J>l9g(B, @code{dp_mod()} $B$K$h$j(B
2445: $BM-M}?t78?tJ,;6I=8=B?9`<0$rJQ49$7$FMQ$$$k$3$H$,$G$-$k(B. $B$^$?(B, $BF@$i$l$?(B
2446: $B7k2L$O(B, $BM-8BBN78?tB?9`<0$H$O1i;;$G$-$k$,(B, $BM-M}?t78?tB?9`<0$H$O1i;;$G$-$J$$(B
2447: $B$?$a(B, @code{dp_rat()} $B$K$h$jJQ49$9$kI,MW$,$"$k(B.
2448: @item
2449: $BM-8BBN78?t$N1i;;$K$*$$$F$O(B, $B$"$i$+$8$a(B @code{setmod()} $B$K$h$jM-8BBN$N85$N(B
2450: $B8D?t$r;XDj$7$F$*$/I,MW$,$"$k(B.
2451: @item
2452: @var{subst} $B$O(B, $B78?t$,M-M}<0$N>l9g(B, $B$=$NM-M}<0$NJQ?t$K$"$i$+$8$a?t$rBeF~(B
2453: $B$7$?8eM-8BBN78?t$KJQ49$9$k$H$$$&A`:n$r9T$&:]$N(B, $BBeF~CM$r;XDj$9$k$b$N$G(B,
2454: @code{[[@var{var},@var{value}],...]} $B$N7A$N%j%9%H$G$"$k(B.
1.2 noro 2455: \E
2456: \BEG
2457: @item
2458: @code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
2459: distributed polynomials with coefficients in a finite field as arguments.
2460: @code{dp_mod()} is used to convert distributed polynomials with rational
2461: number coefficients into appropriate ones.
2462: Polynomials with coefficients in a finite field
2463: cannot be used as inputs of operations with polynomials
2464: with rational number coefficients. @code{dp_rat()} is used for such cases.
2465: @item
2466: The ground finite field must be set in advance by using @code{setmod()}.
2467: @item
2468: @var{subst} is such a list as @code{[[@var{var},@var{value}],...]}.
2469: This is valid when the ground field of the input polynomial is a
2470: rational function field. @var{var}'s are variables in the ground field and
2471: the list means that @var{value} is substituted for @var{var} before
2472: converting the coefficients into elements of a finite field.
2473: \E
1.1 noro 2474: @end itemize
2475:
2476: @example
2477: @end example
2478:
2479: @table @t
1.2 noro 2480: \JP @item $B;2>H(B
2481: \EG @item References
1.1 noro 2482: @fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod},
2483: @fref{subst psubst},
2484: @fref{setmod}.
2485: @end table
2486:
1.2 noro 2487: \JP @node dp_homo dp_dehomo,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2488: \EG @node dp_homo dp_dehomo,,, Functions for Groebner basis computation
1.1 noro 2489: @subsection @code{dp_homo}, @code{dp_dehomo}
2490: @findex dp_homo
2491: @findex dp_dehomo
2492:
2493: @table @t
2494: @item dp_homo(@var{dpoly})
1.2 noro 2495: \JP :: $BJ,;6I=8=B?9`<0$N@F<!2=(B
2496: \EG :: Homogenize a distributed polynomial
1.1 noro 2497: @item dp_dehomo(@var{dpoly})
1.2 noro 2498: \JP :: $B@F<!J,;6I=8=B?9`<0$NHs@F<!2=(B
2499: \EG :: Dehomogenize a homogenious distributed polynomial
1.1 noro 2500: @end table
2501:
2502: @table @var
2503: @item return
1.2 noro 2504: \JP $BJ,;6I=8=B?9`<0(B
2505: \EG distributed polynomial
1.1 noro 2506: @item dpoly
1.2 noro 2507: \JP $BJ,;6I=8=B?9`<0(B
2508: \EG distributed polynomial
1.1 noro 2509: @end table
2510:
2511: @itemize @bullet
1.2 noro 2512: \BJP
1.1 noro 2513: @item
2514: @code{dp_homo()} $B$O(B, @var{dpoly} $B$N(B $B3F9`(B @var{t} $B$K$D$$$F(B, $B;X?t%Y%/%H%k$ND9$5$r(B
2515: 1 $B?-$P$7(B, $B:G8e$N@.J,$NCM$r(B @var{d}-@code{deg(@var{t})}
2516: (@var{d} $B$O(B @var{dpoly} $B$NA4<!?t(B) $B$H$7$?J,;6I=8=B?9`<0$rJV$9(B.
2517: @item
2518: @code{dp_dehomo()} $B$O(B, @var{dpoly} $B$N3F9`$K$D$$$F(B, $B;X?t%Y%/%H%k$N:G8e$N@.J,(B
2519: $B$r<h$j=|$$$?J,;6B?9`<0$rJV$9(B.
2520: @item
2521: $B$$$:$l$b(B, $B@8@.$5$l$?B?9`<0$rMQ$$$?1i;;$r9T$&>l9g(B, $B$=$l$i$KE,9g$9$k9`=g=x$r(B
2522: $B@5$7$/@_Dj$9$kI,MW$,$"$k(B.
2523: @item
2524: @code{hgr()} $B$J$I$K$*$$$F(B, $BFbItE*$KMQ$$$i$l$F$$$k(B.
1.2 noro 2525: \E
2526: \BEG
2527: @item
2528: @code{dp_homo()} makes a copy of @var{dpoly}, extends
2529: the length of the exponent vector of each term @var{t} in the copy by 1,
2530: and sets the value of the newly appended
2531: component to @var{d}-@code{deg(@var{t})}, where @var{d} is the total
2532: degree of @var{dpoly}.
2533: @item
2534: @code{dp_dehomo()} make a copy of @var{dpoly} and removes the last component
2535: of each terms in the copy.
2536: @item
2537: Appropriate term orderings must be set when the results are used as inputs
2538: of some operations.
2539: @item
2540: These are used internally in @code{hgr()} etc.
2541: \E
1.1 noro 2542: @end itemize
2543:
2544: @example
2545: [202] X=<<1,2,3>>+3*<<1,2,1>>;
2546: (1)*<<1,2,3>>+(3)*<<1,2,1>>
2547: [203] dp_homo(X);
2548: (1)*<<1,2,3,0>>+(3)*<<1,2,1,2>>
2549: [204] dp_dehomo(@@);
2550: (1)*<<1,2,3>>+(3)*<<1,2,1>>
2551: @end example
2552:
2553: @table @t
1.2 noro 2554: \JP @item $B;2>H(B
2555: \EG @item References
1.1 noro 2556: @fref{gr hgr gr_mod}.
2557: @end table
2558:
1.2 noro 2559: \JP @node dp_ptozp dp_prim,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2560: \EG @node dp_ptozp dp_prim,,, Functions for Groebner basis computation
1.1 noro 2561: @subsection @code{dp_ptozp}, @code{dp_prim}
2562: @findex dp_ptozp
2563: @findex dp_prim
2564:
2565: @table @t
2566: @item dp_ptozp(@var{dpoly})
1.2 noro 2567: \JP :: $BDj?tG\$7$F78?t$r@0?t78?t$+$D78?t$N@0?t(B GCD $B$r(B 1 $B$K$9$k(B.
2568: \BEG
2569: :: Converts a distributed polynomial @var{poly} with rational coefficients
2570: into an integral distributed polynomial such that GCD of all its coefficients
2571: is 1.
2572: \E
1.1 noro 2573: @itemx dp_prim(@var{dpoly})
1.2 noro 2574: \JP :: $BM-M}<0G\$7$F78?t$r@0?t78?tB?9`<078?t$+$D78?t$NB?9`<0(B GCD $B$r(B 1 $B$K$9$k(B.
2575: \BEG
2576: :: Converts a distributed polynomial @var{poly} with rational function
2577: coefficients into an integral distributed polynomial such that polynomial
2578: GCD of all its coefficients is 1.
2579: \E
1.1 noro 2580: @end table
2581:
2582: @table @var
2583: @item return
1.2 noro 2584: \JP $BJ,;6I=8=B?9`<0(B
2585: \EG distributed polynomial
1.1 noro 2586: @item dpoly
1.2 noro 2587: \JP $BJ,;6I=8=B?9`<0(B
2588: \EG distributed polynomial
1.1 noro 2589: @end table
2590:
2591: @itemize @bullet
1.2 noro 2592: \BJP
1.1 noro 2593: @item
2594: @code{dp_ptozp()} $B$O(B, @code{ptozp()} $B$KAjEv$9$kA`:n$rJ,;6I=8=B?9`<0$K(B
2595: $BBP$7$F9T$&(B. $B78?t$,B?9`<0$r4^$`>l9g(B, $B78?t$K4^$^$l$kB?9`<06&DL0x;R$O(B
2596: $B<h$j=|$+$J$$(B.
2597: @item
2598: @code{dp_prim()} $B$O(B, $B78?t$,B?9`<0$r4^$`>l9g(B, $B78?t$K4^$^$l$kB?9`<06&DL0x;R(B
2599: $B$r<h$j=|$/(B.
1.2 noro 2600: \E
2601: \BEG
2602: @item
2603: @code{dp_ptozp()} executes the same operation as @code{ptozp()} for
2604: a distributed polynomial. If the coefficients include polynomials,
2605: polynomial contents included in the coefficients are not removed.
2606: @item
2607: @code{dp_prim()} removes polynomial contents.
2608: \E
1.1 noro 2609: @end itemize
2610:
2611: @example
2612: [208] X=dp_ptod(3*(x-y)*(y-z)*(z-x),[x]);
2613: (-3*y+3*z)*<<2>>+(3*y^2-3*z^2)*<<1>>+(-3*z*y^2+3*z^2*y)*<<0>>
2614: [209] dp_ptozp(X);
2615: (-y+z)*<<2>>+(y^2-z^2)*<<1>>+(-z*y^2+z^2*y)*<<0>>
2616: [210] dp_prim(X);
2617: (1)*<<2>>+(-y-z)*<<1>>+(z*y)*<<0>>
2618: @end example
2619:
2620: @table @t
1.2 noro 2621: \JP @item $B;2>H(B
2622: \EG @item References
1.1 noro 2623: @fref{ptozp}.
2624: @end table
2625:
1.2 noro 2626: \JP @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2627: \EG @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod,,, Functions for Groebner basis computation
1.1 noro 2628: @subsection @code{dp_nf}, @code{dp_nf_mod}, @code{dp_true_nf}, @code{dp_true_nf_mod}
2629: @findex dp_nf
2630: @findex dp_true_nf
2631: @findex dp_nf_mod
2632: @findex dp_true_nf_mod
2633:
2634: @table @t
2635: @item dp_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
2636: @item dp_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
1.2 noro 2637: \JP :: $BJ,;6I=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B7k2L$ODj?tG\$5$l$F$$$k2DG=@-$"$j(B)
1.1 noro 2638:
1.2 noro 2639: \BEG
2640: :: Computes the normal form of a distributed polynomial.
2641: (The result may be multiplied by a constant in the ground field.)
2642: \E
1.1 noro 2643: @item dp_true_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
2644: @item dp_true_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
1.2 noro 2645: \JP :: $BJ,;6I=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B??$N7k2L$r(B @code{[$BJ,;R(B, $BJ,Jl(B]} $B$N7A$GJV$9(B)
2646: \BEG
2647: :: Computes the normal form of a distributed polynomial. (The true result
2648: is returned in such a list as @code{[numerator, denominator]})
2649: \E
1.1 noro 2650: @end table
2651:
2652: @table @var
2653: @item return
1.2 noro 2654: \JP @code{dp_nf()} : $BJ,;6I=8=B?9`<0(B, @code{dp_true_nf()} : $B%j%9%H(B
2655: \EG @code{dp_nf()} : distributed polynomial, @code{dp_true_nf()} : list
1.1 noro 2656: @item indexlist
1.2 noro 2657: \JP $B%j%9%H(B
2658: \EG list
1.1 noro 2659: @item dpoly
1.2 noro 2660: \JP $BJ,;6I=8=B?9`<0(B
2661: \EG distributed polynomial
1.1 noro 2662: @item dpolyarray
1.2 noro 2663: \JP $BG[Ns(B
2664: \EG array of distributed polynomial
1.1 noro 2665: @item fullreduce
1.2 noro 2666: \JP $B%U%i%0(B
2667: \EG flag
1.1 noro 2668: @item mod
1.2 noro 2669: \JP $BAG?t(B
2670: \EG prime
1.1 noro 2671: @end table
2672:
2673: @itemize @bullet
1.2 noro 2674: \BJP
1.1 noro 2675: @item
2676: $BJ,;6I=8=B?9`<0(B @var{dpoly} $B$N@55,7A$r5a$a$k(B.
2677: @item
2678: @code{dp_nf_mod()}, @code{dp_true_nf_mod()} $B$NF~NO$O(B, @code{dp_mod()} $B$J$I(B
2679: $B$K$h$j(B, $BM-8BBN>e$NJ,;6I=8=B?9`<0$K$J$C$F$$$J$1$l$P$J$i$J$$(B.
2680: @item
2681: $B7k2L$KM-M}?t(B, $BM-M}<0$,4^$^$l$k$N$rHr$1$k$?$a(B, @code{dp_nf()} $B$O(B
2682: $B??$NCM$NDj?tG\$NCM$rJV$9(B. $BM-M}<078?t$N>l9g$N(B @code{dp_nf_mod()} $B$bF1MM(B
2683: $B$G$"$k$,(B, $B78?tBN$,M-8BBN$N>l9g(B @code{dp_nf_mod()} $B$O??$NCM$rJV$9(B.
2684: @item
2685: @code{dp_true_nf()}, @code{dp_true_nf_mod()} $B$O(B,
2686: @code{[@var{nm},@var{dn}]} $B$J$k7A$N%j%9%H$rJV$9(B.
2687: $B$?$@$7(B, @var{nm} $B$O78?t$KJ,?t(B, $BM-M}<0$r4^$^$J$$J,;6I=8=B?9`<0(B, @var{dn} $B$O(B
2688: $B?t$^$?$OB?9`<0$G(B @var{nm}/@var{dn} $B$,??$NCM$H$J$k(B.
2689: @item
2690: @var{dpolyarray} $B$OJ,;6I=8=B?9`<0$rMWAG$H$9$k%Y%/%H%k(B,
2691: @var{indexlist} $B$O@55,2=7W;;$KMQ$$$k(B @var{dpolyarray} $B$NMWAG$N%$%s%G%C%/%9(B
2692: $B$N%j%9%H(B.
2693: @item
2694: @var{fullreduce} $B$,(B 0 $B$G$J$$$H$-A4$F$N9`$KBP$7$F4JLs$r9T$&(B. @var{fullreduce}
2695: $B$,(B 0 $B$N$H$-F,9`$N$_$KBP$7$F4JLs$r9T$&(B.
2696: @item
2697: @var{indexlist} $B$G;XDj$5$l$?B?9`<0$O(B, $BA0$NJ}$N$b$N$,M%@hE*$K;H$o$l$k(B.
2698: @item
2699: $B0lHL$K$O(B @var{indexlist} $B$NM?$(J}$K$h$jH!?t$NCM$O0[$J$k2DG=@-$,$"$k$,(B,
2700: $B%0%l%V%J4pDl$KBP$7$F$O0l0UE*$KDj$^$k(B.
2701: @item
2702: $BJ,;6I=8=$G$J$$8GDj$5$l$?B?9`<0=89g$K$h$k@55,7A$rB??t5a$a$kI,MW$,$"$k>l9g(B
2703: $B$KJXMx$G$"$k(B. $BC10l$N1i;;$K4X$7$F$O(B, @code{p_nf}, @code{p_true_nf} $B$r(B
2704: $BMQ$$$k$H$h$$(B.
1.2 noro 2705: \E
2706: \BEG
2707: @item
2708: Computes the normal form of a distributed polynomial.
2709: @item
2710: @code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
2711: distributed polynomials with coefficients in a finite field as arguments.
2712: @item
2713: The result of @code{dp_nf()} may be multiplied by a constant in the
2714: ground field in order to make the result integral. The same is true
2715: for @code{dp_nf_mod()}, but it returns the true normal form if
2716: the ground field is a finite field.
2717: @item
2718: @code{dp_true_nf()} and @code{dp_true_nf_mod()} return
2719: such a list as @code{[@var{nm},@var{dn}]}.
2720: Here @var{nm} is a distributed polynomial whose coefficients are integral
2721: in the ground field, @var{dn} is an integral element in the ground
2722: field and @var{nm}/@var{dn} is the true normal form.
2723: @item
2724: @var{dpolyarray} is a vector whose components are distributed polynomials
2725: and @var{indexlist} is a list of indices which is used for the normal form
2726: computation.
2727: @item
2728: When argument @var{fullreduce} has non-zero value,
2729: all terms are reduced. When it has value 0,
2730: only the head term is reduced.
2731: @item
2732: As for the polynomials specified by @var{indexlist}, one specified by
2733: an index placed at the preceding position has priority to be selected.
2734: @item
2735: In general, the result of the function may be different depending on
2736: @var{indexlist}. However, the result is unique for Groebner bases.
2737: @item
2738: These functions are useful when a fixed non-distributed polynomial set
2739: is used as a set of reducers to compute normal forms of many polynomials.
2740: For single computation @code{p_nf} and @code{p_true_nf} are sufficient.
2741: \E
1.1 noro 2742: @end itemize
2743:
2744: @example
2745: [0] load("gr")$
2746: [64] load("katsura")$
2747: [69] K=katsura(4)$
2748: [70] dp_ord(2)$
2749: [71] V=[u0,u1,u2,u3,u4]$
2750: [72] DP1=newvect(length(K),map(dp_ptod,K,V))$
2751: [73] G=gr(K,V,2)$
2752: [74] DP2=newvect(length(G),map(dp_ptod,G,V))$
2753: [75] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
2754: [76] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
1.5 noro 2755: u4^2+(6*u3+2*u2+6*u1-2)*u4+9*u3^2+(6*u2+18*u1-6)*u3+u2^2
2756: +(6*u1-2)*u2+9*u1^2-6*u1+1
1.1 noro 2757: [77] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
2758: -5*u4^2+(-4*u3-4*u2-4*u1)*u4-u3^2-3*u3-u2^2+(2*u1-1)*u2-2*u1^2-3*u1+1
2759: [78] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
1.5 noro 2760: -11380879768451657780886122972730785203470970010204714556333530492210
2761: 456775930005716505560062087150928400876150217079820311439477560587583
2762: 488*u4^15+...
1.1 noro 2763: [79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
1.5 noro 2764: -11380879768451657780886122972730785203470970010204714556333530492210
2765: 456775930005716505560062087150928400876150217079820311439477560587583
2766: 488*u4^15+...
1.1 noro 2767: [80] @@78==@@79;
2768: 1
2769: @end example
2770:
2771: @table @t
1.2 noro 2772: \JP @item $B;2>H(B
2773: \EG @item References
1.1 noro 2774: @fref{dp_dtop},
2775: @fref{dp_ord},
2776: @fref{dp_mod dp_rat},
2777: @fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
2778: @end table
2779:
1.2 noro 2780: \JP @node dp_hm dp_ht dp_hc dp_rest,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2781: \EG @node dp_hm dp_ht dp_hc dp_rest,,, Functions for Groebner basis computation
1.1 noro 2782: @subsection @code{dp_hm}, @code{dp_ht}, @code{dp_hc}, @code{dp_rest}
2783: @findex dp_hm
2784: @findex dp_ht
2785: @findex dp_hc
2786: @findex dp_rest
2787:
2788: @table @t
2789: @item dp_hm(@var{dpoly})
1.2 noro 2790: \JP :: $BF,C19`<0$r<h$j=P$9(B.
2791: \EG :: Gets the head monomial.
1.1 noro 2792: @item dp_ht(@var{dpoly})
1.2 noro 2793: \JP :: $BF,9`$r<h$j=P$9(B.
2794: \EG :: Gets the head term.
1.1 noro 2795: @item dp_hc(@var{dpoly})
1.2 noro 2796: \JP :: $BF,78?t$r<h$j=P$9(B.
2797: \EG :: Gets the head coefficient.
1.1 noro 2798: @item dp_rest(@var{dpoly})
1.2 noro 2799: \JP :: $BF,C19`<0$r<h$j=|$$$?;D$j$rJV$9(B.
2800: \EG :: Gets the remainder of the polynomial where the head monomial is removed.
1.1 noro 2801: @end table
2802:
2803: @table @var
1.2 noro 2804: \BJP
1.1 noro 2805: @item return
2806: @code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : $BJ,;6I=8=B?9`<0(B,
2807: @code{dp_hc()} : $B?t$^$?$OB?9`<0(B
2808: @item dpoly
2809: $BJ,;6I=8=B?9`<0(B
1.2 noro 2810: \E
2811: \BEG
2812: @item return
2813: @code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : distributed polynomial
2814: @code{dp_hc()} : number or polynomial
2815: @item dpoly
2816: distributed polynomial
2817: \E
1.1 noro 2818: @end table
2819:
2820: @itemize @bullet
1.2 noro 2821: \BJP
1.1 noro 2822: @item
2823: $B$3$l$i$O(B, $BJ,;6I=8=B?9`<0$N3FItJ,$r<h$j=P$9$?$a$NH!?t$G$"$k(B.
2824: @item
2825: $BJ,;6I=8=B?9`<0(B @var{p} $B$KBP$7<!$,@.$jN)$D(B.
1.2 noro 2826: \E
2827: \BEG
2828: @item
2829: These are used to get various parts of a distributed polynomial.
2830: @item
2831: The next equations hold for a distributed polynomial @var{p}.
2832: \E
1.1 noro 2833: @table @code
2834: @item @var{p} = dp_hm(@var{p}) + dp_rest(@var{p})
2835: @item dp_hm(@var{p}) = dp_hc(@var{p}) dp_ht(@var{p})
2836: @end table
2837: @end itemize
2838:
2839: @example
2840: [87] dp_ord(0)$
2841: [88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
2842: [89] T=dp_ptod(X,[u3,u4,a46])$
2843: [90] dp_hm(T);
2844: (2160)*<<4,0,2>>
2845: [91] dp_ht(T);
2846: (1)*<<4,0,2>>
2847: [92] dp_hc(T);
2848: 2160
2849: [93] dp_rest(T);
2850: (1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
2851: +(-490)*<<0,0,0>>
2852: @end example
2853:
1.2 noro 2854: \JP @node dp_td dp_sugar,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2855: \EG @node dp_td dp_sugar,,, Functions for Groebner basis computation
1.1 noro 2856: @subsection @code{dp_td}, @code{dp_sugar}
2857: @findex dp_td
2858: @findex dp_sugar
2859:
2860: @table @t
2861: @item dp_td(@var{dpoly})
1.2 noro 2862: \JP :: $BF,9`$NA4<!?t$rJV$9(B.
2863: \EG :: Gets the total degree of the head term.
1.1 noro 2864: @item dp_sugar(@var{dpoly})
1.2 noro 2865: \JP :: $BB?9`<0$N(B @code{sugar} $B$rJV$9(B.
2866: \EG :: Gets the @code{sugar} of a polynomial.
1.1 noro 2867: @end table
2868:
2869: @table @var
2870: @item return
1.2 noro 2871: \JP $B<+A3?t(B
2872: \EG non-negative integer
1.1 noro 2873: @item dpoly
1.2 noro 2874: \JP $BJ,;6I=8=B?9`<0(B
2875: \EG distributed polynomial
1.1 noro 2876: @item onoff
1.2 noro 2877: \JP $B%U%i%0(B
2878: \EG flag
1.1 noro 2879: @end table
2880:
2881: @itemize @bullet
1.2 noro 2882: \BJP
1.1 noro 2883: @item
2884: @code{dp_td()} $B$O(B, $BF,9`$NA4<!?t(B, $B$9$J$o$A3FJQ?t$N;X?t$NOB$rJV$9(B.
2885: @item
2886: $BJ,;6I=8=B?9`<0$,@8@.$5$l$k$H(B, @code{sugar} $B$H8F$P$l$k$"$k@0?t$,IUM?(B
2887: $B$5$l$k(B. $B$3$NCM$O(B $B2>A[E*$K@F<!2=$7$F7W;;$7$?>l9g$K7k2L$,;}$DA4<!?t$NCM$H$J$k(B.
2888: @item
2889: @code{sugar} $B$O(B, $B%0%l%V%J4pDl7W;;$K$*$1$k@55,2=BP$NA*Br$N%9%H%i%F%8$r(B
2890: $B7hDj$9$k$?$a$N=EMW$J;X?K$H$J$k(B.
1.2 noro 2891: \E
2892: \BEG
2893: @item
2894: Function @code{dp_td()} returns the total degree of the head term,
2895: i.e., the sum of all exponent of variables in that term.
2896: @item
2897: Upon creation of a distributed polynomial, an integer called @code{sugar}
2898: is associated. This value is
2899: the total degree of the virtually homogenized one of the original
2900: polynomial.
2901: @item
2902: The quantity @code{sugar} is an important guide to determine the
2903: selection strategy of critical pairs in Groebner basis computation.
2904: \E
1.1 noro 2905: @end itemize
2906:
2907: @example
2908: [74] dp_ord(0)$
2909: [75] X=<<1,2>>+<<0,1>>$
2910: [76] Y=<<1,2>>+<<1,0>>$
2911: [77] Z=X-Y;
2912: (-1)*<<1,0>>+(1)*<<0,1>>
2913: [78] dp_sugar(T);
2914: 3
2915: @end example
2916:
1.2 noro 2917: \JP @node dp_lcm,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2918: \EG @node dp_lcm,,, Functions for Groebner basis computation
1.1 noro 2919: @subsection @code{dp_lcm}
2920: @findex dp_lcm
2921:
2922: @table @t
2923: @item dp_lcm(@var{dpoly1},@var{dpoly2})
1.2 noro 2924: \JP :: $B:G>.8xG\9`$rJV$9(B.
2925: \EG :: Returns the least common multiple of the head terms of the given two polynomials.
1.1 noro 2926: @end table
2927:
2928: @table @var
2929: @item return
1.2 noro 2930: \JP $BJ,;6I=8=B?9`<0(B
2931: \EG distributed polynomial
1.4 noro 2932: @item dpoly1 dpoly2
1.2 noro 2933: \JP $BJ,;6I=8=B?9`<0(B
2934: \EG distributed polynomial
1.1 noro 2935: @end table
2936:
2937: @itemize @bullet
1.2 noro 2938: \BJP
1.1 noro 2939: @item
2940: $B$=$l$>$l$N0z?t$NF,9`$N:G>.8xG\9`$rJV$9(B. $B78?t$O(B 1 $B$G$"$k(B.
1.2 noro 2941: \E
2942: \BEG
2943: @item
2944: Returns the least common multiple of the head terms of the given
2945: two polynomials, where coefficient is always set to 1.
2946: \E
1.1 noro 2947: @end itemize
2948:
2949: @example
2950: [100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
2951: (1)*<<5,4,3,4,5>>
2952: @end example
2953:
2954: @table @t
1.2 noro 2955: \JP @item $B;2>H(B
2956: \EG @item References
1.1 noro 2957: @fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
2958: @end table
2959:
1.2 noro 2960: \JP @node dp_redble,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
2961: \EG @node dp_redble,,, Functions for Groebner basis computation
1.1 noro 2962: @subsection @code{dp_redble}
2963: @findex dp_redble
2964:
2965: @table @t
2966: @item dp_redble(@var{dpoly1},@var{dpoly2})
1.2 noro 2967: \JP :: $BF,9`$I$&$7$,@0=|2DG=$+$I$&$+D4$Y$k(B.
2968: \EG :: Checks whether one head term is divisible by the other head term.
1.1 noro 2969: @end table
2970:
2971: @table @var
2972: @item return
1.2 noro 2973: \JP $B@0?t(B
2974: \EG integer
1.4 noro 2975: @item dpoly1 dpoly2
1.2 noro 2976: \JP $BJ,;6I=8=B?9`<0(B
2977: \EG distributed polynomial
1.1 noro 2978: @end table
2979:
2980: @itemize @bullet
1.2 noro 2981: \BJP
1.1 noro 2982: @item
2983: @var{dpoly1} $B$NF,9`$,(B @var{dpoly2} $B$NF,9`$G3d$j@Z$l$l$P(B 1, $B3d$j@Z$l$J$1$l$P(B
2984: 0 $B$rJV$9(B.
2985: @item
2986: $BB?9`<0$N4JLs$r9T$&:](B, $B$I$N9`$r4JLs$G$-$k$+$rC5$9$N$KMQ$$$k(B.
1.2 noro 2987: \E
2988: \BEG
2989: @item
2990: Returns 1 if the head term of @var{dpoly2} divides the head term of
2991: @var{dpoly1}; otherwise 0.
2992: @item
2993: Used for finding candidate terms at reduction of polynomials.
2994: \E
1.1 noro 2995: @end itemize
2996:
2997: @example
2998: [148] C;
2999: (1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
3000: [149] T;
3001: (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
3002: [150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
3003: 0
3004: 0
3005: 0
3006: 1
3007: @end example
3008:
3009: @table @t
1.2 noro 3010: \JP @item $B;2>H(B
3011: \EG @item References
1.1 noro 3012: @fref{dp_red dp_red_mod}.
3013: @end table
3014:
1.2 noro 3015: \JP @node dp_subd,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3016: \EG @node dp_subd,,, Functions for Groebner basis computation
1.1 noro 3017: @subsection @code{dp_subd}
3018: @findex dp_subd
3019:
3020: @table @t
3021: @item dp_subd(@var{dpoly1},@var{dpoly2})
1.2 noro 3022: \JP :: $BF,9`$N>&C19`<0$rJV$9(B.
3023: \EG :: Returns the quotient monomial of the head terms.
1.1 noro 3024: @end table
3025:
3026: @table @var
3027: @item return
1.2 noro 3028: \JP $BJ,;6I=8=B?9`<0(B
3029: \EG distributed polynomial
1.4 noro 3030: @item dpoly1 dpoly2
1.2 noro 3031: \JP $BJ,;6I=8=B?9`<0(B
3032: \EG distributed polynomial
1.1 noro 3033: @end table
3034:
3035: @itemize @bullet
1.2 noro 3036: \BJP
1.1 noro 3037: @item
3038: @code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})} $B$r5a$a$k(B. $B7k2L$N78?t$O(B 1
3039: $B$G$"$k(B.
3040: @item
3041: $B3d$j@Z$l$k$3$H$,$"$i$+$8$a$o$+$C$F$$$kI,MW$,$"$k(B.
1.2 noro 3042: \E
3043: \BEG
3044: @item
3045: Gets @code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})}.
3046: The coefficient of the result is always set to 1.
3047: @item
3048: Divisibility assumed.
3049: \E
1.1 noro 3050: @end itemize
3051:
3052: @example
3053: [162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
3054: (1)*<<0,1,1,1,1>>
3055: @end example
3056:
3057: @table @t
1.2 noro 3058: \JP @item $B;2>H(B
3059: \EG @item References
1.1 noro 3060: @fref{dp_red dp_red_mod}.
3061: @end table
3062:
1.2 noro 3063: \JP @node dp_vtoe dp_etov,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3064: \EG @node dp_vtoe dp_etov,,, Functions for Groebner basis computation
1.1 noro 3065: @subsection @code{dp_vtoe}, @code{dp_etov}
3066: @findex dp_vtoe
3067: @findex dp_etov
3068:
3069: @table @t
3070: @item dp_vtoe(@var{vect})
1.2 noro 3071: \JP :: $B;X?t%Y%/%H%k$r9`$KJQ49(B
3072: \EG :: Converts an exponent vector into a term.
1.1 noro 3073: @item dp_etov(@var{dpoly})
1.2 noro 3074: \JP :: $BF,9`$r;X?t%Y%/%H%k$KJQ49(B
3075: \EG :: Convert the head term of a distributed polynomial into an exponent vector.
1.1 noro 3076: @end table
3077:
3078: @table @var
3079: @item return
1.2 noro 3080: \JP @code{dp_vtoe} : $BJ,;6I=8=B?9`<0(B, @code{dp_etov} : $B%Y%/%H%k(B
3081: \EG @code{dp_vtoe} : distributed polynomial, @code{dp_etov} : vector
1.1 noro 3082: @item vect
1.2 noro 3083: \JP $B%Y%/%H%k(B
3084: \EG vector
1.1 noro 3085: @item dpoly
1.2 noro 3086: \JP $BJ,;6I=8=B?9`<0(B
3087: \EG distributed polynomial
1.1 noro 3088: @end table
3089:
3090: @itemize @bullet
1.2 noro 3091: \BJP
1.1 noro 3092: @item
3093: @code{dp_vtoe()} $B$O(B, $B%Y%/%H%k(B @var{vect} $B$r;X?t%Y%/%H%k$H$9$k9`$r@8@.$9$k(B.
3094: @item
3095: @code{dp_etov()} $B$O(B, $BJ,;6I=8=B?9`<0(B @code{dpoly} $B$NF,9`$N;X?t%Y%/%H%k$r(B
3096: $B%Y%/%H%k$KJQ49$9$k(B.
1.2 noro 3097: \E
3098: \BEG
3099: @item
3100: @code{dp_vtoe()} generates a term whose exponent vector is @var{vect}.
3101: @item
3102: @code{dp_etov()} generates a vector which is the exponent vector of the
3103: head term of @code{dpoly}.
3104: \E
1.1 noro 3105: @end itemize
3106:
3107: @example
3108: [211] X=<<1,2,3>>;
3109: (1)*<<1,2,3>>
3110: [212] V=dp_etov(X);
3111: [ 1 2 3 ]
3112: [213] V[2]++$
3113: [214] Y=dp_vtoe(V);
3114: (1)*<<1,2,4>>
3115: @end example
3116:
1.2 noro 3117: \JP @node dp_mbase,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3118: \EG @node dp_mbase,,, Functions for Groebner basis computation
1.1 noro 3119: @subsection @code{dp_mbase}
3120: @findex dp_mbase
3121:
3122: @table @t
3123: @item dp_mbase(@var{dplist})
1.2 noro 3124: \JP :: monomial $B4pDl$N7W;;(B
3125: \EG :: Computes the monomial basis
1.1 noro 3126: @end table
3127:
3128: @table @var
3129: @item return
1.2 noro 3130: \JP $BJ,;6I=8=B?9`<0$N%j%9%H(B
3131: \EG list of distributed polynomial
1.1 noro 3132: @item dplist
1.2 noro 3133: \JP $BJ,;6I=8=B?9`<0$N%j%9%H(B
3134: \EG list of distributed polynomial
1.1 noro 3135: @end table
3136:
3137: @itemize @bullet
1.2 noro 3138: \BJP
1.1 noro 3139: @item
3140: $B$"$k=g=x$G%0%l%V%J4pDl$H$J$C$F$$$kB?9`<0=89g$N(B, $B$=$N=g=x$K4X$9$kJ,;6I=8=(B
3141: $B$G$"$k(B @var{dplist} $B$K$D$$$F(B,
3142: @var{dplist} $B$,(B K[X] $BCf$G@8@.$9$k%$%G%"%k(B I $B$,(B 0 $B<!85$N;~(B,
3143: K $B>eM-8B<!85@~7A6u4V$G$"$k(B K[X]/I $B$N(B monomial $B$K$h$k4pDl$r5a$a$k(B.
3144: @item
3145: $BF@$i$l$?4pDl$N8D?t$,(B, K[X]/I $B$N(B K-$B@~7A6u4V$H$7$F$N<!85$KEy$7$$(B.
1.2 noro 3146: \E
3147: \BEG
3148: @item
3149: Assuming that @var{dplist} is a list of distributed polynomials which
3150: is a Groebner basis with respect to the current ordering type and
3151: that the ideal @var{I} generated by @var{dplist} in K[X] is zero-dimensional,
3152: this function computes the monomial basis of a finite dimenstional K-vector
3153: space K[X]/I.
3154: @item
3155: The number of elements in the monomial basis is equal to the
3156: K-dimenstion of K[X]/I.
3157: \E
1.1 noro 3158: @end itemize
3159:
3160: @example
3161: [215] K=katsura(5)$
3162: [216] V=[u5,u4,u3,u2,u1,u0]$
3163: [217] G0=gr(K,V,0)$
3164: [218] H=map(dp_ptod,G0,V)$
3165: [219] map(dp_ptod,dp_mbase(H),V)$
3166: [u0^5,u4*u0^3,u3*u0^3,u2*u0^3,u1*u0^3,u0^4,u3^2*u0,u2*u3*u0,u1*u3*u0,
3167: u1*u2*u0,u1^2*u0,u4*u0^2,u3*u0^2,u2*u0^2,u1*u0^2,u0^3,u3^2,u2*u3,u1*u3,
3168: u1*u2,u1^2,u4*u0,u3*u0,u2*u0,u1*u0,u0^2,u4,u3,u2,u1,u0,1]
3169: @end example
3170:
3171: @table @t
1.2 noro 3172: \JP @item $B;2>H(B
3173: \EG @item References
1.1 noro 3174: @fref{gr hgr gr_mod}.
3175: @end table
3176:
1.2 noro 3177: \JP @node dp_mag,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3178: \EG @node dp_mag,,, Functions for Groebner basis computation
1.1 noro 3179: @subsection @code{dp_mag}
3180: @findex dp_mag
3181:
3182: @table @t
3183: @item dp_mag(@var{p})
1.2 noro 3184: \JP :: $B78?t$N%S%C%HD9$NOB$rJV$9(B
3185: \EG :: Computes the sum of bit lengths of coefficients of a distributed polynomial.
1.1 noro 3186: @end table
3187:
3188: @table @var
3189: @item return
1.2 noro 3190: \JP $B?t(B
3191: \EG integer
1.1 noro 3192: @item p
1.2 noro 3193: \JP $BJ,;6I=8=B?9`<0(B
3194: \EG distributed polynomial
1.1 noro 3195: @end table
3196:
3197: @itemize @bullet
1.2 noro 3198: \BJP
1.1 noro 3199: @item
3200: $BJ,;6I=8=B?9`<0$N78?t$K8=$l$kM-M}?t$K$D$-(B, $B$=$NJ,JlJ,;R(B ($B@0?t$N>l9g$OJ,;R(B)
3201: $B$N%S%C%HD9$NAmOB$rJV$9(B.
3202: @item
3203: $BBP>]$H$J$kB?9`<0$NBg$-$5$NL\0B$H$7$FM-8z$G$"$k(B. $BFC$K(B, 0 $B<!85%7%9%F%`$K$*$$$F$O(B
3204: $B78?tKDD%$,LdBj$H$J$j(B, $BESCf@8@.$5$l$kB?9`<0$,78?tKDD%$r5/$3$7$F$$$k$+$I$&$+(B
3205: $B$NH=Dj$KLrN)$D(B.
3206: @item
3207: @code{dp_gr_flags()} $B$G(B, @code{ShowMag}, @code{Print} $B$r(B on $B$K$9$k$3$H$K$h$j(B
3208: $BESCf@8@.$5$l$kB?9`<0$K$?$$$9$k(B @code{dp_mag()} $B$NCM$r8+$k$3$H$,$G$-$k(B.
1.2 noro 3209: \E
3210: \BEG
3211: @item
3212: This function computes the sum of bit lengths of coefficients of a
3213: distributed polynomial @var{p}. If a coefficient is non integral,
3214: the sum of bit lengths of the numerator and the denominator is taken.
3215: @item
3216: This is a measure of the size of a polynomial. Especially for
3217: zero-dimensional system coefficient swells are often serious and
3218: the returned value is useful to detect such swells.
3219: @item
3220: If @code{ShowMag} and @code{Print} for @code{dp_gr_flags()} are on,
3221: values of @code{dp_mag()} for intermediate basis elements are shown.
3222: \E
1.1 noro 3223: @end itemize
3224:
3225: @example
3226: [221] X=dp_ptod((x+2*y)^10,[x,y])$
3227: [222] dp_mag(X);
3228: 115
3229: @end example
3230:
3231: @table @t
1.2 noro 3232: \JP @item $B;2>H(B
3233: \EG @item References
1.1 noro 3234: @fref{dp_gr_flags dp_gr_print}.
3235: @end table
3236:
1.2 noro 3237: \JP @node dp_red dp_red_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3238: \EG @node dp_red dp_red_mod,,, Functions for Groebner basis computation
1.1 noro 3239: @subsection @code{dp_red}, @code{dp_red_mod}
3240: @findex dp_red
3241: @findex dp_red_mod
3242:
3243: @table @t
3244: @item dp_red(@var{dpoly1},@var{dpoly2},@var{dpoly3})
3245: @item dp_red_mod(@var{dpoly1},@var{dpoly2},@var{dpoly3},@var{mod})
1.2 noro 3246: \JP :: $B0l2s$N4JLsA`:n(B
3247: \EG :: Single reduction operation
1.1 noro 3248: @end table
3249:
3250: @table @var
3251: @item return
1.2 noro 3252: \JP $B%j%9%H(B
3253: \EG list
1.4 noro 3254: @item dpoly1 dpoly2 dpoly3
1.2 noro 3255: \JP $BJ,;6I=8=B?9`<0(B
3256: \EG distributed polynomial
1.1 noro 3257: @item vlist
1.2 noro 3258: \JP $B%j%9%H(B
3259: \EG list
1.1 noro 3260: @item mod
1.2 noro 3261: \JP $BAG?t(B
3262: \EG prime
1.1 noro 3263: @end table
3264:
3265: @itemize @bullet
1.2 noro 3266: \BJP
1.1 noro 3267: @item
3268: @var{dpoly1} + @var{dpoly2} $B$J$kJ,;6I=8=B?9`<0$r(B @var{dpoly3} $B$G(B
3269: 1 $B2s4JLs$9$k(B.
3270: @item
3271: @code{dp_red_mod()} $B$NF~NO$O(B, $BA4$FM-8BBN78?t$KJQ49$5$l$F$$$kI,MW$,$"$k(B.
3272: @item
3273: $B4JLs$5$l$k9`$O(B @var{dpoly2} $B$NF,9`$G$"$k(B. $B=>$C$F(B, @var{dpoly2} $B$N(B
3274: $BF,9`$,(B @var{dpoly3} $B$NF,9`$G3d$j@Z$l$k$3$H$,$"$i$+$8$a$o$+$C$F$$$J$1$l$P(B
3275: $B$J$i$J$$(B.
3276: @item
3277: $B0z?t$,@0?t78?t$N;~(B, $B4JLs$O(B, $BJ,?t$,8=$l$J$$$h$&(B, $B@0?t(B @var{a}, @var{b},
1.4 noro 3278: $B9`(B @var{t} $B$K$h$j(B @var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3} $B$H$7$F7W;;$5$l$k(B.
1.1 noro 3279: @item
3280: $B7k2L$O(B, @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]} $B$J$k%j%9%H$G$"$k(B.
1.2 noro 3281: \E
3282: \BEG
3283: @item
3284: Reduces a distributed polynomial, @var{dpoly1} + @var{dpoly2},
3285: by @var{dpoly3} for single time.
3286: @item
3287: An input for @code{dp_red_mod()} must be converted into a distributed
3288: polynomial with coefficients in a finite field.
3289: @item
3290: This implies that
3291: the divisibility of the head term of @var{dpoly2} by the head term of
3292: @var{dpoly3} is assumed.
3293: @item
3294: When integral coefficients, computation is so carefully performed that
3295: no rational operations appear in the reduction procedure.
3296: It is computed for integers @var{a} and @var{b}, and a term @var{t} as:
1.4 noro 3297: @var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3}.
1.2 noro 3298: @item
3299: The result is a list @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]}.
3300: \E
1.1 noro 3301: @end itemize
3302:
3303: @example
3304: [157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
3305: (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
3306: [158] R=(6)*<<1,1,1,0,0>>;
3307: (6)*<<1,1,1,0,0>>
3308: [159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>;
3309: (12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
3310: [160] dp_red(D,R,C);
1.5 noro 3311: [(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,
3312: (-1)*<<0,1,1,1,0>>+(-1)*<<1,1,0,0,1>>]
1.1 noro 3313: @end example
3314:
3315: @table @t
1.2 noro 3316: \JP @item $B;2>H(B
3317: \EG @item References
1.1 noro 3318: @fref{dp_mod dp_rat}.
3319: @end table
3320:
1.2 noro 3321: \JP @node dp_sp dp_sp_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3322: \EG @node dp_sp dp_sp_mod,,, Functions for Groebner basis computation
1.1 noro 3323: @subsection @code{dp_sp}, @code{dp_sp_mod}
3324: @findex dp_sp
3325: @findex dp_sp_mod
3326:
3327: @table @t
3328: @item dp_sp(@var{dpoly1},@var{dpoly2})
3329: @item dp_sp_mod(@var{dpoly1},@var{dpoly2},@var{mod})
1.2 noro 3330: \JP :: S-$BB?9`<0$N7W;;(B
3331: \EG :: Computation of an S-polynomial
1.1 noro 3332: @end table
3333:
3334: @table @var
3335: @item return
1.2 noro 3336: \JP $BJ,;6I=8=B?9`<0(B
3337: \EG distributed polynomial
1.4 noro 3338: @item dpoly1 dpoly2
1.2 noro 3339: \JP $BJ,;6I=8=B?9`<0(B
3340: \EG distributed polynomial
1.1 noro 3341: @item mod
1.2 noro 3342: \JP $BAG?t(B
3343: \EG prime
1.1 noro 3344: @end table
3345:
3346: @itemize @bullet
1.2 noro 3347: \BJP
1.1 noro 3348: @item
3349: @var{dpoly1}, @var{dpoly2} $B$N(B S-$BB?9`<0$r7W;;$9$k(B.
3350: @item
3351: @code{dp_sp_mod()} $B$NF~NO$O(B, $BA4$FM-8BBN78?t$KJQ49$5$l$F$$$kI,MW$,$"$k(B.
3352: @item
3353: $B7k2L$KM-M}?t(B, $BM-M}<0$,F~$k$N$rHr$1$k$?$a(B, $B7k2L$,Dj?tG\(B, $B$"$k$$$OB?9`<0(B
3354: $BG\$5$l$F$$$k2DG=@-$,$"$k(B.
1.2 noro 3355: \E
3356: \BEG
3357: @item
3358: This function computes the S-polynomial of @var{dpoly1} and @var{dpoly2}.
3359: @item
3360: Inputs of @code{dp_sp_mod()} must be polynomials with coefficients in a
3361: finite field.
3362: @item
3363: The result may be multiplied by a constant in the ground field in order to
3364: make the result integral.
3365: \E
1.1 noro 3366: @end itemize
3367:
3368: @example
3369: [227] X=dp_ptod(x^2*y+x*y,[x,y]);
3370: (1)*<<2,1>>+(1)*<<1,1>>
3371: [228] Y=dp_ptod(x*y^2+x*y,[x,y]);
3372: (1)*<<1,2>>+(1)*<<1,1>>
3373: [229] dp_sp(X,Y);
3374: (-1)*<<2,1>>+(1)*<<1,2>>
3375: @end example
3376:
3377: @table @t
1.2 noro 3378: \JP @item $B;2>H(B
3379: \EG @item References
1.1 noro 3380: @fref{dp_mod dp_rat}.
3381: @end table
1.2 noro 3382: \JP @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3383: \EG @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, Functions for Groebner basis computation
1.1 noro 3384: @subsection @code{p_nf}, @code{p_nf_mod}, @code{p_true_nf}, @code{p_true_nf_mod}
3385: @findex p_nf
3386: @findex p_nf_mod
3387: @findex p_true_nf
3388: @findex p_true_nf_mod
3389:
3390: @table @t
3391: @item p_nf(@var{poly},@var{plist},@var{vlist},@var{order})
3392: @itemx p_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
1.2 noro 3393: \JP :: $BI=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B7k2L$ODj?tG\$5$l$F$$$k2DG=@-$"$j(B)
3394: \BEG
3395: :: Computes the normal form of the given polynomial.
3396: (The result may be multiplied by a constant.)
3397: \E
1.1 noro 3398: @item p_true_nf(@var{poly},@var{plist},@var{vlist},@var{order})
3399: @itemx p_true_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
1.2 noro 3400: \JP :: $BI=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B??$N7k2L$r(B @code{[$BJ,;R(B, $BJ,Jl(B]} $B$N7A$GJV$9(B)
3401: \BEG
3402: :: Computes the normal form of the given polynomial. (The result is returned
3403: as a form of @code{[numerator, denominator]})
3404: \E
1.1 noro 3405: @end table
3406:
3407: @table @var
3408: @item return
1.2 noro 3409: \JP @code{p_nf} : $BB?9`<0(B, @code{p_true_nf} : $B%j%9%H(B
3410: \EG @code{p_nf} : polynomial, @code{p_true_nf} : list
1.1 noro 3411: @item poly
1.2 noro 3412: \JP $BB?9`<0(B
3413: \EG polynomial
1.4 noro 3414: @item plist vlist
1.2 noro 3415: \JP $B%j%9%H(B
3416: \EG list
1.1 noro 3417: @item order
1.2 noro 3418: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
3419: \EG number, list or matrix
1.1 noro 3420: @item mod
1.2 noro 3421: \JP $BAG?t(B
3422: \EG prime
1.1 noro 3423: @end table
3424:
3425: @itemize @bullet
1.2 noro 3426: \BJP
1.1 noro 3427: @item
3428: @samp{gr} $B$GDj5A$5$l$F$$$k(B.
3429: @item
3430: $BB?9`<0$N(B, $BB?9`<0%j%9%H$K$h$k@55,7A$r5a$a$k(B.
3431: @item
3432: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()}, @code{dp_true_nf_mod}
3433: $B$KBP$9$k%$%s%?%U%'!<%9$G$"$k(B.
3434: @item
3435: @var{poly} $B$*$h$S(B @var{plist} $B$O(B, $BJQ?t=g=x(B @var{vlist} $B$*$h$S(B
3436: $BJQ?t=g=x7?(B @var{otype} $B$K=>$C$FJ,;6I=8=B?9`<0$KJQ49$5$l(B,
3437: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
3438: @code{dp_true_nf_mod()} $B$KEO$5$l$k(B.
3439: @item
3440: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
3441: @code{dp_true_nf_mod()} $B$O(B @var{fullreduce} $B$,(B 1 $B$G8F$S=P$5$l$k(B.
3442: @item
3443: $B7k2L$OB?9`<0$KJQ49$5$l$F=PNO$5$l$k(B.
3444: @item
3445: @code{p_true_nf()}, @code{p_true_nf_mod()} $B$N=PNO$K4X$7$F$O(B,
3446: @code{dp_true_nf()}, @code{dp_true_nf_mod()} $B$N9`$r;2>H(B.
1.2 noro 3447: \E
3448: \BEG
3449: @item
3450: Defined in the package @samp{gr}.
3451: @item
3452: Obtains the normal form of a polynomial by a polynomial list.
3453: @item
3454: These are interfaces to @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
3455: @code{dp_true_nf_mod}
3456: @item
3457: The polynomial @var{poly} and the polynomials in @var{plist} is
3458: converted, according to the variable ordering @var{vlist} and
3459: type of term ordering @var{otype}, into their distributed polynomial
3460: counterparts and passed to @code{dp_nf()}.
3461: @item
3462: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()} and
3463: @code{dp_true_nf_mod()}
3464: is called with value 1 for @var{fullreduce}.
3465: @item
3466: The result is converted back into an ordinary polynomial.
3467: @item
3468: As for @code{p_true_nf()}, @code{p_true_nf_mod()}
3469: refer to @code{dp_true_nf()} and @code{dp_true_nf_mod()}.
3470: \E
1.1 noro 3471: @end itemize
3472:
3473: @example
3474: [79] K = katsura(5)$
3475: [80] V = [u5,u4,u3,u2,u1,u0]$
3476: [81] G = hgr(K,V,2)$
3477: [82] p_nf(K[1],G,V,2);
3478: 0
3479: [83] L = p_true_nf(K[1]+1,G,V,2);
3480: [-1503...,-1503...]
3481: [84] L[0]/L[1];
3482: 1
3483: @end example
3484:
3485: @table @t
1.2 noro 3486: \JP @item $B;2>H(B
3487: \EG @item References
1.1 noro 3488: @fref{dp_ptod},
3489: @fref{dp_dtop},
3490: @fref{dp_ord},
3491: @fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod}.
3492: @end table
3493:
1.2 noro 3494: \JP @node p_terms,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3495: \EG @node p_terms,,, Functions for Groebner basis computation
1.1 noro 3496: @subsection @code{p_terms}
3497: @findex p_terms
3498:
3499: @table @t
3500: @item p_terms(@var{poly},@var{vlist},@var{order})
1.2 noro 3501: \JP :: $BB?9`<0$K$"$i$o$l$kC19`$r%j%9%H$K$9$k(B.
3502: \EG :: Monomials appearing in the given polynomial is collected into a list.
1.1 noro 3503: @end table
3504:
3505: @table @var
3506: @item return
1.2 noro 3507: \JP $B%j%9%H(B
3508: \EG list
1.1 noro 3509: @item poly
1.2 noro 3510: \JP $BB?9`<0(B
3511: \EG polynomial
1.1 noro 3512: @item vlist
1.2 noro 3513: \JP $B%j%9%H(B
3514: \EG list
1.1 noro 3515: @item order
1.2 noro 3516: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
3517: \EG number, list or matrix
1.1 noro 3518: @end table
3519:
3520: @itemize @bullet
1.2 noro 3521: \BJP
1.1 noro 3522: @item
3523: @samp{gr} $B$GDj5A$5$l$F$$$k(B.
3524: @item
3525: $BB?9`<0$rC19`$KE83+$7$?;~$K8=$l$k9`$r%j%9%H$K$7$FJV$9(B.
3526: @var{vlist} $B$*$h$S(B @var{order} $B$K$h$jDj$^$k9`=g=x$K$h$j(B, $B=g=x$N9b$$$b$N(B
3527: $B$,%j%9%H$N@hF,$KMh$k$h$&$K%=!<%H$5$l$k(B.
3528: @item
3529: $B%0%l%V%J4pDl$O$7$P$7$P78?t$,5pBg$K$J$k$?$a(B, $B<B:]$K$I$N9`$,8=$l$F(B
3530: $B$$$k$N$+$r8+$k$?$a$J$I$KMQ$$$k(B.
1.2 noro 3531: \E
3532: \BEG
3533: @item
3534: Defined in the package @samp{gr}.
3535: @item
3536: This returns a list which contains all non-zero monomials in the given
3537: polynomial. The monomials are ordered according to the current
3538: type of term ordering and @var{vlist}.
3539: @item
3540: Since polynomials in a Groebner base often have very large coefficients,
3541: examining a polynomial as it is may sometimes be difficult to perform.
3542: For such a case, this function enables to examine which term is really
3543: exists.
3544: \E
1.1 noro 3545: @end itemize
3546:
3547: @example
3548: [233] G=gr(katsura(5),[u5,u4,u3,u2,u1,u0],2)$
3549: [234] p_terms(G[0],[u5,u4,u3,u2,u1,u0],2);
1.5 noro 3550: [u5,u0^31,u0^30,u0^29,u0^28,u0^27,u0^26,u0^25,u0^24,u0^23,u0^22,
3551: u0^21,u0^20,u0^19,u0^18,u0^17,u0^16,u0^15,u0^14,u0^13,u0^12,u0^11,
3552: u0^10,u0^9,u0^8,u0^7,u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]
1.1 noro 3553: @end example
3554:
1.2 noro 3555: \JP @node gb_comp,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3556: \EG @node gb_comp,,, Functions for Groebner basis computation
1.1 noro 3557: @subsection @code{gb_comp}
3558: @findex gb_comp
3559:
3560: @table @t
3561: @item gb_comp(@var{plist1}, @var{plist2})
1.2 noro 3562: \JP :: $BB?9`<0%j%9%H$,(B, $BId9f$r=|$$$F=89g$H$7$FEy$7$$$+$I$&$+D4$Y$k(B.
3563: \EG :: Checks whether two polynomial lists are equal or not as a set
1.1 noro 3564: @end table
3565:
3566: @table @var
1.2 noro 3567: \JP @item return 0 $B$^$?$O(B 1
3568: \EG @item return 0 or 1
1.4 noro 3569: @item plist1 plist2
1.1 noro 3570: @end table
3571:
3572: @itemize @bullet
1.2 noro 3573: \BJP
1.1 noro 3574: @item
3575: @var{plist1}, @var{plist2} $B$K$D$$$F(B, $BId9f$r=|$$$F=89g$H$7$FEy$7$$$+$I$&$+(B
3576: $BD4$Y$k(B.
3577: @item
3578: $B0[$J$kJ}K!$G5a$a$?%0%l%V%J4pDl$O(B, $B4pDl$N=g=x(B, $BId9f$,0[$J$k>l9g$,$"$j(B,
3579: $B$=$l$i$,Ey$7$$$+$I$&$+$rD4$Y$k$?$a$KMQ$$$k(B.
1.2 noro 3580: \E
3581: \BEG
3582: @item
3583: This function checks whether @var{plist1} and @var{plist2} are equal or
3584: not as a set .
3585: @item
3586: For the same input and the same term ordering different
3587: functions for Groebner basis computations may produce different outputs
3588: as lists. This function compares such lists whether they are equal
3589: as a generating set of an ideal.
3590: \E
1.1 noro 3591: @end itemize
3592:
3593: @example
3594: [243] C=cyclic(6)$
3595: [244] V=[c0,c1,c2,c3,c4,c5]$
3596: [245] G0=gr(C,V,0)$
3597: [246] G=tolex(G0,V,0,V)$
3598: [247] GG=lex_tl(C,V,0,V,0)$
3599: [248] gb_comp(G,GG);
3600: 1
3601: @end example
3602:
1.2 noro 3603: \JP @node katsura hkatsura cyclic hcyclic,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3604: \EG @node katsura hkatsura cyclic hcyclic,,, Functions for Groebner basis computation
1.1 noro 3605: @subsection @code{katsura}, @code{hkatsura}, @code{cyclic}, @code{hcyclic}
3606: @findex katsura
3607: @findex hkatsura
3608: @findex cyclic
3609: @findex hcyclic
3610:
3611: @table @t
3612: @item katsura(@var{n})
3613: @item hkatsura(@var{n})
3614: @item cyclic(@var{n})
3615: @item hcyclic(@var{n})
1.2 noro 3616: \JP :: $BB?9`<0%j%9%H$N@8@.(B
3617: \EG :: Generates a polynomial list of standard benchmark.
1.1 noro 3618: @end table
3619:
3620: @table @var
3621: @item return
1.2 noro 3622: \JP $B%j%9%H(B
3623: \EG list
1.1 noro 3624: @item n
1.2 noro 3625: \JP $B@0?t(B
3626: \EG integer
1.1 noro 3627: @end table
3628:
3629: @itemize @bullet
1.2 noro 3630: \BJP
1.1 noro 3631: @item
3632: @code{katsura()} $B$O(B @samp{katsura}, @code{cyclic()} $B$O(B @samp{cyclic}
3633: $B$GDj5A$5$l$F$$$k(B.
3634: @item
3635: $B%0%l%V%J4pDl7W;;$G$7$P$7$P%F%9%H(B, $B%Y%s%A%^!<%/$KMQ$$$i$l$k(B @code{katsura},
3636: @code{cyclic} $B$*$h$S$=$N@F<!2=$r@8@.$9$k(B.
3637: @item
3638: @code{cyclic} $B$O(B @code{Arnborg}, @code{Lazard}, @code{Davenport} $B$J$I$N(B
3639: $BL>$G8F$P$l$k$3$H$b$"$k(B.
1.2 noro 3640: \E
3641: \BEG
3642: @item
3643: Function @code{katsura()} is defined in @samp{katsura}, and
3644: function @code{cyclic()} in @samp{cyclic}.
3645: @item
3646: These functions generate a series of polynomial sets, respectively,
3647: which are often used for testing and bench marking:
3648: @code{katsura}, @code{cyclic} and their homogenized versions.
3649: @item
3650: Polynomial set @code{cyclic} is sometimes called by other name:
3651: @code{Arnborg}, @code{Lazard}, and @code{Davenport}.
3652: \E
1.1 noro 3653: @end itemize
3654:
3655: @example
3656: [74] load("katsura")$
3657: [79] load("cyclic")$
3658: [89] katsura(5);
3659: [u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
1.5 noro 3660: 2*u3*u0+2*u1*u4-u3+(2*u1+2*u5)*u2,2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3
3661: -u2+u1^2,2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
1.1 noro 3662: u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
3663: [90] hkatsura(5);
3664: [-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
3665: -u4*t+2*u4*u0+2*u1*u3+u2^2+2*u5*u1,-u3*t+2*u3*u0+2*u1*u4+(2*u1+2*u5)*u2,
3666: -u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
3667: -u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
3668: -u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
3669: [91] cyclic(6);
3670: [c5*c4*c3*c2*c1*c0-1,
3671: ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
3672: (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
3673: ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
3674: (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
3675: [92] hcyclic(6);
3676: [-c^6+c5*c4*c3*c2*c1*c0,
3677: ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
3678: (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
3679: ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
3680: (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
3681: @end example
3682:
3683: @table @t
1.2 noro 3684: \JP @item $B;2>H(B
3685: \EG @item References
1.1 noro 3686: @fref{dp_dtop}.
3687: @end table
3688:
1.3 noro 3689: \JP @node primadec primedec,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3690: \EG @node primadec primedec,,, Functions for Groebner basis computation
3691: @subsection @code{primadec}, @code{primedec}
3692: @findex primadec
3693: @findex primedec
3694:
3695: @table @t
3696: @item primadec(@var{plist},@var{vlist})
3697: @item primedec(@var{plist},@var{vlist})
3698: \JP :: $B%$%G%"%k$NJ,2r(B
3699: \EG :: Computes decompositions of ideals.
3700: @end table
3701:
3702: @table @var
3703: @item return
3704: @itemx plist
3705: \JP $BB?9`<0%j%9%H(B
3706: \EG list of polynomials
3707: @item vlist
3708: \JP $BJQ?t%j%9%H(B
3709: \EG list of variables
3710: @end table
3711:
3712: @itemize @bullet
3713: \BJP
3714: @item
3715: @code{primadec()}, @code{primedec} $B$O(B @samp{primdec} $B$GDj5A$5$l$F$$$k(B.
3716: @item
3717: @code{primadec()}, @code{primedec()} $B$O$=$l$>$lM-M}?tBN>e$G$N%$%G%"%k$N(B
3718: $B=`AGJ,2r(B, $B:,4p$NAG%$%G%"%kJ,2r$r9T$&(B.
3719: @item
3720: $B0z?t$OB?9`<0%j%9%H$*$h$SJQ?t%j%9%H$G$"$k(B. $BB?9`<0$OM-M}?t78?t$N$_$,5v$5$l$k(B.
3721: @item
3722: @code{primadec} $B$O(B @code{[$B=`AG@.J,(B, $BIUB0AG%$%G%"%k(B]} $B$N%j%9%H$rJV$9(B.
3723: @item
3724: @code{primadec} $B$O(B $BAG0x;R$N%j%9%H$rJV$9(B.
3725: @item
3726: $B7k2L$K$*$$$F(B, $BB?9`<0%j%9%H$H$7$FI=<($5$l$F$$$k3F%$%G%"%k$OA4$F(B
3727: $B%0%l%V%J4pDl$G$"$k(B. $BBP1~$9$k9`=g=x$O(B, $B$=$l$>$l(B
3728: $BJQ?t(B @code{PRIMAORD}, @code{PRIMEORD} $B$K3JG<$5$l$F$$$k(B.
3729: @item
3730: @code{primadec} $B$O(B @code{[Shimoyama,Yokoyama]} $B$N=`AGJ,2r%"%k%4%j%:%`(B
3731: $B$r<BAu$7$F$$$k(B.
3732: @item
3733: $B$b$7AG0x;R$N$_$r5a$a$?$$$J$i(B, @code{primedec} $B$r;H$&J}$,$h$$(B.
3734: $B$3$l$O(B, $BF~NO%$%G%"%k$,:,4p%$%G%"%k$G$J$$>l9g$K(B, @code{primadec}
3735: $B$N7W;;$KM>J,$J%3%9%H$,I,MW$H$J$k>l9g$,$"$k$+$i$G$"$k(B.
3736: \E
3737: \BEG
3738: @item
3739: Function @code{primadec()} and @code{primedec} are defined in @samp{primdec}.
3740: @item
3741: @code{primadec()}, @code{primedec()} are the function for primary
3742: ideal decomposition and prime decomposition of the radical over the
3743: rationals respectively.
3744: @item
3745: The arguments are a list of polynomials and a list of variables.
3746: These functions accept ideals with rational function coefficients only.
3747: @item
3748: @code{primadec} returns the list of pair lists consisting a primary component
3749: and its associated prime.
3750: @item
3751: @code{primedec} returns the list of prime components.
3752: @item
3753: Each component is a Groebner basis and the corresponding term order
3754: is indicated by the global variables @code{PRIMAORD}, @code{PRIMEORD}
3755: respectively.
3756: @item
3757: @code{primadec} implements the primary decompostion algorithm
3758: in @code{[Shimoyama,Yokoyama]}.
3759: @item
3760: If one only wants to know the prime components of an ideal, then
3761: use @code{primedec} because @code{primadec} may need additional costs
3762: if an input ideal is not radical.
3763: \E
3764: @end itemize
3765:
3766: @example
3767: [84] load("primdec")$
3768: [102] primedec([p*q*x-q^2*y^2+q^2*y,-p^2*x^2+p^2*x+p*q*y,
3769: (q^3*y^4-2*q^3*y^3+q^3*y^2)*x-q^3*y^4+q^3*y^3,
3770: -q^3*y^4+2*q^3*y^3+(-q^3+p*q^2)*y^2],[p,q,x,y]);
3771: [[y,x],[y,p],[x,q],[q,p],[x-1,q],[y-1,p],[(y-1)*x-y,q*y^2-2*q*y-p+q]]
3772: [103] primadec([x,z*y,w*y^2,w^2*y-z^3,y^3],[x,y,z,w]);
3773: [[[x,z*y,y^2,w^2*y-z^3],[z,y,x]],[[w,x,z*y,z^3,y^3],[w,z,y,x]]]
3774: @end example
3775:
3776: @table @t
3777: \JP @item $B;2>H(B
3778: \EG @item References
3779: @fref{fctr sqfr},
3780: \JP @fref{$B9`=g=x$N@_Dj(B}.
3781: \EG @fref{Setting term orderings}.
3782: @end table
1.5 noro 3783:
3784: \JP @node primedec_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
3785: \EG @node primedec_mod,,, Functions for Groebner basis computation
3786: @subsection @code{primedec_mod}
3787: @findex primedec_mod
3788:
3789: @table @t
3790: @item primedec_mod(@var{plist},@var{vlist},@var{ord},@var{mod},@var{strategy})
3791: \JP :: $B%$%G%"%k$NJ,2r(B
3792: \EG :: Computes decompositions of ideals over small finite fields.
3793: @end table
3794:
3795: @table @var
3796: @item return
3797: @itemx plist
3798: \JP $BB?9`<0%j%9%H(B
3799: \EG list of polynomials
3800: @item vlist
3801: \JP $BJQ?t%j%9%H(B
3802: \EG list of variables
3803: @item ord
3804: \JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
3805: \EG number, list or matrix
3806: @item mod
3807: \JP $B@5@0?t(B
3808: \EG positive integer
3809: @item strategy
3810: \JP $B@0?t(B
3811: \EG integer
3812: @end table
3813:
3814: @itemize @bullet
3815: \BJP
3816: @item
3817: @code{primedec_mod()} $B$O(B @samp{primdec_mod}
3818: $B$GDj5A$5$l$F$$$k(B. @code{[Yokoyama]} $B$NAG%$%G%"%kJ,2r%"%k%4%j%:%`(B
3819: $B$r<BAu$7$F$$$k(B.
3820: @item
3821: @code{primedec_mod()} $B$OM-8BBN>e$G$N%$%G%"%k$N(B
3822: $B:,4p$NAG%$%G%"%kJ,2r$r9T$$(B, $BAG%$%G%"%k$N%j%9%H$rJV$9(B.
3823: @item
3824: @code{primedec_mod()} $B$O(B, GF(@var{mod}) $B>e$G$NJ,2r$rM?$($k(B.
3825: $B7k2L$N3F@.J,$N@8@.85$O(B, $B@0?t78?tB?9`<0$G$"$k(B.
3826: @item
3827: $B7k2L$K$*$$$F(B, $BB?9`<0%j%9%H$H$7$FI=<($5$l$F$$$k3F%$%G%"%k$OA4$F(B
3828: [@var{vlist},@var{ord}] $B$G;XDj$5$l$k9`=g=x$K4X$9$k%0%l%V%J4pDl$G$"$k(B.
3829: @item
3830: @var{strategy} $B$,(B 0 $B$G$J$$$H$-(B, incremental $B$K(B component $B$N6&DL(B
3831: $BItJ,$r7W;;$9$k$3$H$K$h$k(B early termination $B$r9T$&(B. $B0lHL$K(B,
3832: $B%$%G%"%k$N<!85$,9b$$>l9g$KM-8z$@$,(B, 0 $B<!85$N>l9g$J$I(B, $B<!85$,>.$5$$(B
3833: $B>l9g$K$O(B overhead $B$,Bg$-$$>l9g$,$"$k(B.
3834: \E
3835: \BEG
3836: @item
3837: Function @code{primedec_mod()}
3838: is defined in @samp{primdec_mod} and implements the prime decomposition
3839: algorithm in @code{[Yokoyama]}.
3840: @item
3841: @code{primedec_mod()}
3842: is the function for prime ideal decomposition
3843: of the radical of a polynomial ideal over small finite field,
3844: and they return a list of prime ideals, which are associated primes
3845: of the input ideal.
3846: @item
3847: @code{primedec_mod()} gives the decomposition over GF(@var{mod}).
3848: The generators of each resulting component consists of integral polynomials.
3849: @item
3850: Each resulting component is a Groebner basis with respect to
3851: a term order specified by [@var{vlist},@var{ord}].
3852: @item
3853: If @var{strategy} is non zero, then the early termination strategy
3854: is tried by computing the intersection of obtained components
3855: incrementally. In general, this strategy is useful when the krull
3856: dimension of the ideal is high, but it may add some overhead
3857: if the dimension is small.
3858: \E
3859: @end itemize
3860:
3861: @example
3862: [0] load("primdec_mod")$
3863: [246] PP444=[x^8+x^2+t,y^8+y^2+t,z^8+z^2+t]$
3864: [247] primedec_mod(PP444,[x,y,z,t],0,2,1);
3865: [[y+z,x+z,z^8+z^2+t],[x+y,y^2+y+z^2+z+1,z^8+z^2+t],
3866: [y+z+1,x+z+1,z^8+z^2+t],[x+z,y^2+y+z^2+z+1,z^8+z^2+t],
3867: [y+z,x^2+x+z^2+z+1,z^8+z^2+t],[y+z+1,x^2+x+z^2+z+1,z^8+z^2+t],
3868: [x+z+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z+1,x+z,z^8+z^2+t],
3869: [x+y+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z,x+z+1,z^8+z^2+t]]
3870: [248]
3871: @end example
3872:
3873: @table @t
3874: \JP @item $B;2>H(B
3875: \EG @item References
3876: @fref{modfctr},
1.6 ! noro 3877: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.5 noro 3878: \JP @fref{$B9`=g=x$N@_Dj(B}.
3879: \EG @fref{Setting term orderings}.
3880: @end table
3881:
1.6 ! noro 3882: \JP @node bfunction generic_bfct,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
! 3883: \EG @node bfunction generic_bfct,,, Functions for Groebner basis computation
! 3884: @subsection @code{bfunction}, @code{generic_bfct}
! 3885: @findex bfunction
! 3886: @findex generic_bfct
1.5 noro 3887:
1.6 ! noro 3888: @table @t
! 3889: @item bfunction(@var{f})
! 3890: @item generic_bfct(@var{plist},@var{vlist},@var{dvlist},@var{weight})
! 3891: \JP :: b $B4X?t$N7W;;(B
! 3892: \EG :: Computes the global b function of a polynomial or an ideal
! 3893: @end table
! 3894: @table @var
! 3895: @item return
! 3896: @itemx f
! 3897: \JP $BB?9`<0(B
! 3898: \EG polynomial
! 3899: @item plist
! 3900: \JP $BB?9`<0%j%9%H(B
! 3901: \EG list of polynomials
! 3902: @item vlist dvlist
! 3903: \JP $BJQ?t%j%9%H(B
! 3904: \EG list of variables
! 3905: @end table
1.5 noro 3906:
1.6 ! noro 3907: @itemize @bullet
! 3908: \BJP
! 3909: @item @samp{bfct} $B$GDj5A$5$l$F$$$k(B.
! 3910: @item @code{bfunction(@var{f})} $B$OB?9`<0(B @var{f} $B$N(B global b $B4X?t(B @code{b(s)} $B$r(B
! 3911: $B7W;;$9$k(B. @code{b(s)} $B$O(B, Weyl $BBe?t(B @code{D} $B>e$N0lJQ?tB?9`<04D(B @code{D[s]}
! 3912: $B$N85(B @code{P(x,s)} $B$,B8:_$7$F(B, @code{P(x,s)f^(s+1)=b(s)f^s} $B$rK~$?$9$h$&$J(B
! 3913: $BB?9`<0(B @code{b(s)} $B$NCf$G(B, $B<!?t$,:G$bDc$$$b$N$G$"$k(B.
! 3914: @item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
! 3915: $B$O(B, @var{plist} $B$G@8@.$5$l$k(B @code{D} $B$N:8%$%G%"%k(B @code{I} $B$N(B,
! 3916: $B%&%'%$%H(B @var{weight} $B$K4X$9$k(B global b $B4X?t$r7W;;$9$k(B.
! 3917: @var{vlist} $B$O(B @code{x}-$BJQ?t(B, @var{vlist} $B$OBP1~$9$k(B @code{D}-$BJQ?t(B
! 3918: $B$r=g$KJB$Y$k(B.
! 3919: @item $B>\:Y$K$D$$$F$O(B, [SST] $B$r8+$h(B.
! 3920: \E
! 3921: \BEG
! 3922: @item These functions are defined in @samp{bfct}.
! 3923: @item @code{bfunction(@var{f})} computes the global b-function @code{b(s)} of
! 3924: a polynomial @var{f}.
! 3925: @code{b(s)} is a polynomial of the minimal degree
! 3926: such that there exists @code{P(x,s)} in D[s], which is a polynomial
! 3927: ring over Weyl algebra @code{D}, and @code{P(x,s)f^(s+1)=b(s)f^s} holds.
! 3928: @item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
! 3929: computes the global b-function of a left ideal @code{I} in @code{D}
! 3930: generated by @var{plist}, with respect to @var{weight}.
! 3931: @var{vlist} is the list of @code{x}-variables,
! 3932: @var{vlist} is the list of corresponding @code{D}-variables.
! 3933: @item See [SST] for the details.
! 3934: \E
! 3935: @end itemize
! 3936:
! 3937: @example
! 3938: [0] load("bfct")$
! 3939: [216] bfunction(x^3+y^3+z^3+x^2*y^2*z^2+x*y*z);
! 3940: -9*s^5-63*s^4-173*s^3-233*s^2-154*s-40
! 3941: [217] fctr(@@);
! 3942: [[-1,1],[s+2,1],[3*s+4,1],[3*s+5,1],[s+1,2]]
! 3943: [218] F = [4*x^3*dt+y*z*dt+dx,x*z*dt+4*y^3*dt+dy,
! 3944: x*y*dt+5*z^4*dt+dz,-x^4-z*y*x-y^4-z^5+t]$
! 3945: [219] generic_bfct(F,[t,z,y,x],[dt,dz,dy,dx],[1,0,0,0]);
! 3946: 20000*s^10-70000*s^9+101750*s^8-79375*s^7+35768*s^6-9277*s^5
! 3947: +1278*s^4-72*s^3
! 3948: @end example
! 3949:
! 3950: @table @t
! 3951: \JP @item $B;2>H(B
! 3952: \EG @item References
! 3953: \JP @fref{Weyl $BBe?t(B}.
! 3954: \EG @fref{Weyl algebra}.
! 3955: @end table
1.5 noro 3956:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to groebner.texi CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / asir-doc / parts