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