OpenXM/src/asir-doc/parts/groebner.texi - view

Return to groebner.texi CVS log

Up to [local] / OpenXM / src / asir-doc / parts

File: [local] / OpenXM / src / asir-doc / parts / groebner.texi (download)

Revision 1.9, Thu Apr 24 08:13:24 2003 UTC (21 years, 1 month ago) by noro
Branch: MAIN
Changes since 1.8: +13 -7 lines

Added description of bfct().

@comment $OpenXM: OpenXM/src/asir-doc/parts/groebner.texi,v 1.9 2003/04/24 08:13:24 noro Exp $
\BJP
@node $B%0%l%V%J4pDl$N7W;;(B,,, Top
@chapter $B%0%l%V%J4pDl$N7W;;(B
\E
\BEG
@node Groebner basis computation,,, Top
@chapter Groebner basis computation
\E

@menu
\BJP
* $BJ,;6I=8=B?9`<0(B::
* $B%U%!%$%k$NFI$_9~$_(B::
* $B4pK\E*$JH!?t(B::
* $B7W;;$*$h$SI=<($N@)8f(B::
* $B9`=g=x$N@_Dj(B::
* $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B::
* $B4pDlJQ49(B::
* Weyl $BBe?t(B::
* $B%0%l%V%J4pDl$K4X$9$kH!?t(B::
\E
\BEG
* Distributed polynomial:: 
* Reading files::
* Fundamental functions::
* Controlling Groebner basis computations::
* Setting term orderings::
* Groebner basis computation with rational function coefficients::
* Change of ordering::
* Weyl algebra::
* Functions for Groebner basis computation::
\E
@end menu

\BJP
@node $BJ,;6I=8=B?9`<0(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $BJ,;6I=8=B?9`<0(B
\E
\BEG
@node Distributed polynomial,,, Groebner basis computation
@section Distributed polynomial
\E

@noindent
\BJP
$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 
(@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
$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
$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, 
$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.
\E
\BEG
A distributed polynomial is a polynomial with a special internal
representation different from the ordinary one.
      
An ordinary polynomial (having @code{type} 2) is internally represented
in a format, called recursive representation.
In fact, it is represented as an uni-variate polynomial with respect to
a fixed variable, called main variable of that polynomial,
where the other variables appear in the coefficients which may again
polynomials in such variables other than the previous main variable.
A polynomial in the coefficients is again represented as
an uni-variate polynomial in a certain fixed variable,
the main variable.  Thus, by this recursive structure of polynomial
representation, it is called the `recursive representation.'
\E

@iftex
@tex
\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 ))$
\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 ))$
@end tex
@end iftex
@ifinfo
@example
(x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))
@end example
@end ifinfo

@noindent
\BJP
$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
$BI=8=$H8F$V(B. 
\E
\BEG
On the other hand,
we call a representation the distributed representation of a polynomial,
if a polynomial is represented, according to its original meaning,
as a sum of monomials,
where a monomial is the product of power product of variables
and a coefficient.  We call a polynomial, represented in such an
internal format, a distributed polynomial. (This naming may sounds
something strange.)
\E

@iftex
@tex
\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$
\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$
@end tex
@end iftex
@ifinfo
@example
(x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$
@end example
@end ifinfo

@noindent
\BJP
$B%0%l%V%J4pDl7W;;$K$*$$$F$O(B, $BC19`<0$KCmL\$7$FA`:n$r9T$&$?$aB?9`<0$,J,;6I=8=(B
$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, 
$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. 
$B$3$3$G(B, $B8e$N@bL@$N$?$a$K(B, $B$$$/$D$+$N8@MU$rDj5A$7$F$*$/(B. 
\E
\BEG
For computation of Groebner basis, efficient operation is expected if
polynomials are represented in a distributed representation,
because major operations for Groebner basis are performed with respect
to monomials.
From this view point, we provide the object type distributed polynomial
with its object identification number 9, and objects having such a type
are available by @b{Asir} language.
      
Here, we provide several definitions for the later description.
\E

@table @b
\BJP
@item $B9`(B (term)
$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, 
\E
\BEG
@item term
The power product of variables, i.e., a monomial with coefficient 1.
In an @b{Asir} session, it is displayed in the form like
\E

@example
<<0,1,2,3,4>>
@end example

\BJP
$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
$B$r<($9(B. $B3FJQ?t$r(B @code{a}, @code{b}, @code{c}, @code{d}, @code{e} $B$H$9$k$H(B
$B$3$N9`$O(B @code{b*c^2*d^3*e^4} $B$rI=$9(B. 
\E
\BEG
and also can be input in such a form.
This example shows a term in 5 variables.  If we assume the 5 variables
as @code{a}, @code{b}, @code{c}, @code{d}, and @code{e},
the term represents @code{b*c^2*d^3*e^4} in the ordinary expression.
\E

\BJP
@item $B9`=g=x(B (term order)
$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. 
\E
\BEG
@item term order
Terms are ordered according to a total order with the following properties.
\E

@enumerate
@item
\JP $BG$0U$N9`(B @code{t} $B$KBP$7(B @code{t} > 1
\EG For all @code{t} @code{t} > 1.

@item
\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}
\EG For all @code{t}, @code{s}, @code{u} @code{t} > @code{s} implies @code{tu} > @code{su}.
@end enumerate

\BJP
$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) 
$B$H9`=g=x7?(B ($B?t(B, $B%j%9%H$^$?$O9TNs(B) $B$K$h$j;XDj$5$l$k(B.
\E
\BEG
Such a total order is called a term ordering. A term ordering is specified
by a variable ordering (a list of variables) and a type of term ordering
(an integer, a list or a matrix).
\E

\BJP
@item $BC19`<0(B (monomial)
$B9`$H78?t$N@Q(B. 
\E
\BEG
@item monomial
The product of a term and a coefficient.
In an @b{Asir} session, it is displayed in the form like
\E

@example
2*<<0,1,2,3,4>>
@end example

\JP $B$H$$$&7A$GI=<($5$l(B, $B$^$?(B, $B$3$N7A$GF~NO2DG=$G$"$k(B. 
\EG and also can be input in such a form.

\BJP
@itemx $BF,C19`<0(B (head monomial)
@item $BF,9`(B (head term)
@itemx $BF,78?t(B (head coefficient)
$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
$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
$B$H8F$V(B. 
\E
\BEG
@itemx head monomial
@item head term
@itemx head coefficient
      
Monomials in a distributed polynomial is sorted by a total order.
In such representation, we call the monomial that is maximum
with respect to the order the head monomial, and its term and coefficient
the head term and the head coefficient respectively.
\E
@end table

\BJP
@node $B%U%!%$%k$NFI$_9~$_(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B%U%!%$%k$NFI$_9~$_(B
\E
\BEG
@node Reading files,,, Groebner basis computation
@section Reading files
\E

@noindent
\BJP
$B%0%l%V%J4pDl$r7W;;$9$k$?$a$N4pK\E*$JH!?t$O(B @code{dp_gr_main()} $B$*$h$S(B
@code{dp_gr_mod_main()}, @code{dp_gr_f_main()}
 $B$J$k(B 3 $B$D$NAH$_9~$_H!?t$G$"$k$,(B, $BDL>o$O(B, $B%Q%i%a%?(B
$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. 
$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
$B$_9~$`$3$H$K$h$j;HMQ2DG=$H$J$k(B. @samp{gr} $B$O(B, @b{Asir} $B$NI8=`(B
$B%i%$%V%i%j%G%#%l%/%H%j$KCV$+$l$F$$$k(B. 
\E
\BEG
Facilities for computing Groebner bases are 
@code{dp_gr_main()}, @code{dp_gr_mod_main()}and @code{dp_gr_f_main()}.
To call these functions, 
it is necessary to set several parameters correctly and it is convenient
to use a set of interface functions provided in the library file
@samp{gr}.
The facilities will be ready to use after you load the package by
@code{load()}.  The package @samp{gr} is placed in the standard library
directory of @b{Asir}.  
\E

@example
[0] load("gr")$
@end example

\BJP
@node $B4pK\E*$JH!?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B4pK\E*$JH!?t(B
\E
\BEG
@node Fundamental functions,,, Groebner basis computation
@section Fundamental functions
\E

@noindent
\BJP
@samp{gr} $B$G$O?tB?$/$NH!?t$,Dj5A$5$l$F$$$k$,(B, $BD>@\(B
$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. 
$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, 
@var{order} $B$OJQ?t=g=x7?(B, @var{p} $B$O(B @code{2^27} $BL$K~$NAG?t$G$"$k(B. 
\E
\BEG
There are many functions and options defined in the package @samp{gr}.
Usually not so many of them are used.  Top level functions for Groebner
basis computation are the following three functions.
      
In the following description, @var{plist}, @var{vlist}, @var{order}
and @var{p} stand for  a list of polynomials,  a list of variables
(indeterminates), a type of term ordering and a prime less than
@code{2^27} respectively.
\E

@table @code
@item gr(@var{plist},@var{vlist},@var{order})

\BJP
Gebauer-Moeller $B$K$h$k(B useless pair elimination criteria, sugar
strategy $B$*$h$S(B Traverso $B$K$h$k(B trace-lifting $B$rMQ$$$?(B Buchberger $B%"%k(B
$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.
\E
\BEG
Function that computes Groebner bases over the rationals. The
algorithm is Buchberger algorithm with useless pair elimination
criteria by Gebauer-Moeller, sugar strategy and trace-lifting by
Traverso. For ordinary computation, this function is used.
\E

@item hgr(@var{plist},@var{vlist},@var{order})

\BJP
$BF~NOB?9`<0$r@F<!2=$7$?8e(B @code{gr()} $B$N%0%l%V%J4pDl8uJd@8@.It$K$h$j8u(B
$BJd@8@.$7(B, $BHs@F<!2=(B, interreduce $B$7$?$b$N$r(B @code{gr()} $B$N%0%l%V%J4pDl(B
$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) 
$B$N>l9g(B, sugar strategy $B$,78?tKDD%$r0z$-5/$3$9>l9g$,$"$k(B. $B$3$N$h$&$J>l(B
$B9g(B, strategy $B$r@F<!2=$K$h$k(B strategy $B$KCV$-49$($k$3$H$K$h$j78?tKDD%$r(B
$BM^@)$9$k$3$H$,$G$-$k>l9g$,B?$$(B.
\E
\BEG
After homogenizing the input polynomials a candidate of the \gr basis
is computed by trace-lifting. Then the candidate is dehomogenized and
checked whether it is indeed a Groebner basis of the input.  Sugar
strategy often causes intermediate coefficient swells.  It is
empirically known that the combination of homogenization and supresses
the swells for such cases.
\E

@item gr_mod(@var{plist},@var{vlist},@var{order},@var{p})

\BJP
Gebauer-Moeller $B$K$h$k(B useless pair elimination criteria, sugar
strategy $B$*$h$S(B Buchberger $B%"%k%4%j%:%`$K$h$k(B GF(p) $B78?t%0%l%V%J4pDl7W(B
$B;;H!?t(B.
\E
\BEG
Function that computes Groebner bases over GF(@var{p}). The same
algorithm as @code{gr()} is used.
\E

@end table

\BJP
@node $B7W;;$*$h$SI=<($N@)8f(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B7W;;$*$h$SI=<($N@)8f(B
\E
\BEG
@node Controlling Groebner basis computations,,, Groebner basis computation
@section Controlling Groebner basis computations
\E

@noindent
\BJP
$B%0%l%V%J4pDl$N7W;;$K$*$$$F(B, $B$5$^$6$^$J%Q%i%a%?@_Dj$r9T$&$3$H$K$h$j7W;;(B, 
$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()}
$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
$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. 
\E
\BEG
One can cotrol a Groebner basis computation by setting various parameters.
These parameters can be set and examined by a built-in function
@code{dp_gr_flags()}. Without argument it returns the current settings.
\E

@example
[100] dp_gr_flags();
[Demand,0,NoSugar,0,NoCriB,0,NoGC,0,NoMC,0,NoRA,0,NoGCD,0,Top,0,
ShowMag,1,Print,1,Stat,0,Reverse,0,InterReduce,0,Multiple,0]
[101]
@end example

\BJP
$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
$B$$$&(B. $B$3$l$i$N%Q%i%a%?$N=i4|CM$OA4$F(B 0 (off) $B$G$"$k(B. 
\E
\BEG
The return value is a list which contains the names of parameters and their
values. The meaning of the parameters are as follows. `on' means that the
parameter is not zero.
\E

@table @code
@item NoSugar
\BJP
on $B$N>l9g(B, sugar strategy $B$NBe$o$j$K(B Buchberger$B$N(B normal strategy $B$,MQ(B
$B$$$i$l$k(B.
\E
\BEG
If `on', Buchberger's normal strategy is used instead of sugar strategy.
\E

@item NoCriB
\JP on $B$N>l9g(B, $BITI,MWBP8!=P5,=`$N$&$A(B, $B5,=`(B B $B$rE,MQ$7$J$$(B.
\EG If `on', criterion B among the Gebauer-Moeller's criteria is not applied.

@item NoGC
\JP on $B$N>l9g(B, $B7k2L$,%0%l%V%J4pDl$K$J$C$F$$$k$+$I$&$+$N%A%'%C%/$r9T$o$J$$(B.
\BEG
If `on', the check that a Groebner basis candidate is indeed a Groebner basis,
is not executed.
\E

@item NoMC
\BJP
on $B$N>l9g(B, $B7k2L$,F~NO%$%G%"%k$HF1Ey$N%$%G%"%k$G$"$k$+$I$&$+$N%A%'%C%/(B
$B$r9T$o$J$$(B.
\E
\BEG
If `on', the check that the resulting polynomials generates the same ideal as
the ideal generated by the input, is not executed.
\E

@item NoRA
\BJP
on $B$N>l9g(B, $B7k2L$r(B reduced $B%0%l%V%J4pDl$K$9$k$?$a$N(B
interreduce $B$r9T$o$J$$(B. 
\E
\BEG
If `on', the interreduction, which makes the Groebner basis reduced, is not
executed.
\E

@item NoGCD
\BJP
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, 
$B78?t$N(B content $B$r$H$i$J$$(B.
\E
\BEG
If `on', content removals are not executed during a Groebner basis computation
over a rational function field.
\E

@item Top
\JP on $B$N>l9g(B, normal form $B7W;;$K$*$$$FF,9`>C5n$N$_$r9T$&(B. 
\EG If `on', Only the head term of the polynomial being reduced is reduced.

@comment @item Interreduce
@comment \BJP
@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
@comment $B$h$k(B normal form $B$GCV$-49$($k(B.
@comment \E
@comment \BEG
@comment If `on', intermediate basis elements are reduced by using a newly generated
@comment basis element.
@comment \E

@item Reverse
\BJP
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
$B@h$7$FA*$V(B.
\E
\BEG
If `on', the selection strategy of reducer in a normal form computation
is such that a newer reducer is used first.
\E

@item Print
\JP on $B$N>l9g(B, $B%0%l%V%J4pDl7W;;$NESCf$K$*$1$k$5$^$6$^$J>pJs$rI=<($9$k(B. 
\BEG
If `on', various informations during a Groebner basis computation is
displayed.
\E

@item PrintShort
\JP on $B$G!"(BPrint $B$,(B off $B$N>l9g(B, $B%0%l%V%J4pDl7W;;$NESCf$N>pJs$rC;=L7A$GI=<($9$k(B. 
\BEG
If `on' and Print is `off', short information during a Groebner basis computation is
displayed.
\E

@item Stat
\BJP
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
$B$l$k%G!<%?$NFb(B, $B=87W%G!<%?$N$_$,I=<($5$l$k(B. 
\E
\BEG
If `on', a summary of informations is shown after a Groebner basis
computation. Note that the summary is always shown if @code{Print} is `on'.
\E

@item ShowMag
\BJP
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
$B78?t$N%S%C%HD9$NOB$rI=<($7(B, $B:G8e$K(B, $B$=$l$i$NOB$N:GBgCM$rI=<($9$k(B. 
\E
\BEG
If `on' and @code{Print} is `on', the sum of bit length of
coefficients of a generated basis element, which we call @var{magnitude},
is shown after every normal computation.  After comleting the
computation the maximal value among the sums is shown.
\E

@item Content
@itemx Multiple
\BJP
0 $B$G$J$$M-M}?t$N;~(B, $BM-M}?t>e$N@55,7A7W;;$K$*$$$F(B, $B78?t$N%S%C%HD9$NOB$,(B
@code{Content} $BG\$K$J$k$4$H$K78?tA4BN$N(B GCD $B$,7W;;$5$l(B, $B$=$N(B GCD $B$G(B
$B3d$C$?B?9`<0$r4JLs$9$k(B. @code{Content} $B$,(B 1 $B$J$i$P(B, $B4JLs$9$k$4$H$K(B
GCD $B7W;;$,9T$o$l0lHL$K$O8zN($,0-$/$J$k$,(B, @code{Content} $B$r(B 2 $BDxEY(B
$B$H$9$k$H(B, $B5pBg$J@0?t$,78?t$K8=$l$k>l9g(B, $B8zN($,NI$/$J$k>l9g$,$"$k(B. 
backward compatibility $B$N$?$a!"(B@code{Multiple} $B$G@0?tCM$r;XDj$G$-$k(B.
\E
\BEG
If a non-zero rational number, in a normal form computation
over the rationals, the integer content of the polynomial being
reduced is removed when its magnitude becomes @code{Content} times
larger than a registered value, which is set to the magnitude of the
input polynomial. After each content removal the registered value is
set to the magnitude of the resulting polynomial. @code{Content} is
equal to 1, the simiplification is done after every normal form computation.
It is empirically known that it is often efficient to set @code{Content} to 2
for the case where large integers appear during the computation.
An integer value can be set by the keyword @code{Multiple} for
backward compatibility.
\E

@item Demand

\BJP
$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
$BCf$K$*$+$l$:(B, $B$=$N%G%#%l%/%H%jCf$K%P%$%J%j%G!<%?$H$7$FCV$+$l(B, $B$=$NB?9`(B
$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
$B9`<0$O(B, $BFbIt$G$N%$%s%G%C%/%9$r%U%!%$%kL>$K;}$D%U%!%$%k$K3JG<$5$l$k(B. 
$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
$B$?$a(B, $B%f!<%6$,@UG$$r;}$C$F>C5n$9$kI,MW$,$"$k(B. 
\E
\BEG
If the value (a character string) is a valid directory name, then
generated basis elements are put in the directory and are loaded on
demand during normal form computations.  Each elements is saved in the
binary form and its name coincides with the index internally used in
the computation. These binary files are not removed automatically
and one should remove them by hand.
\E
@end table

@noindent
\JP @code{Print} $B$,(B 0 $B$G$J$$>l9g<!$N$h$&$J%G!<%?$,I=<($5$l$k(B.
\EG If @code{Print} is `on', the following informations are shown.

@example
[93] gr(cyclic(4),[c0,c1,c2,c3],0)$
mod= 99999989, eval = []
(0)(0)<<0,2,0,0>>(2,3),nb=2,nab=5,rp=2,sugar=2,mag=4
(0)(0)<<0,1,2,0>>(1,2),nb=3,nab=6,rp=2,sugar=3,mag=4
(0)(0)<<0,1,1,2>>(0,1),nb=4,nab=7,rp=3,sugar=4,mag=6
.
(0)(0)<<0,0,3,2>>(5,6),nb=5,nab=8,rp=2,sugar=5,mag=4
(0)(0)<<0,1,0,4>>(4,6),nb=6,nab=9,rp=3,sugar=5,mag=4
(0)(0)<<0,0,2,4>>(6,8),nb=7,nab=10,rp=4,sugar=6,mag=6
....gb done
reduceall
.......
membercheck
(0,0)(0,0)(0,0)(0,0)
gbcheck total 8 pairs
........
UP=(0,0)SP=(0,0)SPM=(0,0)NF=(0,0)NFM=(0.010002,0)ZNFM=(0.010002,0)
PZ=(0,0)NP=(0,0)MP=(0,0)RA=(0,0)MC=(0,0)GC=(0,0)T=40,B=0 M=8 F=6
D=12 ZR=5 NZR=6 Max_mag=6
[94]
@end example

@noindent
\BJP
$B:G=i$KI=<($5$l$k(B @code{mod}, @code{eval} $B$O(B, trace-lifting $B$GMQ$$$i$l$kK!(B
$B$G$"$k(B. @code{mod} $B$OAG?t(B, @code{eval} $B$OM-M}<078?t$N>l9g$KMQ$$$i$l$k(B
$B?t$N%j%9%H$G$"$k(B. 
\E
\BEG
In this example @code{mod} and @code{eval} indicate moduli used in
trace-lifting. @code{mod} is a prime and @code{eval} is a list of integers
used for evaluation when the ground field is a field of rational functions.
\E

@noindent
\JP $B7W;;ESCf$GB?9`<0$,@8@.$5$l$kKh$K<!$N7A$N%G!<%?$,I=<($5$l$k(B. 
\EG The following information is shown after every normal form computation.

@example
(TNF)(TCONT)HT(INDEX),nb=NB,nab=NAB,rp=RP,sugar=S,mag=M
@end example

@noindent
\JP $B$=$l$i$N0UL#$O<!$NDL$j(B. 
\EG Meaning of each component is as follows.

@table @code
\BJP
@item TNF

normal form $B7W;;;~4V(B ($BIC(B)

@item TCONT

content $B7W;;;~4V(B ($BIC(B)

@item HT

$B@8@.$5$l$?B?9`<0$NF,9`(B

@item INDEX

S-$BB?9`<0$r9=@.$9$kB?9`<0$N%$%s%G%C%/%9$N%Z%"(B

@item NB

$B8=:_$N(B, $B>iD9@-$r=|$$$?4pDl$N?t(B

@item NAB

$B8=:_$^$G$K@8@.$5$l$?4pDl$N?t(B

@item RP

$B;D$j$N%Z%"$N?t(B

@item S

$B@8@.$5$l$?B?9`<0$N(B sugar $B$NCM(B

@item M

$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. )
\E
\BEG
@item TNF

CPU time for normal form computation (second)

@item TCONT

CPU time for content removal(second)

@item HT

Head term of the generated basis element

@item INDEX

Pair of indices which corresponds to the reduced S-polynomial

@item NB

Number of basis elements after removing redundancy
      
@item NAB

Number of all the basis elements
      
@item RP

Number of remaining pairs

@item S

Sugar of the generated basis element
      
@item M

Magnitude of the genrated basis element (shown if @code{ShowMag} is `on'.)
\E
@end table

@noindent
\BJP
$B:G8e$K(B, $B=87W%G!<%?$,I=<($5$l$k(B. $B0UL#$O<!$NDL$j(B. 
($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.)
\E
\BEG
The summary of the informations shown after a Groebner basis
computation is as follows.  If a component shows timings and it
contains two numbers, they are a pair of time for computation and time
for garbage colection.
\E

@table @code
\BJP
@item UP

$B%Z%"$N%j%9%H$NA`:n$K$+$+$C$?;~4V(B

@item SP

$BM-M}?t>e$N(B S-$BB?9`<07W;;;~4V(B

@item SPM

$BM-8BBN>e$N(B S-$BB?9`<07W;;;~4V(B

@item NF

$BM-M}?t>e$N(B normal form $B7W;;;~4V(B

@item NFM

$BM-8BBN>e$N(B normal form $B7W;;;~4V(B

@item ZNFM

@code{NFM} $B$NFb(B, 0 $B$X$N(B reduction $B$K$+$+$C$?;~4V(B

@item PZ

content $B7W;;;~4V(B

@item NP

$BM-M}?t78?tB?9`<0$N78?t$KBP$9$k>jM>1i;;$N7W;;;~4V(B

@item MP

S-$BB?9`<0$r@8@.$9$k%Z%"$NA*Br$K$+$+$C$?;~4V(B

@item RA

interreduce $B7W;;;~4V(B

@item MC

trace-lifting $B$K$*$1$k(B, $BF~NOB?9`<0$N%a%s%P%7%C%W7W;;;~4V(B

@item GC

$B7k2L$N%0%l%V%J4pDl8uJd$N%0%l%V%J4pDl%A%'%C%/;~4V(B

@item T

$B@8@.$5$l$?%Z%"$N?t(B

@item B, M, F, D

$B3F(B criterion $B$K$h$j=|$+$l$?%Z%"$N?t(B
      
@item ZR

0 $B$K(B reduce $B$5$l$?%Z%"$N?t(B

@item NZR

0 $B$G$J$$B?9`<0$K(B reduce $B$5$l$?%Z%"$N?t(B

@item Max_mag

$B@8@.$5$l$?B?9`<0$N(B, $B78?t$N%S%C%HD9$NOB$N:GBgCM(B
\E
\BEG
@item UP

Time to manipulate the list of critical pairs

@item SP

Time to compute S-polynomials over the rationals

@item SPM

Time to compute S-polynomials over a finite field

@item NF

Time to compute normal forms over the rationals

@item NFM

Time to compute normal forms over a finite field

@item ZNFM

Time for zero reductions in @code{NFM}

@item PZ

Time to remove integer contets

@item NP

Time to compute remainders for coefficients of polynomials with coeffieints
in the rationals

@item MP

Time to select pairs from which S-polynomials are computed

@item RA

Time to interreduce the Groebner basis candidate

@item MC

Time to check that each input polynomial is a member of the ideal
generated by the Groebner basis candidate.

@item GC

Time to check that the Groebner basis candidate is a Groebner basis

@item T

Number of critical pairs generated

@item B, M, F, D

Number of critical pairs removed by using each criterion
     
@item ZR

Number of S-polynomials reduced to 0

@item NZR

Number of S-polynomials reduced to non-zero results

@item Max_mag

Maximal magnitude among all the generated polynomials
\E
@end table

\BJP
@node $B9`=g=x$N@_Dj(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B9`=g=x$N@_Dj(B
\E
\BEG
@node Setting term orderings,,, Groebner basis computation
@section Setting term orderings
\E

@noindent
\BJP
$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
$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
$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
$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
$B9TNs$GI=8=$5$l$k(B. 
\E
\BEG
A term is internally represented as an integer vector whose components
are exponents with respect to variables. A variable list specifies the
correspondences between variables and components. A type of term ordering
specifies a total order for integer vectors. A type of term ordering is
represented by an integer, a list of integer or matrices.
\E

@noindent
\JP $B4pK\E*$J9`=g=x7?$H$7$F<!$N(B 3 $B$D$,$"$k(B. 
\EG There are following three fundamental types.

@table @code
\JP @item 0 (DegRevLex; @b{$BA4<!?t5U<-=q<0=g=x(B})
\EG @item 0 (DegRevLex; @b{total degree reverse lexicographic ordering})

\BJP
$B0lHL$K(B, $B$3$N=g=x$K$h$k%0%l%V%J4pDl7W;;$,:G$b9bB.$G$"$k(B. $B$?$@$7(B, 
$BJ}Dx<0$r2r$/$H$$$&L\E*$KMQ$$$k$3$H$O(B, $B0lHL$K$O$G$-$J$$(B. $B$3$N(B
$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, 
$BB>$NJQ?t=g=x$X$N4pDlJQ49$N$?$a$N%=!<%9$H$7$FMQ$$$i$l$k(B. 
\E
\BEG
In general, computation by this ordering shows the fastest speed
in most Groebner basis computations.
However, for the purpose to solve polynomial equations, this type
of ordering is, in general, not so suitable.
The Groebner bases obtained by this ordering is used for computing
the number of solutions, solving ideal membership problem and seeds
for conversion to other Groebner bases under different ordering.
\E

\JP @item 1 (DegLex; @b{$BA4<!?t<-=q<0=g=x(B})
\EG @item 1 (DegLex; @b{total degree lexicographic ordering})

\BJP
$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, 
@code{DegRevLex} $B$HF1MMD>@\$=$N7k2L$rMQ$$$k$3$H$O:$Fq$G$"$k(B. $B$7$+$7(B, 
$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
$B$r5a$a$F$$$k(B. 
\E
\BEG
By this type term ordering, Groebner bases are obtained fairly faster
than Lex (lexicographic) ordering, too.
Alike the @code{DegRevLex} ordering, the result, in general, cannot directly
be used for solving polynomial equations.
It is used, however, in such a way
that a Groebner basis is computed in this ordering after homogenization
to obtain the final lexicographic Groebner basis.
\E

\JP @item 2 (Lex; @b{$B<-=q<0=g=x(B})
\EG @item 2 (Lex; @b{lexicographic ordering})

\BJP
$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
$B7W;;;~4V$,$+$+$j2a$.$k$N$,FqE@$G$"$k(B. $BFC$K(B, $B2r$,M-8B8D$N>l9g(B, $B7k2L$N(B
$B78?t$,6K$a$FD9Bg$JB?G\D9?t$K$J$k>l9g$,B?$$(B. $B$3$N>l9g(B, @code{gr()}, 
@code{hgr()} $B$K$h$k7W;;$,6K$a$FM-8z$K$J$k>l9g$,B?$$(B. 
\E
\BEG
Groebner bases computed by this ordering give the most convenient
Groebner bases for solving the polynomial equations.
The only and serious shortcoming is the enormously long computation
time. 
It is often observed that the number coefficients of the result becomes
very very long integers, especially if the ideal is 0-dimensional.
For such a case, it is empirically true for many cases
that i.e., computation by
@code{gr()} and/or @code{hgr()} may be quite effective.
\E
@end table

@noindent
\BJP
$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. 
$B$3$l$O(B, 
\E
\BEG
By combining these fundamental orderingl into a list, one can make
various term ordering called elimination orderings.
\E

@code{[[O1,L1],[O2,L2],...]}

@noindent
\BJP
$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
$B?t$rI=$9(B. $B$3$N;XDj$O(B, $BJQ?t$r@hF,$+$i(B @code{L1}, @code{L2} , ...$B8D(B
$B$:$D$NAH$KJ,$1(B, $B$=$l$>$l$NJQ?t$K4X$7(B, $B=g$K(B @code{O1}, @code{O2},
...$B$N9`=g=x7?$GBg>.$,7hDj$9$k$^$GHf3S$9$k$3$H$r0UL#$9$k(B. $B$3$N7?$N(B
$B=g=x$O0lHL$K>C5n=g=x$H8F$P$l$k(B. 
\E
\BEG
In this example @code{Oi} indicates 0, 1 or 2 and @code{Li} indicates
the number of variables subject to the correspoinding orderings.
This specification means the following.
      
The variable list is separated into sub lists from left to right where
the @code{i}-th list contains @code{Li} members and it corresponds to
the ordering of type @code{Oi}. The result of a comparison is equal
to that for the leftmost different sub components. This type of ordering
is called an elimination ordering.
\E

@noindent
\BJP
$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
@code{m} $BNs$N<B?t9TNs(B @code{M} $B$,<!$N@-<A$r;}$D$H$9$k(B. 
\E
\BEG
Furthermore one can specify a term ordering by a matix.
Suppose that a real @code{n}, @code{m} matrix @code{M} has the
following properties.
\E

@enumerate
@item
\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. 
\BEG
For all integer verctors @code{v} of length @code{m} @code{Mv=0} is equivalent
to @code{v=0}.
\E

@item
\BJP
$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, 
@code{Mv} $B$N(B 0 $B$G$J$$:G=i$N@.J,$OHsIi(B.
\E
\BEG
For all non-negative integer vectors @code{v} the first non-zero component
of @code{Mv} is non-negative.
\E
@end enumerate

@noindent
\BJP
$B$3$N;~(B, 2 $B$D$N%Y%/%H%k(B @code{t}, @code{s} $B$KBP$7(B, 
@code{t>s} $B$r(B, @code{M(t-s)} $B$N(B 0 $B$G$J$$:G=i$N@.J,$,HsIi(B,
$B$GDj5A$9$k$3$H$K$h$j9`=g=x$,Dj5A$G$-$k(B.
\E
\BEG
Then we can define a term ordering such that, for two vectors
@code{t}, @code{s}, @code{t>s} means that the first non-zero component
of @code{M(t-s)} is non-negative.
\E

@noindent
\BJP
$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
@code{dp_ord()} $B$G;XDj$5$l(B, $B$5$^$6$^$JH!?t$N<B9T$N:]$K;2>H$5$l$k(B. 
\E
\BEG
Types of term orderings are used as arguments of functions such as
@code{gr()}. It is also set internally by @code{dp_ord()} and is used
during executions of various functions.
\E

@noindent
\BJP
$B$3$l$i$N=g=x$N6qBNE*$JDj5A$*$h$S%0%l%V%J4pDl$K4X$9$k99$K>\$7$$2r@b$O(B
@code{[Becker,Weispfenning]} $B$J$I$r;2>H$N$3$H(B. 
\E
\BEG
For concrete definitions of term ordering and more information
about Groebner basis, refer to, for example, the book
@code{[Becker,Weispfenning]}.
\E

@noindent
\JP $B9`=g=x7?$N@_Dj$NB>$K(B, $BJQ?t$N=g=x<+BN$b7W;;;~4V$KBg$-$J1F6A$rM?$($k(B. 
\BEG
Note that the variable ordering have strong effects on the computation
time as well as the choice of types of term orderings.
\E

@example
[90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
[91] gr(B,[x,y,z,t],2);
[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
-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
+(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
-167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
(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+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+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,
(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+(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-11*t^2-5*t+9)*z^2,
-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
-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+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+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,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-32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t,
-z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
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,
z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
-t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
-t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,z^5-t^4]
[93] gr(B,[t,z,y,x],2);
[x^10-t,x^8-z,x^31-x^6-x-y]
@end example

@noindent
\BJP
$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
$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
$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
$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
$B$3$H$G$"$j(B, $B$3$NNc$N>l9g$O(B, @code{t},  @code{z}, @code{y} $B$,4{$K(B
@code{x} $B$GI=$5$l$F$$$k$3$H$+$i$3$N$h$&$J6KC<$J7k2L$H$J$C$?$o$1$G$"$k(B. 
$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
$B$3$H$O>/$J$/(B, $B;n9T:x8m$,I,MW$J>l9g$b$"$k(B. 
\E
\BEG
As you see in the above example, the Groebner base under variable
ordering @code{[x,y,z,t]} has a lot of bases and each base itself is
large.  Under variable ordering @code{[t,z,y,x]}, however, @code{B} itself
is already the Groebner basis.
Roughly speaking, to obtain a Groebner base under the lexicographic
ordering is to express the variables on the left (having higher order)
in terms of variables on the right (having lower order).
In the example, variables @code{t},  @code{z}, and @code{y} are already
expressed by variable @code{x}, and the above explanation justifies
such a drastic experimental results.
In practice, however, optimum ordering for variables may not known
beforehand, and some heuristic trial may be inevitable.
\E

\BJP
@node $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $BM-M}<0$r78?t$H$9$k%0%l%V%J4pDl7W;;(B
\E
\BEG
@node Groebner basis computation with rational function coefficients,,, Groebner basis computation
@section Groebner basis computation with rational function coefficients
\E

@noindent
\BJP
@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
$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
$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
$BBN$N85$H$7$F07$&(B. 
\E
\BEG
Such variables that appear within the input polynomials but
not appearing in the input variable list are automatically treated
as elements in the coefficient field
by top level functions, such as @code{gr()}.
\E

@example
[64] gr([a*x+b*y-c,d*x+e*y-f],[x,y],2);
[(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]
@end example

@noindent
\BJP
$B$3$NNc$G$O(B, @code{a}, @code{b}, @code{c}, @code{d} $B$,78?tBN$N85$H$7$F(B
$B07$o$l$k(B. $B$9$J$o$A(B, $BM-M}H!?tBN(B 
@b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}) $B>e$N(B 2 $BJQ?tB?9`<04D(B
@b{F}[@code{x},@code{y}] $B$K$*$1$k%0%l%V%J4pDl$r5a$a$k$3$H$K$J$k(B. 
$BCm0U$9$Y$-$3$H$O(B, 
$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
$B$H$7$F$N6&DL0x;R$,$"$C$?>l9g$K$O(B, $B7k2L$+$i$=$N0x;R$O=|$+$l$F$$$k(B
$B$?$a(B, $BM-M}?tBN>e$NB?9`<04D>e$NLdBj$H$7$F9M$($?>l9g$N7k2L$H$O0lHL(B
$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
$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
$B;}$DM-M}<0$OJ,;6I=8=B?9`<0$N78?t$H$7$F$O5v$5$l$J$$(B. 
\E
\BEG
In this example, variables @code{a}, @code{b}, @code{c}, and @code{d}
are treated as elements in the coefficient field.
In this case, a Groebner basis is computed
on a bi-variate polynomial ring
@b{F}[@code{x},@code{y}]
over rational function field
 @b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}).
Notice that coefficients are considered as a member in a field.
As a consequence, polynomial factors common to the coefficients
are removed so that the result, in general, is different from
the result that would be obtained when the problem is considered
as a computation of Groebner basis over a polynomial ring
with rational function coefficients.
And note that coefficients of a distributed polynomial are limited
to numbers and polynomials because of efficiency.
\E

\BJP
@node $B4pDlJQ49(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B4pDlJQ49(B
\E
\BEG
@node Change of ordering,,, Groebner basis computation
@section Change of orderng
\E

@noindent
\BJP
$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
$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, 
$B$=$l$rF~NO$H$7$F<-=q<0=g=x$N%0%l%V%J4pDl$r7W;;$9$kJ}$,8zN($,$h$$>l9g(B
$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
$BJQ49$H8F$P$l$kJ}K!$K$h$j(B, Buchberger $B%"%k%4%j%:%`$K$h$i$:$K8zN(NI$/(B
$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
$BH!?t$,(B, $B%f!<%6Dj5AH!?t$H$7$F(B @samp{gr} $B$K$$$/$D$+Dj5A$5$l$F$$$k(B. 
$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
$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
@var{vlist2} $B$K$*$1$k<-=q<0=g=x$N%0%l%V%J4pDl$KJQ49$9$kH!?t$G$"$k(B. 
\E
\BEG
When we compute a lex order Groebner basis, it is often efficient to
compute it via Groebner basis with respect to another order such as
degree reverse lex order, rather than to compute it directory by
@code{gr()} etc. If we know that an input is a Groebner basis with
respect to an order, we can apply special methods called change of
ordering for a Groebner basis computation with respect to another
order, without using Buchberger algorithm. The following two functions
are ones for change of ordering such that they convert a Groebner
basis @var{gbase} with respect to the variable order @var{vlist1} and
the order type @var{order} into a lex Groebner basis with respect
to the variable order @var{vlist2}.
\E

@table @code
@item tolex(@var{gbase},@var{vlist1},@var{order},@var{vlist2})

\BJP
$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. 
$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
$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. 
\E
\BEG
This function can be used only when @var{gbase} is an ideal over the
rationals.  The input @var{gbase} must be a Groebner basis with respect
to the variable order @var{vlist1} and the order type @var{order}. Moreover
the ideal generated by @var{gbase} must be zero-dimensional.
This computes the lex Groebner basis of @var{gbase}
by using the modular change of ordering algorithm. The algorithm first
computes the lex Groebner basis over a finite field. Then each element
in the lex Groebner basis over the rationals is computed with undetermined
coefficient method and linear equation solving by Hensel lifting.
\E

@item tolex_tl(@var{gbase},@var{vlist1},@var{order},@var{vlist2},@var{homo})

\BJP
$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
$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 
trace-lifting$B$K$*$1$k%0%l%V%J4pDl8uJd$NF,9`(B, $BF,78?t$N@-<A$rMxMQ$7$F(B, 
$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
$B$k$?$a(B, $BC1$K(BBuchberger $B%"%k%4%j%:%`$r7+$jJV$9$h$j8zN($h$/7W;;$G$-$k(B. 
$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
$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, 
$BD>@\<-=q<0=g=x$N7W;;$r9T$&$h$j8zN($,$h$$(B. ($B$b$A$m$sNc30$"$j(B. )
$B0z?t(B @var{homo} $B$,(B 0 $B$G$J$$;~(B, @code{hgr()} $B$HF1MM$K@F<!2=$r7PM3$7$F(B
$B7W;;$r9T$&(B. 
\E
\BEG
This function computes the lex Groebner basis of @var{gbase}.  The
input @var{gbase} must be a Groebner basis with respect to the
variable order @var{vlist1} and the order type @var{order}.
Buchberger algorithm with trace lifting is used to compute the lex
Groebner basis, however the Groebner basis check and the ideal
membership check can be omitted by using several properties derived
from the fact that the input is a Groebner basis. So it is more
efficient than simple repetition of Buchberger algorithm. If the input
is zero-dimensional, this function inserts automatically a computation
of Groebner basis with respect to an elimination order, which makes
the whole computation more efficient for many cases. If @var{homo} is
not equal to 0, homogenization is used in each step.
\E
@end table

@noindent
\BJP
$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
$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
@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. 
\E
\BEG
For zero-dimensional systems, there are several fuctions to
compute the minimal polynomial of a polynomial and or a more compact
representation for zeros of the system. They are all defined in @samp{gr}.
Refer to the sections for each functions.
\E

\BJP
@node Weyl $BBe?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section Weyl $BBe?t(B
\E
\BEG
@node Weyl algebra,,, Groebner basis computation
@section Weyl algebra
\E

@noindent

\BJP
$B$3$l$^$G$O(B, $BDL>o$N2D49$JB?9`<04D$K$*$1$k%0%l%V%J4pDl7W;;$K$D$$$F(B
$B=R$Y$F$-$?$,(B, $B%0%l%V%J4pDl$NM}O@$O(B, $B$"$k>r7o$rK~$?$9Hs2D49$J(B
$B4D$K$b3HD%$G$-$k(B. $B$3$N$h$&$J4D$NCf$G(B, $B1~MQ>e$b=EMW$J(B, 
Weyl $BBe?t(B, $B$9$J$o$AB?9`<04D>e$NHyJ,:nMQAG4D$N1i;;$*$h$S(B
$B%0%l%V%J4pDl7W;;$,(B Risa/Asir $B$K<BAu$5$l$F$$$k(B. 

$BBN(B @code{K} $B>e$N(B @code{n} $B<!85(B Weyl $BBe?t(B 
@code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} $B$O(B
\E

\BEG
So far we have explained Groebner basis computation in
commutative polynomial rings. However Groebner basis can be
considered in more general non-commutative rings.
Weyl algebra is one of such rings and 
Risa/Asir implements fundamental operations
in Weyl algebra and Groebner basis computation in Weyl algebra.

The @code{n} dimensional Weyl algebra over a field @code{K},
@code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} is a non-commutative
algebra which has the following fundamental relations:
\E

@code{xi*xj-xj*xi=0}, @code{Di*Dj-Dj*Di=0}, @code{Di*xj-xj*Di=0} (@code{i!=j}),
@code{Di*xi-xi*Di=1}

\BJP
$B$H$$$&4pK\4X78$r;}$D4D$G$"$k(B. @code{D} $B$O(B $BB?9`<04D(B @code{K[x1,@dots{},xn]} $B$r78?t(B
$B$H$9$kHyJ,:nMQAG4D$G(B,  @code{Di} $B$O(B @code{xi} $B$K$h$kHyJ,$rI=$9(B. $B8r494X78$K$h$j(B, 
@code{D} $B$N85$O(B, @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn} $B$J$kC19`(B
$B<0$N(B @code{K} $B@~7A7k9g$H$7$F=q$-I=$9$3$H$,$G$-$k(B. 
Risa/Asir $B$K$*$$$F$O(B, $B$3$NC19`<0$r(B, $B2D49$JB?9`<0$HF1MM$K(B
@code{<<i1,@dots{},in,j1,@dots{},jn>>} $B$GI=$9(B. $B$9$J$o$A(B, @code{D} $B$N85$b(B
$BJ,;6I=8=B?9`<0$H$7$FI=$5$l$k(B. $B2C8:;;$O(B, $B2D49$N>l9g$HF1MM$K(B, @code{+}, @code{-}
$B$K$h$j(B
$B<B9T$G$-$k$,(B, $B>h;;$O(B, $BHs2D49@-$r9MN8$7$F(B @code{dp_weyl_mul()} $B$H$$$&4X?t(B
$B$K$h$j<B9T$9$k(B.
\E

\BEG
@code{D} is the ring of differential operators whose coefficients
are polynomials in @code{K[x1,@dots{},xn]} and
@code{Di} denotes the differentiation with respect to  @code{xi}.
According to the commutation relation,
elements of @code{D} can be represented as a @code{K}-linear combination 
of monomials @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn}.
In Risa/Asir, this type of monomial is represented 
by @code{<<i1,@dots{},in,j1,@dots{},jn>>} as in the case of commutative
polynomial.
That is, elements of @code{D} are represented by distributed polynomials.
Addition and subtraction can be done by @code{+}, @code{-},
but multiplication is done by calling @code{dp_weyl_mul()} because of
the non-commutativity of @code{D}.
\E

@example
[0] A=<<1,2,2,1>>;
(1)*<<1,2,2,1>>
[1] B=<<2,1,1,2>>;
(1)*<<2,1,1,2>>
[2] A*B;
(1)*<<3,3,3,3>>
[3] dp_weyl_mul(A,B);
(1)*<<3,3,3,3>>+(1)*<<3,2,3,2>>+(4)*<<2,3,2,3>>+(4)*<<2,2,2,2>>
+(2)*<<1,3,1,3>>+(2)*<<1,2,1,2>>
@end example

\BJP
$B%0%l%V%J4pDl7W;;$K$D$$$F$b(B, Weyl $BBe?t@lMQ$N4X?t$H$7$F(B, 
$B<!$N4X?t$,MQ0U$7$F$"$k(B. 
\E
\BEG
The following functions are avilable for Groebner basis computation
in Weyl algebra:
\E
@code{dp_weyl_gr_main()},
@code{dp_weyl_gr_mod_main()},
@code{dp_weyl_gr_f_main()},
@code{dp_weyl_f4_main()},
@code{dp_weyl_f4_mod_main()}.
\BJP
$B$^$?(B, $B1~MQ$H$7$F(B, global b $B4X?t$N7W;;$,<BAu$5$l$F$$$k(B. 
\E
\BEG
Computation of the global b function is implemented as an application.
\E

\BJP
@node $B%0%l%V%J4pDl$K4X$9$kH!?t(B,,, $B%0%l%V%J4pDl$N7W;;(B
@section $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\E
\BEG
@node Functions for Groebner basis computation,,, Groebner basis computation
@section Functions for Groebner basis computation
\E

@menu
* gr hgr gr_mod::
* lex_hensel lex_tl tolex tolex_d tolex_tl::
* lex_hensel_gsl tolex_gsl tolex_gsl_d::
* gr_minipoly minipoly::
* tolexm minipolym::
* dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main::
* dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main::
* dp_gr_flags dp_gr_print::
* dp_ord::
* dp_ptod::
* dp_dtop::
* dp_mod dp_rat::
* dp_homo dp_dehomo::
* dp_ptozp dp_prim::
* dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod::
* dp_hm dp_ht dp_hc dp_rest::
* dp_td dp_sugar::
* dp_lcm::
* dp_redble::
* dp_subd::
* dp_mbase::
* dp_mag::
* dp_red dp_red_mod::
* dp_sp dp_sp_mod::
* p_nf p_nf_mod p_true_nf p_true_nf_mod ::
* p_terms::
* gb_comp::
* katsura hkatsura cyclic hcyclic::
* dp_vtoe dp_etov::
* lex_hensel_gsl tolex_gsl tolex_gsl_d::
* primadec primedec::
* primedec_mod::
* bfunction bfct generic_bfct::
@end menu

\JP @node gr hgr gr_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node gr hgr gr_mod,,, Functions for Groebner basis computation
@subsection @code{gr}, @code{hgr}, @code{gr_mod}, @code{dgr}
@findex gr
@findex hgr
@findex gr_mod
@findex dgr

@table @t
@item gr(@var{plist},@var{vlist},@var{order})
@itemx hgr(@var{plist},@var{vlist},@var{order})
@itemx gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
@itemx dgr(@var{plist},@var{vlist},@var{order},@var{procs})
\JP :: $B%0%l%V%J4pDl$N7W;;(B
\EG :: Groebner basis computation
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item plist  vlist  procs
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item p
\JP 2^27 $BL$K~$NAG?t(B
\EG prime less than 2^27
@end table

@itemize @bullet
\BJP
@item
$BI8=`%i%$%V%i%j$N(B @samp{gr} $B$GDj5A$5$l$F$$$k(B. 
@item
$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
@var{order} $B$K4X$9$k%0%l%V%J4pDl$r5a$a$k(B. @code{gr()}, @code{hgr()}
$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. 
@item
@var{vlist} $B$OITDj85$N%j%9%H(B. @var{vlist} $B$K8=$l$J$$ITDj85$O(B, 
$B78?tBN$KB0$9$k$H8+$J$5$l$k(B. 
@item
@code{gr()}, trace-lifting ($B%b%8%e%i1i;;$rMQ$$$?9bB.2=(B) $B$*$h$S(B sugar
strategy $B$K$h$k7W;;(B, @code{hgr()} $B$O(B trace-lifting $B$*$h$S(B
$B@F<!2=$K$h$k(B $B6:@5$5$l$?(B sugar strategy $B$K$h$k7W;;$r9T$&(B. 
@item
@code{dgr()} $B$O(B, @code{gr()}, @code{dgr()} $B$r(B
$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, 
$B@h$K7k2L$rJV$7$?J}$N7k2L$rJV$9(B. $B7k2L$OF10l$G$"$k$,(B, $B$I$A$i$NJ}K!$,(B
$B9bB.$+0lHL$K$OITL@$N$?$a(B, $B<B:]$N7P2a;~4V$rC;=L$9$k$N$KM-8z$G$"$k(B. 
@item
@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
CPU $B;~4V$G$"$j(B, $B$3$NH!?t$N>l9g$O$[$H$s$IDL?.$N$?$a$N;~4V$G$"$k(B. 
\E
\BEG
@item 
These functions are defined in @samp{gr} in the standard library
directory.
@item 
They compute a Groebner basis of a polynomial list @var{plist} with
respect to the variable order @var{vlist} and the order type @var{order}.
@code{gr()} and @code{hgr()} compute a Groebner basis over the rationals
and @code{gr_mod} computes over GF(@var{p}).
@item 
Variables not included in @var{vlist} are regarded as
included in the ground field.
@item 
@code{gr()} uses trace-lifting (an improvement by modular computation)
 and sugar strategy.
@code{hgr()} uses trace-lifting and a cured sugar strategy
by using homogenization.
@item 
@code{dgr()} executes @code{gr()}, @code{dgr()} simultaneously on
two process in a child process list @var{procs} and returns
the result obtained first. The results returned from both the process
should be equal, but it is not known in advance which method is faster.
Therefore this function is useful to reduce the actual elapsed time.
@item 
The CPU time shown after an exection of @code{dgr()} indicates
that of the master process, and most of the time corresponds to the time
for communication.
\E
@end itemize

@example
[0] load("gr")$
[64] load("cyclic")$
[74] G=gr(cyclic(5),[c0,c1,c2,c3,c4],2);
[c4^15+122*c4^10-122*c4^5-1,...]
[75] GM=gr_mod(cyclic(5),[c0,c1,c2,c3,c4],2,31991)$
24628*c4^15+29453*c4^10+2538*c4^5+7363
[76] (G[0]*24628-GM[0])%31991;
0
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
@fref{dp_ord}.
@end table

\JP @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, Functions for Groebner basis computation
@subsection @code{lex_hensel}, @code{lex_tl}, @code{tolex}, @code{tolex_d}, @code{tolex_tl}
@findex lex_hensel
@findex lex_tl
@findex tolex
@findex tolex_d
@findex tolex_tl

@table @t
@item lex_hensel(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
@itemx lex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
\JP :: $B4pDlJQ49$K$h$k<-=q<0=g=x%0%l%V%J4pDl$N7W;;(B
\EG:: Groebner basis computation with respect to a lex order by change of ordering
@item tolex(@var{plist},@var{vlist1},@var{order},@var{vlist2})
@itemx tolex_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
@itemx tolex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
\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
\EG :: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item plist  vlist1  vlist2  procs
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item homo
\JP $B%U%i%0(B
\EG flag
@end table

@itemize @bullet
\BJP
@item
$BI8=`%i%$%V%i%j$N(B @samp{gr} $B$GDj5A$5$l$F$$$k(B. 
@item
@code{lex_hensel()}, @code{lex_tl()} $B$O(B, 
$BB?9`<0%j%9%H(B @var{plist} $B$N(B, $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B
@var{order} $B$K4X$9$k%0%l%V%J4pDl$r5a$a(B, $B$=$l$r(B, $BJQ?t=g=x(B @var{vlist2}
$B$N<-=q<0=g=x%0%l%V%J4pDl$KJQ49$9$k(B. 
@item
@code{tolex()}, @code{tolex_tl()} $B$O(B, 
$BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B @var{order} $B$K4X$9$k%0%l%V%J4pDl$G$"$k(B
$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
$B4pDl$KJQ49$9$k(B. 
@code{tolex_d()} $B$O(B, @code{tolex()} $B$K$*$1$k(B, $B3F4pDl$N7W;;$r(B, $B;R%W%m%;%9(B
$B%j%9%H(B @var{procs} $B$N3F%W%m%;%9$KJ,;67W;;$5$;$k(B. 
@item
@code{lex_hensel()}, @code{lex_tl()} $B$K$*$$$F$O(B, $B<-=q<0=g=x%0%l%V%J4pDl$N(B
$B7W;;$O<!$N$h$&$K9T$o$l$k(B. (@code{[Noro,Yokoyama]} $B;2>H(B.)
@enumerate
@item
@var{vlist1}, @var{order} $B$K4X$9$k%0%l%V%J4pDl(B @var{G0} $B$r7W;;$9$k(B. 
(@code{lex_hensel()} $B$N$_(B. )
@item
@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
$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
@var{Gp} $B$r7W;;$9$k(B. 
@item
@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. 
@item
@var{Gp} $B$N3F85(B @var{f} $B$K$D$-(B, @var{f} $B$N78?t$rL$Dj78?t$G(B, 
@var{f} $B$N3F9`$rBP1~$9$k(B @var{NF} $B$N85$GCV$-49$((B, $B3F9`$N78?t$r(B 0 $B$HCV$$$?(B,
$BL$Dj78?t$K4X$9$k@~7AJ}Dx<07O(B @var{Lf} $B$r:n$k(B. 
@item
@var{Lf} $B$,(B, $BK!(B @var{p} $B$G0l0U2r$r;}$D$3$H$rMQ$$$F(B @var{Lf} $B$N2r$r(B
$BK!(B @var{p}$B$N2r$+$i(B Hensel $B9=@.$K$h$j5a$a$k(B. 
@item
$B$9$Y$F$N(B @var{Gp} $B$N85$K$D$-@~7AJ}Dx<0$,2r$1$?$i$=$N2rA4BN$,5a$a$k(B
$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, 
@var{p} $B$r$H$jD>$7$F$d$jD>$9(B. 
@end enumerate

@item
@code{lex_tl()}, @code{tolex_tl()} $B$K$*$$$F$O(B, $B<-=q<0=g=x%0%l%V%J4pDl$N(B
$B7W;;$O<!$N$h$&$K9T$o$l$k(B. 

@enumerate
@item
@var{vlist1}, @var{order} $B$K4X$9$k%0%l%V%J4pDl(B @var{G0} $B$r7W;;$9$k(B. 
(@code{lex_hensel()} $B$N$_(B. )
@item
@var{G0} $B$,(B 0 $B<!85%7%9%F%`$G$J$$$H$-(B, @var{G0} $B$rF~NO$H$7$F(B, 
@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
$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
$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
$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. 
@item
@var{G0} $B$,(B 0 $B<!85%7%9%F%`$N$H$-(B, @var{G0} $B$rF~NO$H$7$F(B, 
$B$^$:(B, @var{vlist2} $B$N:G8e$NJQ?t0J30$r>C5n$9$k>C5n=g=x$K$h$j(B
$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
$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
$BF,78?t$r3d$i$J$$AG?t$rMQ$$$?(B trace-lifting $B$G%0%l%V%J4pDl8uJd$r5a$a(B, 
$B$b$75a$^$C$?$i%A%'%C%/$J$7$K$=$l$,$=$N=g=x$G$N%0%l%V%J4pDl$H$J$k(B. 
@end enumerate

@item
$BM-M}<078?t$N7W;;$O(B, @code{lex_tl()}, @code{tolex_tl()} $B$N$_<u$1IU$1$k(B. 
@item
@code{homo} $B$,(B 0 $B$G$J$$>l9g(B, $BFbIt$G5/F0$5$l$k(B Buchberger $B%"%k%4%j%:%`$K(B
$B$*$$$F(B, $B@F<!2=$,9T$o$l$k(B.
@item
@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
$B$*$$$F9T$o$l$?7W;;$KBP1~$7$F$$$F(B, $B;R%W%m%;%9$K$*$1$k;~4V$O4^$^$l$J$$(B. 
\E
\BEG
@item 
These functions are defined in @samp{gr} in the standard library
directory.
@item 
@code{lex_hensel()} and @code{lex_tl()} first compute a Groebner basis
with respect to the variable order @var{vlist1} and the order type @var{order}.
Then the Groebner basis is converted into a lex order Groebner basis
with respect to the varable order @var{vlist2}.
@item 
@code{tolex()} and @code{tolex_tl()} convert a Groebner basis @var{plist}
with respect to the variable order @var{vlist1} and the order type @var{order}
into a lex order Groebner basis
with respect to the varable order @var{vlist2}.
@code{tolex_d()} does computations of basis elements in @code{tolex()}
in parallel on the processes in a child process list @var{procs}.
@item 
In @code{lex_hensel()} and @code{tolex_hensel()} a lex order Groebner basis
is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
@enumerate
@item 
Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
(Only in @code{lex_hensel()}. )
@item 
Choose a prime which does not divide head coefficients of elements in @var{G0}
with respect to @var{vlist1} and @var{order}. Then compute a lex order
Groebner basis @var{Gp} over GF(@var{p}) with respect to @var{vlist2}.
@item 
Compute @var{NF}, the set of all the normal forms with respect to
@var{G0} of terms appearing in @var{Gp}.
@item 
For each element @var{f} in @var{Gp}, replace coefficients and terms in @var{f}
with undetermined coefficients and the corresponding polynomials in @var{NF}
respectively, and generate a system of liear equation @var{Lf} by equating
the coefficients of terms in the replaced polynomial with 0.
@item 
Solve @var{Lf} by Hensel lifting, starting from the unique mod @var{p}
solution.
@item 
If all the linear equations generated from the elements in @var{Gp}
could be solved, then the set of solutions corresponds to a lex order
Groebner basis. Otherwise redo the whole process with another @var{p}.
@end enumerate
      
@item
In @code{lex_tl()} and @code{tolex_tl()} a lex order Groebner basis
is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
      
@enumerate
@item 
Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
(Only in @code{lex_tl()}. )
@item 
If @var{G0} is not zero-dimensional, choose a prime which does not divide
head coefficients of elements in @var{G0} with respect to @var{vlist1} and
@var{order}. Then compute a candidate of a lex order Groebner basis
via trace lifting with @var{p}. If it succeeds the candidate is indeed
a lex order Groebner basis without any check. Otherwise redo the whole
process with another @var{p}.
@item
    
If @var{G0} is zero-dimensional, starting from @var{G0},
compute a Groebner basis @var{G1} with respect to an elimination order
to eliminate variables other than the last varibale in @var{vlist2}.
Then compute a lex order Groebner basis stating from @var{G1}. These
computations are done by trace lifting and the selection of a mudulus
@var{p} is the same as in non zero-dimensional cases.
@end enumerate
      
@item
Computations with rational function coefficients can be done only by
@code{lex_tl()} and @code{tolex_tl()}.
@item 
If @code{homo} is not equal to 0, homogenization is used in Buchberger
algorithm.
@item 
The CPU time shown after an execution of @code{tolex_d()} indicates
that of the master process, and it does not include the time in child
processes.
\E
@end itemize

@example
[78] K=katsura(5)$ 
30msec + gc : 20msec
[79] V=[u5,u4,u3,u2,u1,u0]$
0msec
[80] G0=hgr(K,V,2)$
91.558sec + gc : 15.583sec
[81] G1=lex_hensel(K,V,0,V,0)$
49.049sec + gc : 9.961sec
[82] G2=lex_tl(K,V,0,V,1)$
31.186sec + gc : 3.500sec
[83] gb_comp(G0,G1);
1
10msec
[84] gb_comp(G0,G2);
1
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
\JP @fref{dp_ord}, @fref{$BJ,;67W;;(B}
\EG @fref{dp_ord}, @fref{Distributed computation}
@end table

\JP @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, Functions for Groebner basis computation
@subsection @code{lex_hensel_gsl}, @code{tolex_gsl}, @code{tolex_gsl_d}
@findex lex_hensel_gsl
@findex tolex_gsl
@findex tolex_gsl_d

@table @t
@item lex_hensel_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
\JP :: GSL $B7A<0$N%$%G%"%k4pDl$N7W;;(B
\EG ::Computation of an GSL form ideal basis
@item tolex_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2})
@itemx tolex_gsl_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
\JP :: $B%0%l%V%J4pDl$rF~NO$H$9$k(B, GSL $B7A<0$N%$%G%"%k4pDl$N7W;;(B
\EG :: Computation of an GSL form ideal basis stating from a Groebner basis
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item plist  vlist1  vlist2  procs
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item homo
\JP $B%U%i%0(B
\EG flag
@end table

@itemize @bullet
\BJP
@item
@code{lex_hensel_gsl()} $B$O(B @code{lex_hensel()} $B$N(B, @code{tolex_gsl()} $B$O(B
@code{tolex()} $B$NJQ<o$G(B, $B7k2L$N$_$,0[$J$k(B. 
@code{tolex_gsl_d()} $B$O(B, $B4pDl7W;;$r(B, @code{procs} $B$G;XDj$5$l$k;R%W%m%;%9$K(B
$BJ,;67W;;$5$;$k(B. 
@item
$BF~NO$,(B 0 $B<!85%7%9%F%`$G(B, $B$=$N<-=q<0=g=x%0%l%V%J4pDl$,(B
@code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} $B$O(B
@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, 
@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)
$B$rJV$9(B. 
$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
@code{x0} $B$N(B1 $BJQ?tB?9`<0$G(B, 
$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')]}
$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
$B$h$kDL>o$N%0%l%V%J4pDl$rJV$9(B. 
@item
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
$B$N%0%l%V%J4pDl$h$jHs>o$K>.$5$$$?$a7W;;$bB.$/(B, $B2r$b5a$a$d$9$$(B. 
@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
$B$*$$$F9T$o$l$?7W;;$KBP1~$7$F$$$F(B, $B;R%W%m%;%9$K$*$1$k;~4V$O4^$^$l$J$$(B. 
\E
\BEG
@item 
@code{lex_hensel_gsl()} and @code{lex_hensel()} are variants of
@code{tolex_gsl()} and @code{tolex()} respectively. The results are
Groebner basis or a kind of ideal basis, called GSL form.
@code{tolex_gsl_d()} does basis computations in parallel on child
processes specified in @code{procs}.
      
@item
If the input is zero-dimensional and a lex order Groebner basis has
the form @code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} are
univariate polynomials of @code{x0}; SL form), then this these
functions return a list such as
@code{[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]} (GSL form).  In this list
@code{gi} is a univariate polynomial of @code{x0} such that
@code{di*f0'*fi-gi} divides @code{f0} and the roots of the input ideal is
@code{[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]} for @code{x0}
such that @code{f0(x0)=0}.
If the lex order Groebner basis does not have the above form, 
these functions return
a lex order Groebner basis computed by @code{tolex()}.
@item 
Though an ideal basis represented as GSL form is not a Groebner basis
we can expect that the coefficients are much smaller than those in a Groebner
basis and that the computation is efficient.
The CPU time shown after an execution of @code{tolex_gsl_d()} indicates
that of the master process, and it does not include the time in child
processes.
\E
@end itemize

@example
[103] K=katsura(5)$
[104] V=[u5,u4,u3,u2,u1,u0]$
[105] G0=gr(K,V,0)$
[106] GSL=tolex_gsl(G0,V,0,V)$ 
[107] GSL[0];
[u1,8635837421130477667200000000*u0^31-...]
[108] GSL[1];
[u2,10352277157007342793600000000*u0^31-...]
[109] GSL[5];
[u0,11771021876193064124640000000*u0^32-...,
376672700038178051988480000000*u0^31-...]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
\JP @fref{$BJ,;67W;;(B}
\EG @fref{Distributed computation}
@end table

\JP @node gr_minipoly minipoly,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node gr_minipoly minipoly,,, Functions for Groebner basis computation
@subsection @code{gr_minipoly}, @code{minipoly}
@findex gr_minipoly
@findex minipoly

@table @t
@item gr_minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v},@var{homo})
\JP :: $BB?9`<0$N(B, $B%$%G%"%k$rK!$H$7$?:G>.B?9`<0$N7W;;(B
\EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
@item minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v})
\JP :: $B%0%l%V%J4pDl$rF~NO$H$9$k(B, $BB?9`<0$N:G>.B?9`<0$N7W;;(B
\EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item plist  vlist
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item v
\JP $BITDj85(B
\EG indeterminate
@item homo
\JP $B%U%i%0(B
\EG flag
@end table

@itemize @bullet
\BJP
@item
@code{gr_minipoly()} $B$O%0%l%V%J4pDl$N7W;;$+$i9T$$(B, @code{minipoly()} $B$O(B
$BF~NO$r%0%l%V%J4pDl$H$_$J$9(B. 
@item
$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, 
K[@var{v}] $B$N85(B f(@var{v}) $B$K(B f(@var{p}) mod I $B$rBP1~$5$;$k(B
$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}
$B$N(B, $BK!(B @var{I} $B$G$N:G>.B?9`<0$H8F$V(B. 
@item
@code{gr_minipoly()}, @code{minipoly()} $B$O(B, $BB?9`<0(B @var{p} $B$N:G>.B?9`<0(B
$B$r5a$a(B, @var{v} $B$rJQ?t$H$9$kB?9`<0$H$7$FJV$9(B. 
@item
$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, 
$B:G>.B?9`<0$N$_$r5a$a$?$$>l9g(B, @code{minipoly()}, @code{gr_minipoly()} $B$O(B
$B%0%l%V%J4pDl$rMQ$$$kJ}K!$KHf$Y$F8zN($,$h$$(B. 
@item
@code{gr_minipoly()} $B$K;XDj$9$k9`=g=x$H$7$F$O(B, $BDL>oA4<!?t5U<-=q<0=g=x$r(B
$BMQ$$$k(B. 
\E
\BEG
@item 
@code{gr_minipoly()} begins by computing a Groebner basis.
@code{minipoly()} regards an input as a Groebner basis with respect to
the variable order @var{vlist} and the order type @var{order}.
@item 
Let K be a field. If an ideal @var{I} in K[X] is zero-dimensional, then, for
a polynomial @var{p} in K[X], the kernel of a homomorphism from
K[@var{v}] to K[X]/@var{I} which maps f(@var{v}) to f(@var{p}) mod @var{I}
is generated by a polynomial. The generator is called the minimal polynomial
of @var{p} modulo @var{I}.
@item 
@code{gr_minipoly()} and @code{minipoly()} computes the minimal polynomial
of a polynomial @var{p} and returns it as a polynomial of @var{v}.
@item 
The minimal polynomial can be computed as an element of a Groebner basis.
But if we are only interested in the minimal polynomial,
@code{minipoly()} and @code{gr_minipoly()} can compute it more efficiently
than methods using Groebner basis computation.
@item 
It is recommended to use a degree reverse lex order as a term order
for @code{gr_minipoly()}.
\E
@end itemize

@example
[117] G=tolex(G0,V,0,V)$      
43.818sec + gc : 11.202sec
[118] GSL=tolex_gsl(G0,V,0,V)$
17.123sec + gc : 2.590sec
[119] MP=minipoly(G0,V,0,u0,z)$
4.370sec + gc : 780msec
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl}.
@end table

\JP @node tolexm minipolym,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node tolexm minipolym,,, Functions for Groebner basis computation
@subsection @code{tolexm}, @code{minipolym}
@findex tolexm
@findex minipolym

@table @t
@item tolexm(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{mod})
\JP :: $BK!(B @var{mod} $B$G$N4pDlJQ49$K$h$k%0%l%V%J4pDl7W;;(B
\EG :: Groebner basis computation modulo @var{mod} by change of ordering.
@item minipolym(@var{plist},@var{vlist1},@var{order},@var{poly},@var{v},@var{mod})
\JP :: $BK!(B @var{mod} $B$G$N%0%l%V%J4pDl$K$h$kB?9`<0$N:G>.B?9`<0$N7W;;(B
\EG :: Minimal polynomial computation modulo @var{mod} the same method as
@end table

@table @var
@item return
\JP @code{tolexm()} : $B%j%9%H(B, @code{minipolym()} : $BB?9`<0(B
\EG @code{tolexm()} : list, @code{minipolym()} : polynomial
@item plist  vlist1  vlist2
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
$BF~NO(B @var{plist} $B$O$$$:$l$b(B $BJQ?t=g=x(B @var{vlist1}, $B9`=g=x7?(B @var{order},
$BK!(B @var{mod} $B$K$*$1$k%0%l%V%J4pDl$G$J$1$l$P$J$i$J$$(B. 
@item
@code{minipolym()} $B$O(B @code{minipoly} $B$KBP1~$9$k7W;;$rK!(B @var{mod}$B$G9T$&(B. 
@item
@code{tolexm()} $B$O(B FGLM $BK!$K$h$k4pDlJQ49$K$h$j(B @var{vlist2},
$B<-=q<0=g=x$K$h$k%0%l%V%J4pDl$r7W;;$9$k(B. 
\E
\BEG
@item 
An input @var{plist} must be a Groebner basis modulo @var{mod}
with respect to the variable order @var{vlist1} and the order type @var{order}.
@item 
@code{minipolym()} executes the same computation as in @code{minipoly}.
@item 
@code{tolexm()} computes a lex order Groebner basis modulo @var{mod}
with respect to the variable order @var{vlist2}, by using FGLM algorithm.
\E
@end itemize

@example
[197] tolexm(G0,V,0,V,31991);
[8271*u0^31+10435*u0^30+816*u0^29+26809*u0^28+...,...]
[198] minipolym(G0,V,0,u0,z,31991);
z^32+11405*z^31+20868*z^30+21602*z^29+...
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
@fref{gr_minipoly minipoly}.
@end table

\JP @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, Functions for Groebner basis computation
@subsection @code{dp_gr_main}, @code{dp_gr_mod_main}, @code{dp_gr_f_main}, @code{dp_weyl_gr_main}, @code{dp_weyl_gr_mod_main}, @code{dp_weyl_gr_f_main}
@findex dp_gr_main
@findex dp_gr_mod_main
@findex dp_gr_f_main
@findex dp_weyl_gr_main
@findex dp_weyl_gr_mod_main
@findex dp_weyl_gr_f_main

@table @t
@item dp_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
@itemx dp_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
@itemx dp_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
@itemx dp_weyl_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
@itemx dp_weyl_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
@itemx dp_weyl_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
\JP :: $B%0%l%V%J4pDl$N7W;;(B ($BAH$_9~$_H!?t(B)
\EG :: Groebner basis computation (built-in functions)
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item plist  vlist
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item homo
\JP $B%U%i%0(B
\EG flag
@item modular
\JP $B%U%i%0$^$?$OAG?t(B
\EG flag or prime
@end table

@itemize @bullet
\BJP
@item
$B$3$l$i$NH!?t$O(B, $B%0%l%V%J4pDl7W;;$N4pK\E*AH$_9~$_H!?t$G$"$j(B, @code{gr()},
@code{hgr()}, @code{gr_mod()} $B$J$I$O$9$Y$F$3$l$i$NH!?t$r8F$S=P$7$F7W;;(B
$B$r9T$C$F$$$k(B. $B4X?tL>$K(B weyl $B$,F~$C$F$$$k$b$N$O(B, Weyl $BBe?t>e$N7W;;(B
$B$N$?$a$N4X?t$G$"$k(B. 
@item
@code{dp_gr_f_main()}, @code{dp_weyl_f_main()} $B$O(B, $B<o!9$NM-8BBN>e$N%0%l%V%J4pDl$r7W;;$9$k(B
$B>l9g$KMQ$$$k(B. $BF~NO$O(B, $B$"$i$+$8$a(B, @code{simp_ff()} $B$J$I$G(B, 
$B9M$($kM-8BBN>e$K<M1F$5$l$F$$$kI,MW$,$"$k(B. 
@item
$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
$B$r<B9T$9$k(B. 
@item
@code{dp_gr_mod_main()} $B$KBP$7$F$O(B, @var{modular} $B$O(B, GF(@var{modular}) $B>e(B
$B$G$N7W;;$r0UL#$9$k(B. 
@code{dp_gr_main()} $B$KBP$7$F$O(B, @var{modular} $B$O<!$N$h$&$J0UL#$r;}$D(B. 
@enumerate
@item
@var{modular} $B$,(B 1 $B$N;~(B, trace-lifting $B$K$h$k7W;;$r9T$&(B. $BAG?t$O(B
@code{lprime(0)} $B$+$i=g$K@.8y$9$k$^$G(B @code{lprime()} $B$r8F$S=P$7$F@8@.$9$k(B. 
@item
@var{modular} $B$,(B 2 $B0J>e$N<+A3?t$N;~(B, $B$=$NCM$rAG?t$H$_$J$7$F(B trace-lifting
$B$r9T$&(B. $B$=$NAG?t$G<:GT$7$?>l9g(B, 0 $B$rJV$9(B. 
@item
@var{modular} $B$,Ii$N>l9g(B, 
@var{-modular} $B$KBP$7$F>e=R$N5,B'$,E,MQ$5$l$k$,(B, trace-lifting $B$N:G=*(B
$BCJ3,$N%0%l%V%J4pDl%A%'%C%/$H%$%G%"%k%a%s%P%7%C%W%A%'%C%/$,>JN,$5$l$k(B. 
@end enumerate

@item
@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
@code{dp_gr_main(P,V,1,1,O)}, @code{gr_mod(P,V,O,M)} $B$O(B
@code{dp_gr_mod_main(P,V,0,M,O)} $B$r$=$l$>$l<B9T$9$k(B. 
@item
@var{homo}, @var{modular} $B$NB>$K(B, @code{dp_gr_flags()} $B$G@_Dj$5$l$k(B
$B$5$^$6$^$J%U%i%0$K$h$j7W;;$,@)8f$5$l$k(B. 
\E
\BEG
@item
These functions are fundamental built-in functions for Groebner basis
computation and @code{gr()},@code{hgr()} and @code{gr_mod()}
are all interfaces to these functions. Functions whose names
contain weyl are those for computation in Weyl algebra.
@item
@code{dp_gr_f_main()} and @code{dp_weyl_gr_f_main()}
are functions for Groebner basis computation
over various finite fields. Coefficients of input polynomials 
must be converted to elements of a finite field 
currently specified by @code{setmod_ff()}.
@item
If @var{homo} is not equal to 0, homogenization is applied before entering
Buchberger algorithm
@item
For @code{dp_gr_mod_main()}, @var{modular} means a computation over
GF(@var{modular}).
For @code{dp_gr_main()}, @var{modular} has the following mean.
@enumerate
@item
If @var{modular} is 1 , trace lifting is used. Primes for trace lifting
are generated by @code{lprime()}, starting from @code{lprime(0)}, until
the computation succeeds.
@item
If @var{modular} is an integer  greater than 1, the integer is regarded as a
prime and trace lifting is executed by using the prime. If the computation
fails then 0 is returned.
@item
If @var{modular} is negative, the above rule is applied for @var{-modular}
but the Groebner basis check and ideal-membership check are omitted in
the last stage of trace lifting.
@end enumerate
     
@item
@code{gr(P,V,O)}, @code{hgr(P,V,O)} and @code{gr_mod(P,V,O,M)} execute
@code{dp_gr_main(P,V,0,1,O)}, @code{dp_gr_main(P,V,1,1,O)}
and @code{dp_gr_mod_main(P,V,0,M,O)} respectively.
@item
Actual computation is controlled by various parameters set by 
@code{dp_gr_flags()}, other then by @var{homo} and @var{modular}.
\E
@end itemize

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_ord},
@fref{dp_gr_flags dp_gr_print},
@fref{gr hgr gr_mod},
@fref{setmod_ff},
\JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}.
\EG @fref{Controlling Groebner basis computations}
@end table

\JP @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, Functions for Groebner basis computation
@subsection @code{dp_f4_main}, @code{dp_f4_mod_main}, @code{dp_weyl_f4_main}, @code{dp_weyl_f4_mod_main}
@findex dp_f4_main
@findex dp_f4_mod_main
@findex dp_weyl_f4_main
@findex dp_weyl_f4_mod_main

@table @t
@item dp_f4_main(@var{plist},@var{vlist},@var{order})
@itemx dp_f4_mod_main(@var{plist},@var{vlist},@var{order})
@itemx dp_weyl_f4_main(@var{plist},@var{vlist},@var{order})
@itemx dp_weyl_f4_mod_main(@var{plist},@var{vlist},@var{order})
\JP :: F4 $B%"%k%4%j%:%`$K$h$k%0%l%V%J4pDl$N7W;;(B ($BAH$_9~$_H!?t(B)
\EG :: Groebner basis computation by F4 algorithm (built-in functions)
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item plist  vlist
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@end table

@itemize @bullet
\BJP
@item
F4 $B%"%k%4%j%:%`$K$h$j%0%l%V%J4pDl$N7W;;$r9T$&(B. 
@item
F4 $B%"%k%4%j%:%`$O(B, J.C. Faugere $B$K$h$jDs>'$5$l$??7@$Be%0%l%V%J4pDl(B
$B;;K!$G$"$j(B, $BK\<BAu$O(B, $BCf9q>jM>DjM}$K$h$k@~7AJ}Dx<05a2r$rMQ$$$?(B
$B;n83E*$J<BAu$G$"$k(B. 
@item
$B@F<!2=$N0z?t$,$J$$$3$H$r=|$1$P(B, $B0z?t$*$h$SF0:n$O$=$l$>$l(B 
@code{dp_gr_main()}, @code{dp_gr_mod_main()},
@code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()}
$B$HF1MM$G$"$k(B. 
\E
\BEG
@item
These functions compute Groebner bases by F4 algorithm.
@item
F4 is a new generation algorithm for Groebner basis computation
invented by J.C. Faugere. The current implementation of @code{dp_f4_main()}
uses Chinese Remainder theorem and not highly optimized.
@item
Arguments and actions are the same as those of 
@code{dp_gr_main()}, @code{dp_gr_mod_main()},
@code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()},
except for lack of the argument for controlling homogenization.
\E
@end itemize

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_ord},
@fref{dp_gr_flags dp_gr_print},
@fref{gr hgr gr_mod},
\JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}.
\EG @fref{Controlling Groebner basis computations}
@end table

\JP @node dp_gr_flags dp_gr_print,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_gr_flags dp_gr_print,,, Functions for Groebner basis computation
@subsection @code{dp_gr_flags}, @code{dp_gr_print}
@findex dp_gr_flags
@findex dp_gr_print

@table @t
@item dp_gr_flags([@var{list}])
@itemx dp_gr_print([@var{i}])
\JP :: $B7W;;$*$h$SI=<(MQ%Q%i%a%?$N@_Dj(B, $B;2>H(B
\BEG :: Set and show various parameters for cotrolling computations 
and showing informations.
\E
@end table

@table @var
@item return
\JP $B@_DjCM(B
\EG value currently set
@item list
\JP $B%j%9%H(B
\EG list
@item i
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
@code{dp_gr_main()}, @code{dp_gr_mod_main()}, @code{dp_gr_f_main()}  $B<B9T;~$K$*$1$k$5$^$6$^(B
$B$J%Q%i%a%?$r@_Dj(B, $B;2>H$9$k(B. 
@item
$B0z?t$,$J$$>l9g(B, $B8=:_$N@_Dj$,JV$5$l$k(B. 
@item
$B0z?t$O(B, @code{["Print",1,"NoSugar",1,...]} $B$J$k7A$N%j%9%H$G(B, $B:8$+$i=g$K(B
$B@_Dj$5$l$k(B. $B%Q%i%a%?L>$OJ8;zNs$GM?$($kI,MW$,$"$k(B. 
@item
@code{dp_gr_print()} $B$O(B, $BFC$K%Q%i%a%?(B @code{Print}, @code{PrintShort} $B$NCM$rD>@\@_Dj(B, $B;2>H(B
$B$G$-$k(B. $B@_Dj$5$l$kCM$O<!$NDL$j$G$"$k!#(B
@table @var
@item i=0
@code{Print=0}, @code{PrintShort=0}
@item i=1
@code{Print=1}, @code{PrintShort=0}
@item i=2
@code{Print=0}, @code{PrintShort=1}
@end table
$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
$BH!?t$K$*$$$F(B, $B$=$N%5%V%k!<%A%s$,Cf4V>pJs$NI=<((B
$B$r9T$&:]$K(B, $B?WB.$K%U%i%0$r8+$k$3$H$,$G$-$k$h$&$KMQ0U$5$l$F$$$k(B. 
\E
\BEG
@item
@code{dp_gr_flags()} sets and shows various parameters for Groebner basis
 computation.
@item
If no argument is specified the current settings are returned.
@item
Arguments must be specified as a list such as
 @code{["Print",1,"NoSugar",1,...]}. Names of parameters must be character
strings.
@item
@code{dp_gr_print()} is used to set and show the value of a parameter
@code{Print} and @code{PrintShort}. 
@table @var
@item i=0
@code{Print=0}, @code{PrintShort=0}
@item i=1
@code{Print=1}, @code{PrintShort=0}
@item i=2
@code{Print=0}, @code{PrintShort=1}
@end table
This functions is prepared to get quickly the value
when a user defined function calling @code{dp_gr_main()} etc.
uses the value as a flag for showing intermediate informations.
\E
@end itemize

@table @t
\JP @item $B;2>H(B
\EG @item References
\JP @fref{$B7W;;$*$h$SI=<($N@)8f(B}
\EG @fref{Controlling Groebner basis computations}
@end table

\JP @node dp_ord,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_ord,,, Functions for Groebner basis computation
@subsection @code{dp_ord}
@findex dp_ord

@table @t
@item dp_ord([@var{order}])
\JP :: $BJQ?t=g=x7?$N@_Dj(B, $B;2>H(B
\EG :: Set and show the ordering type.
@end table

@table @var
@item return
\JP $BJQ?t=g=x7?(B ($B?t(B, $B%j%9%H$^$?$O9TNs(B)
\EG ordering type (number, list or matrix)
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@end table

@itemize @bullet
\BJP
@item
$B0z?t$,$"$k;~(B, $BJQ?t=g=x7?$r(B @var{order} $B$K@_Dj$9$k(B. $B0z?t$,$J$$;~(B, 
$B8=:_@_Dj$5$l$F$$$kJQ?t=g=x7?$rJV$9(B. 

@item
$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
$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
$B9T$o$l$k(B. 

@item
@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()}
$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. 

@item
$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, 
$B$=$NB?9`<0$,@8@.$5$l$?;~E@$K$*$1$kJQ?t=g=x7?$,(B, $B;MB'1i;;;~$K@5$7$/@_Dj(B
$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
$B7?$K4p$E$$$F@8@.$5$l$?$b$N$G$J$1$l$P$J$i$J$$(B. 

@item
$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
$BJQ?t=g=x7?$r@5$7$/@_Dj$7$J$1$l$P$J$i$J$$(B. 
\E
\BEG
@item
If an argument is specified, the function
sets the current ordering type to @var{order}.
If no argument is specified, the function returns the ordering
type currently set.
     
@item
There are two types of functions concerning distributed polynomial,
functions which take a ordering type and those which don't take it.
The latter ones use the current setting.
     
@item
Functions such as @code{gr()}, which need a ordering type as an argument,
call @code{dp_ord()} internally during the execution.
The setting remains after the execution.
     
Fundamental arithmetics for distributed polynomial also use the current
setting. Therefore, when such arithmetics for distributed polynomials
are done, the current setting must coincide with the ordering type
which was used upon the creation of the polynomials. It is assumed
that such polynomials were generated under the same ordering type.
     
@item
Type of term ordering must be correctly set by this function
when functions other than top level functions are called directly.
\E
@end itemize

@example
[19] dp_ord(0)$          
[20] <<1,2,3>>+<<3,1,1>>;
(1)*<<1,2,3>>+(1)*<<3,1,1>>
[21] dp_ord(2)$          
[22] <<1,2,3>>+<<3,1,1>>;
(1)*<<3,1,1>>+(1)*<<1,2,3>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
\JP @fref{$B9`=g=x$N@_Dj(B}
\EG @fref{Setting term orderings}
@end table

\JP @node dp_ptod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_ptod,,, Functions for Groebner basis computation
@subsection @code{dp_ptod}
@findex dp_ptod

@table @t
@item dp_ptod(@var{poly},@var{vlist})
\JP :: $BB?9`<0$rJ,;6I=8=B?9`<0$KJQ49$9$k(B. 
\EG :: Converts an ordinary polynomial into a distributed polynomial.
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item vlist
\JP $B%j%9%H(B
\EG list
@end table

@itemize @bullet
\BJP
@item
$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. 
@item
@var{vlist} $B$K4^$^$l$J$$ITDj85$O(B, $B78?tBN$KB0$9$k$H$7$FJQ49$5$l$k(B. 
\E
\BEG
@item
According to the variable ordering @var{vlist} and current
type of term ordering, this function converts an ordinary
polynomial into a distributed polynomial.
@item
Indeterminates not included in @var{vlist} are regarded to belong to
the coefficient field.
\E
@end itemize

@example
[50] dp_ord(0);
1
[51] dp_ptod((x+y+z)^2,[x,y,z]);
(1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
+(1)*<<0,0,2>>
[52] dp_ptod((x+y+z)^2,[x,y]);  
(1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
+(z^2)*<<0,0>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_dtop},
@fref{dp_ord}.
@end table

\JP @node dp_dtop,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_dtop,,, Functions for Groebner basis computation
@subsection @code{dp_dtop}
@findex dp_dtop

@table @t
@item dp_dtop(@var{dpoly},@var{vlist})
\JP :: $BJ,;6I=8=B?9`<0$rB?9`<0$KJQ49$9$k(B. 
\EG :: Converts a distributed polynomial into an ordinary polynomial.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item vlist
\JP $B%j%9%H(B
\EG list
@end table

@itemize @bullet
\BJP
@item
$BJ,;6I=8=B?9`<0$r(B, $BM?$($i$l$?ITDj85%j%9%H$rMQ$$$FB?9`<0$KJQ49$9$k(B. 
@item
$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. 
\E
\BEG
@item
This function converts a distributed polynomial into an ordinary polynomial
according to a list of indeterminates @var{vlist}.
@item
@var{vlist} is such a list that its length coincides with the number of
variables of @var{dpoly}.
\E
@end itemize

@example
[53] T=dp_ptod((x+y+z)^2,[x,y]);
(1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
+(z^2)*<<0,0>>
[54] P=dp_dtop(T,[a,b]);
z^2+(2*a+2*b)*z+a^2+2*b*a+b^2
@end example

\JP @node dp_mod dp_rat,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_mod dp_rat,,, Functions for Groebner basis computation
@subsection @code{dp_mod}, @code{dp_rat}
@findex dp_mod
@findex dp_rat

@table @t
@item dp_mod(@var{p},@var{mod},@var{subst})
\JP :: $BM-M}?t78?tJ,;6I=8=B?9`<0$NM-8BBN78?t$X$NJQ49(B
\EG :: Converts a disributed polynomial into one with coefficients in a finite field.
@item dp_rat(@var{p})
\JP :: $BM-8BBN78?tJ,;6I=8=B?9`<0$NM-M}?t78?t$X$NJQ49(B
\BEG
:: Converts a distributed polynomial with coefficients in a finite field into
one with coefficients in the rationals.
\E
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item p
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item mod
\JP $BAG?t(B
\EG prime
@item subst
\JP $B%j%9%H(B
\EG list
@end table

@itemize @bullet
\BJP
@item
@code{dp_nf_mod()}, @code{dp_true_nf_mod()} $B$O(B, $BF~NO$H$7$FM-8BBN78?t$N(B
$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
$BM-M}?t78?tJ,;6I=8=B?9`<0$rJQ49$7$FMQ$$$k$3$H$,$G$-$k(B. $B$^$?(B, $BF@$i$l$?(B
$B7k2L$O(B, $BM-8BBN78?tB?9`<0$H$O1i;;$G$-$k$,(B, $BM-M}?t78?tB?9`<0$H$O1i;;$G$-$J$$(B
$B$?$a(B, @code{dp_rat()} $B$K$h$jJQ49$9$kI,MW$,$"$k(B. 
@item
$BM-8BBN78?t$N1i;;$K$*$$$F$O(B, $B$"$i$+$8$a(B @code{setmod()} $B$K$h$jM-8BBN$N85$N(B
$B8D?t$r;XDj$7$F$*$/I,MW$,$"$k(B. 
@item
@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
$B$7$?8eM-8BBN78?t$KJQ49$9$k$H$$$&A`:n$r9T$&:]$N(B, $BBeF~CM$r;XDj$9$k$b$N$G(B, 
@code{[[@var{var},@var{value}],...]} $B$N7A$N%j%9%H$G$"$k(B. 
\E
\BEG
@item
@code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
distributed polynomials with coefficients in a finite field as arguments.
@code{dp_mod()} is used to convert distributed polynomials with rational
number coefficients into appropriate ones.
Polynomials with coefficients in a finite field
cannot be used as inputs of operations with polynomials
with rational number coefficients. @code{dp_rat()} is used for such cases.
@item
The ground finite field must be set in advance by using @code{setmod()}.
@item
@var{subst} is such a list as @code{[[@var{var},@var{value}],...]}.
This is valid when the ground field of the input polynomial is a
rational function field. @var{var}'s are variables in the ground field and
the list means that @var{value} is substituted for @var{var} before
converting the coefficients into elements of a finite field.
\E
@end itemize

@example
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod},
@fref{subst psubst},
@fref{setmod}.
@end table

\JP @node dp_homo dp_dehomo,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_homo dp_dehomo,,, Functions for Groebner basis computation
@subsection @code{dp_homo}, @code{dp_dehomo}
@findex dp_homo
@findex dp_dehomo

@table @t
@item dp_homo(@var{dpoly})
\JP :: $BJ,;6I=8=B?9`<0$N@F<!2=(B
\EG :: Homogenize a distributed polynomial
@item dp_dehomo(@var{dpoly})
\JP :: $B@F<!J,;6I=8=B?9`<0$NHs@F<!2=(B
\EG :: Dehomogenize a homogenious distributed polynomial
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
@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
1 $B?-$P$7(B, $B:G8e$N@.J,$NCM$r(B @var{d}-@code{deg(@var{t})} 
(@var{d} $B$O(B @var{dpoly} $B$NA4<!?t(B) $B$H$7$?J,;6I=8=B?9`<0$rJV$9(B. 
@item
@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
$B$r<h$j=|$$$?J,;6B?9`<0$rJV$9(B. 
@item
$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
$B@5$7$/@_Dj$9$kI,MW$,$"$k(B. 
@item
@code{hgr()} $B$J$I$K$*$$$F(B, $BFbItE*$KMQ$$$i$l$F$$$k(B.
\E
\BEG
@item
@code{dp_homo()} makes a copy of @var{dpoly}, extends
the length of the exponent vector of each term @var{t} in the copy by 1,
and sets the value of the newly appended
component to @var{d}-@code{deg(@var{t})}, where @var{d} is the total
degree of @var{dpoly}.
@item
@code{dp_dehomo()} make a copy of @var{dpoly} and removes the last component
of each terms in the copy.
@item
Appropriate term orderings must be set when the results are used as inputs
of some operations.
@item
These are used internally in @code{hgr()} etc.
\E
@end itemize

@example
[202] X=<<1,2,3>>+3*<<1,2,1>>;
(1)*<<1,2,3>>+(3)*<<1,2,1>>
[203] dp_homo(X);
(1)*<<1,2,3,0>>+(3)*<<1,2,1,2>>
[204] dp_dehomo(@@);
(1)*<<1,2,3>>+(3)*<<1,2,1>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{gr hgr gr_mod}.
@end table

\JP @node dp_ptozp dp_prim,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_ptozp dp_prim,,, Functions for Groebner basis computation
@subsection @code{dp_ptozp}, @code{dp_prim}
@findex dp_ptozp
@findex dp_prim

@table @t
@item dp_ptozp(@var{dpoly})
\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. 
\BEG
:: Converts a distributed polynomial @var{poly} with rational coefficients
into an integral distributed polynomial such that GCD of all its coefficients
is 1.
\E
@itemx dp_prim(@var{dpoly})
\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. 
\BEG
:: Converts a distributed polynomial @var{poly} with rational function
coefficients into an integral distributed polynomial such that polynomial 
GCD of all its coefficients is 1.
\E
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
@code{dp_ptozp()} $B$O(B,  @code{ptozp()} $B$KAjEv$9$kA`:n$rJ,;6I=8=B?9`<0$K(B
$BBP$7$F9T$&(B. $B78?t$,B?9`<0$r4^$`>l9g(B, $B78?t$K4^$^$l$kB?9`<06&DL0x;R$O(B
$B<h$j=|$+$J$$(B. 
@item
@code{dp_prim()} $B$O(B, $B78?t$,B?9`<0$r4^$`>l9g(B, $B78?t$K4^$^$l$kB?9`<06&DL0x;R(B
$B$r<h$j=|$/(B. 
\E
\BEG
@item
@code{dp_ptozp()} executes the same operation as @code{ptozp()} for
a distributed polynomial. If the coefficients include polynomials,
polynomial contents included in the coefficients are not removed.
@item
@code{dp_prim()} removes polynomial contents.
\E
@end itemize

@example
[208] X=dp_ptod(3*(x-y)*(y-z)*(z-x),[x]);
(-3*y+3*z)*<<2>>+(3*y^2-3*z^2)*<<1>>+(-3*z*y^2+3*z^2*y)*<<0>>
[209] dp_ptozp(X);                       
(-y+z)*<<2>>+(y^2-z^2)*<<1>>+(-z*y^2+z^2*y)*<<0>>
[210] dp_prim(X);                        
(1)*<<2>>+(-y-z)*<<1>>+(z*y)*<<0>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{ptozp}.
@end table

\JP @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod,,, Functions for Groebner basis computation
@subsection @code{dp_nf}, @code{dp_nf_mod}, @code{dp_true_nf}, @code{dp_true_nf_mod}
@findex dp_nf
@findex  dp_true_nf
@findex dp_nf_mod
@findex  dp_true_nf_mod

@table @t
@item dp_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
@item dp_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
\JP :: $BJ,;6I=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B7k2L$ODj?tG\$5$l$F$$$k2DG=@-$"$j(B)

\BEG
:: Computes the normal form of a distributed polynomial.
(The result may be multiplied by a constant in the ground field.)
\E
@item dp_true_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
@item dp_true_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
\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)
\BEG
:: Computes the normal form of a distributed polynomial. (The true result
is returned in such a list as @code{[numerator, denominator]})
\E
@end table

@table @var
@item return
\JP @code{dp_nf()} : $BJ,;6I=8=B?9`<0(B, @code{dp_true_nf()} : $B%j%9%H(B
\EG @code{dp_nf()} : distributed polynomial, @code{dp_true_nf()} : list
@item indexlist
\JP $B%j%9%H(B
\EG list
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpolyarray
\JP $BG[Ns(B
\EG array of distributed polynomial
@item fullreduce
\JP $B%U%i%0(B
\EG flag
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
$BJ,;6I=8=B?9`<0(B @var{dpoly} $B$N@55,7A$r5a$a$k(B. 
@item
@code{dp_nf_mod()}, @code{dp_true_nf_mod()} $B$NF~NO$O(B, @code{dp_mod()} $B$J$I(B
$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. 
@item
$B7k2L$KM-M}?t(B, $BM-M}<0$,4^$^$l$k$N$rHr$1$k$?$a(B, @code{dp_nf()} $B$O(B
$B??$NCM$NDj?tG\$NCM$rJV$9(B. $BM-M}<078?t$N>l9g$N(B @code{dp_nf_mod()} $B$bF1MM(B
$B$G$"$k$,(B, $B78?tBN$,M-8BBN$N>l9g(B @code{dp_nf_mod()} $B$O??$NCM$rJV$9(B. 
@item
@code{dp_true_nf()}, @code{dp_true_nf_mod()} $B$O(B, 
@code{[@var{nm},@var{dn}]} $B$J$k7A$N%j%9%H$rJV$9(B. 
$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
$B?t$^$?$OB?9`<0$G(B @var{nm}/@var{dn} $B$,??$NCM$H$J$k(B. 
@item
@var{dpolyarray} $B$OJ,;6I=8=B?9`<0$rMWAG$H$9$k%Y%/%H%k(B, 
@var{indexlist} $B$O@55,2=7W;;$KMQ$$$k(B @var{dpolyarray} $B$NMWAG$N%$%s%G%C%/%9(B
$B$N%j%9%H(B. 
@item
@var{fullreduce} $B$,(B 0 $B$G$J$$$H$-A4$F$N9`$KBP$7$F4JLs$r9T$&(B. @var{fullreduce}
$B$,(B 0 $B$N$H$-F,9`$N$_$KBP$7$F4JLs$r9T$&(B. 
@item
@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. 
@item
$B0lHL$K$O(B @var{indexlist} $B$NM?$(J}$K$h$jH!?t$NCM$O0[$J$k2DG=@-$,$"$k$,(B, 
$B%0%l%V%J4pDl$KBP$7$F$O0l0UE*$KDj$^$k(B. 
@item
$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
$B$KJXMx$G$"$k(B. $BC10l$N1i;;$K4X$7$F$O(B, @code{p_nf}, @code{p_true_nf} $B$r(B
$BMQ$$$k$H$h$$(B. 
\E
\BEG
@item
Computes the normal form of a distributed polynomial.
@item
@code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
distributed polynomials with coefficients in a finite field as arguments.
@item
The result of @code{dp_nf()} may be multiplied by a constant in the
ground field in order to make the result integral. The same is true
for @code{dp_nf_mod()}, but it returns the true normal form if
the ground field is a finite field.
@item
@code{dp_true_nf()} and @code{dp_true_nf_mod()} return
such a list as @code{[@var{nm},@var{dn}]}.
Here @var{nm} is a distributed polynomial whose coefficients are integral
in the ground field, @var{dn} is an integral element in the ground
field and @var{nm}/@var{dn} is the true normal form.
@item
@var{dpolyarray} is a vector whose components are distributed polynomials
and @var{indexlist} is a list of indices which is used for the normal form
computation.
@item
When argument @var{fullreduce} has non-zero value,
all terms are reduced. When it has value 0,
only the head term is reduced.
@item
As for the polynomials specified by @var{indexlist}, one specified by
an index placed at the preceding position has priority to be selected.
@item
In general, the result of the function may be different depending on
@var{indexlist}.  However, the result is unique for Groebner bases.
@item
These functions are useful when a fixed non-distributed polynomial set
is used as a set of reducers to compute normal forms of many polynomials.
For single computation @code{p_nf} and @code{p_true_nf} are sufficient.
\E
@end itemize

@example
[0] load("gr")$
[64] load("katsura")$
[69] K=katsura(4)$
[70] dp_ord(2)$
[71] V=[u0,u1,u2,u3,u4]$
[72] DP1=newvect(length(K),map(dp_ptod,K,V))$
[73] G=gr(K,V,2)$
[74] DP2=newvect(length(G),map(dp_ptod,G,V))$
[75] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
[76] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
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
[77] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
-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
[78] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
-11380879768451657780886122972730785203470970010204714556333530492210
456775930005716505560062087150928400876150217079820311439477560587583
488*u4^15+...
[79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
-11380879768451657780886122972730785203470970010204714556333530492210
456775930005716505560062087150928400876150217079820311439477560587583
488*u4^15+...
[80] @@78==@@79;
1
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_dtop},
@fref{dp_ord},
@fref{dp_mod dp_rat},
@fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
@end table

\JP @node dp_hm dp_ht dp_hc dp_rest,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_hm dp_ht dp_hc dp_rest,,, Functions for Groebner basis computation
@subsection @code{dp_hm}, @code{dp_ht}, @code{dp_hc}, @code{dp_rest}
@findex dp_hm
@findex dp_ht
@findex dp_hc
@findex dp_rest

@table @t
@item dp_hm(@var{dpoly})
\JP :: $BF,C19`<0$r<h$j=P$9(B. 
\EG :: Gets the head monomial.
@item dp_ht(@var{dpoly})
\JP :: $BF,9`$r<h$j=P$9(B. 
\EG :: Gets the head term.
@item dp_hc(@var{dpoly})
\JP :: $BF,78?t$r<h$j=P$9(B. 
\EG :: Gets the head coefficient.
@item dp_rest(@var{dpoly})
\JP :: $BF,C19`<0$r<h$j=|$$$?;D$j$rJV$9(B. 
\EG :: Gets the remainder of the polynomial where the head monomial is removed.
@end table

@table @var
\BJP
@item return
@code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : $BJ,;6I=8=B?9`<0(B,
@code{dp_hc()} : $B?t$^$?$OB?9`<0(B
@item dpoly
$BJ,;6I=8=B?9`<0(B
\E
\BEG
@item return
@code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : distributed polynomial
@code{dp_hc()} : number or polynomial
@item dpoly
distributed polynomial
\E
@end table

@itemize @bullet
\BJP
@item
$B$3$l$i$O(B, $BJ,;6I=8=B?9`<0$N3FItJ,$r<h$j=P$9$?$a$NH!?t$G$"$k(B. 
@item
$BJ,;6I=8=B?9`<0(B @var{p} $B$KBP$7<!$,@.$jN)$D(B. 
\E
\BEG
@item
These are used to get various parts of a distributed polynomial.
@item
The next equations hold for a distributed polynomial @var{p}.
\E
@table @code
@item @var{p} = dp_hm(@var{p}) + dp_rest(@var{p})
@item dp_hm(@var{p}) = dp_hc(@var{p}) dp_ht(@var{p})
@end table
@end itemize

@example
[87] dp_ord(0)$
[88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
[89] T=dp_ptod(X,[u3,u4,a46])$                                        
[90] dp_hm(T);                                                        
(2160)*<<4,0,2>>
[91] dp_ht(T);
(1)*<<4,0,2>>
[92] dp_hc(T);
2160
[93] dp_rest(T);
(1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
+(-490)*<<0,0,0>>
@end example

\JP @node dp_td dp_sugar,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_td dp_sugar,,, Functions for Groebner basis computation
@subsection @code{dp_td}, @code{dp_sugar}
@findex dp_td
@findex dp_sugar

@table @t
@item dp_td(@var{dpoly})
\JP :: $BF,9`$NA4<!?t$rJV$9(B. 
\EG :: Gets the total degree of the head term.
@item dp_sugar(@var{dpoly})
\JP :: $BB?9`<0$N(B @code{sugar} $B$rJV$9(B. 
\EG :: Gets the @code{sugar} of a polynomial.
@end table

@table @var
@item return
\JP $B<+A3?t(B
\EG non-negative integer
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item onoff
\JP $B%U%i%0(B
\EG flag
@end table

@itemize @bullet
\BJP
@item
@code{dp_td()} $B$O(B, $BF,9`$NA4<!?t(B, $B$9$J$o$A3FJQ?t$N;X?t$NOB$rJV$9(B. 
@item
$BJ,;6I=8=B?9`<0$,@8@.$5$l$k$H(B, @code{sugar} $B$H8F$P$l$k$"$k@0?t$,IUM?(B
$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. 
@item
@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
$B7hDj$9$k$?$a$N=EMW$J;X?K$H$J$k(B.
\E
\BEG
@item
Function @code{dp_td()} returns the total degree of the head term,
i.e., the sum of all exponent of variables in that term.
@item
Upon creation of a distributed polynomial, an integer called @code{sugar}
is associated.  This value is
the total degree of the virtually homogenized one of the original
polynomial.
@item
The quantity @code{sugar} is an important guide to determine the
selection strategy of critical pairs in Groebner basis computation.
\E
@end itemize

@example
[74] dp_ord(0)$
[75] X=<<1,2>>+<<0,1>>$
[76] Y=<<1,2>>+<<1,0>>$
[77] Z=X-Y;
(-1)*<<1,0>>+(1)*<<0,1>>
[78] dp_sugar(T);
3
@end example

\JP @node dp_lcm,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_lcm,,, Functions for Groebner basis computation
@subsection @code{dp_lcm}
@findex dp_lcm

@table @t
@item dp_lcm(@var{dpoly1},@var{dpoly2})
\JP :: $B:G>.8xG\9`$rJV$9(B. 
\EG :: Returns the least common multiple of the head terms of the given two polynomials.
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpoly1  dpoly2
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
$B$=$l$>$l$N0z?t$NF,9`$N:G>.8xG\9`$rJV$9(B. $B78?t$O(B 1 $B$G$"$k(B. 
\E
\BEG
@item
Returns the least common multiple of the head terms of the given
two polynomials, where coefficient is always set to 1.
\E
@end itemize

@example
[100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
(1)*<<5,4,3,4,5>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
@end table

\JP @node dp_redble,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_redble,,, Functions for Groebner basis computation
@subsection @code{dp_redble}
@findex dp_redble

@table @t
@item dp_redble(@var{dpoly1},@var{dpoly2})
\JP :: $BF,9`$I$&$7$,@0=|2DG=$+$I$&$+D4$Y$k(B. 
\EG :: Checks whether one head term is divisible by the other head term.
@end table

@table @var
@item return
\JP $B@0?t(B
\EG integer
@item dpoly1  dpoly2
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
@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
0 $B$rJV$9(B. 
@item
$BB?9`<0$N4JLs$r9T$&:](B, $B$I$N9`$r4JLs$G$-$k$+$rC5$9$N$KMQ$$$k(B. 
\E
\BEG
@item
Returns 1 if the head term of @var{dpoly2} divides the head term of
@var{dpoly1}; otherwise 0.
@item
Used for finding candidate terms at reduction of polynomials.
\E
@end itemize

@example
[148] C;
(1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
[149] T;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
[150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
0
0
0
1
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_red dp_red_mod}.
@end table

\JP @node dp_subd,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_subd,,, Functions for Groebner basis computation
@subsection @code{dp_subd}
@findex dp_subd

@table @t
@item dp_subd(@var{dpoly1},@var{dpoly2})
\JP :: $BF,9`$N>&C19`<0$rJV$9(B. 
\EG :: Returns the quotient monomial of the head terms.
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpoly1  dpoly2
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
@code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})} $B$r5a$a$k(B. $B7k2L$N78?t$O(B 1 
$B$G$"$k(B. 
@item
$B3d$j@Z$l$k$3$H$,$"$i$+$8$a$o$+$C$F$$$kI,MW$,$"$k(B.
\E
\BEG
@item
Gets @code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})}.
The coefficient of the result is always set to 1.
@item
Divisibility assumed.
\E
@end itemize

@example
[162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
(1)*<<0,1,1,1,1>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_red dp_red_mod}.
@end table

\JP @node dp_vtoe dp_etov,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_vtoe dp_etov,,, Functions for Groebner basis computation
@subsection @code{dp_vtoe}, @code{dp_etov}
@findex dp_vtoe
@findex dp_etov

@table @t
@item dp_vtoe(@var{vect})
\JP :: $B;X?t%Y%/%H%k$r9`$KJQ49(B
\EG :: Converts an exponent vector into a term.
@item dp_etov(@var{dpoly})
\JP :: $BF,9`$r;X?t%Y%/%H%k$KJQ49(B
\EG :: Convert the head term of a distributed polynomial into an exponent vector.
@end table

@table @var
@item return
\JP @code{dp_vtoe} : $BJ,;6I=8=B?9`<0(B, @code{dp_etov} : $B%Y%/%H%k(B
\EG @code{dp_vtoe} : distributed polynomial, @code{dp_etov} : vector
@item vect
\JP $B%Y%/%H%k(B
\EG vector
@item dpoly
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
@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. 
@item
@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
$B%Y%/%H%k$KJQ49$9$k(B. 
\E
\BEG
@item
@code{dp_vtoe()} generates a term whose exponent vector is @var{vect}.
@item
@code{dp_etov()} generates a vector which is the exponent vector of the
head term of @code{dpoly}.
\E
@end itemize

@example
[211] X=<<1,2,3>>;
(1)*<<1,2,3>>
[212] V=dp_etov(X);
[ 1 2 3 ]
[213] V[2]++$
[214] Y=dp_vtoe(V);
(1)*<<1,2,4>>
@end example

\JP @node dp_mbase,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_mbase,,, Functions for Groebner basis computation
@subsection @code{dp_mbase}
@findex dp_mbase

@table @t
@item dp_mbase(@var{dplist})
\JP :: monomial $B4pDl$N7W;;(B
\EG :: Computes the monomial basis
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0$N%j%9%H(B
\EG list of distributed polynomial
@item dplist
\JP $BJ,;6I=8=B?9`<0$N%j%9%H(B
\EG list of distributed polynomial
@end table

@itemize @bullet
\BJP
@item
$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
$B$G$"$k(B @var{dplist} $B$K$D$$$F(B, 
@var{dplist} $B$,(B K[X] $BCf$G@8@.$9$k%$%G%"%k(B I $B$,(B 0 $B<!85$N;~(B, 
K $B>eM-8B<!85@~7A6u4V$G$"$k(B K[X]/I $B$N(B monomial $B$K$h$k4pDl$r5a$a$k(B. 
@item
$BF@$i$l$?4pDl$N8D?t$,(B, K[X]/I $B$N(B K-$B@~7A6u4V$H$7$F$N<!85$KEy$7$$(B. 
\E
\BEG
@item
Assuming that @var{dplist} is a list of distributed polynomials which
is a Groebner basis with respect to the current ordering type and
that the ideal @var{I} generated by @var{dplist} in K[X] is zero-dimensional,
this function computes the monomial basis of a finite dimenstional K-vector
space K[X]/I.
@item
The number of elements in the monomial basis is equal to the
K-dimenstion of K[X]/I.
\E
@end itemize

@example
[215] K=katsura(5)$
[216] V=[u5,u4,u3,u2,u1,u0]$
[217] G0=gr(K,V,0)$
[218] H=map(dp_ptod,G0,V)$
[219] map(dp_ptod,dp_mbase(H),V)$
[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,
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,
u1*u2,u1^2,u4*u0,u3*u0,u2*u0,u1*u0,u0^2,u4,u3,u2,u1,u0,1]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{gr hgr gr_mod}.
@end table

\JP @node dp_mag,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_mag,,, Functions for Groebner basis computation
@subsection @code{dp_mag}
@findex dp_mag

@table @t
@item dp_mag(@var{p})
\JP :: $B78?t$N%S%C%HD9$NOB$rJV$9(B
\EG :: Computes the sum of bit lengths of coefficients of a distributed polynomial.
@end table

@table @var
@item return
\JP $B?t(B
\EG integer
@item p
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@end table

@itemize @bullet
\BJP
@item
$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)
$B$N%S%C%HD9$NAmOB$rJV$9(B. 
@item
$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
$B78?tKDD%$,LdBj$H$J$j(B, $BESCf@8@.$5$l$kB?9`<0$,78?tKDD%$r5/$3$7$F$$$k$+$I$&$+(B
$B$NH=Dj$KLrN)$D(B. 
@item
@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
$BESCf@8@.$5$l$kB?9`<0$K$?$$$9$k(B @code{dp_mag()} $B$NCM$r8+$k$3$H$,$G$-$k(B. 
\E
\BEG
@item
This function computes the sum of bit lengths of coefficients of a
distributed polynomial @var{p}. If a coefficient is non integral,
the sum of bit lengths of the numerator and the denominator is taken.
@item
This is a measure of the size of a polynomial. Especially for
zero-dimensional system coefficient swells are often serious and
the returned value is useful to detect such swells.
@item
If @code{ShowMag} and @code{Print} for @code{dp_gr_flags()} are on,
values of @code{dp_mag()} for intermediate basis elements are shown.
\E
@end itemize

@example
[221] X=dp_ptod((x+2*y)^10,[x,y])$
[222] dp_mag(X);
115
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_gr_flags dp_gr_print}.
@end table

\JP @node dp_red dp_red_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_red dp_red_mod,,, Functions for Groebner basis computation
@subsection @code{dp_red}, @code{dp_red_mod}
@findex dp_red
@findex dp_red_mod

@table @t
@item dp_red(@var{dpoly1},@var{dpoly2},@var{dpoly3})
@item dp_red_mod(@var{dpoly1},@var{dpoly2},@var{dpoly3},@var{mod})
\JP :: $B0l2s$N4JLsA`:n(B
\EG :: Single reduction operation
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item dpoly1  dpoly2  dpoly3
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item vlist
\JP $B%j%9%H(B
\EG list
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
@var{dpoly1} + @var{dpoly2} $B$J$kJ,;6I=8=B?9`<0$r(B @var{dpoly3} $B$G(B
1 $B2s4JLs$9$k(B.
@item
@code{dp_red_mod()} $B$NF~NO$O(B, $BA4$FM-8BBN78?t$KJQ49$5$l$F$$$kI,MW$,$"$k(B. 
@item
$B4JLs$5$l$k9`$O(B @var{dpoly2} $B$NF,9`$G$"$k(B. $B=>$C$F(B, @var{dpoly2} $B$N(B
$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
$B$J$i$J$$(B. 
@item
$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}, 
$B9`(B @var{t} $B$K$h$j(B @var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3} $B$H$7$F7W;;$5$l$k(B. 
@item
$B7k2L$O(B, @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]} $B$J$k%j%9%H$G$"$k(B.
\E
\BEG
@item
Reduces a distributed polynomial, @var{dpoly1} + @var{dpoly2},
by @var{dpoly3} for single time.
@item
An input for @code{dp_red_mod()} must be converted into a distributed
polynomial with coefficients in a finite field.
@item
This implies that
the divisibility of the head term of @var{dpoly2} by the head term of
@var{dpoly3} is assumed.
@item
When integral coefficients, computation is so carefully performed that
no rational operations appear in the reduction procedure.
It is computed for integers @var{a} and @var{b}, and a term @var{t} as:
@var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3}.
@item
The result is a list @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]}.
\E
@end itemize

@example
[157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
[158] R=(6)*<<1,1,1,0,0>>;                                    
(6)*<<1,1,1,0,0>>
[159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>; 
(12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
[160] dp_red(D,R,C);                                         
[(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,
(-1)*<<0,1,1,1,0>>+(-1)*<<1,1,0,0,1>>]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_mod dp_rat}.
@end table

\JP @node dp_sp dp_sp_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node dp_sp dp_sp_mod,,, Functions for Groebner basis computation
@subsection @code{dp_sp}, @code{dp_sp_mod}
@findex dp_sp
@findex dp_sp_mod

@table @t
@item dp_sp(@var{dpoly1},@var{dpoly2})
@item dp_sp_mod(@var{dpoly1},@var{dpoly2},@var{mod})
\JP :: S-$BB?9`<0$N7W;;(B
\EG :: Computation of an S-polynomial
@end table

@table @var
@item return
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item dpoly1  dpoly2
\JP $BJ,;6I=8=B?9`<0(B
\EG distributed polynomial
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
@var{dpoly1}, @var{dpoly2} $B$N(B S-$BB?9`<0$r7W;;$9$k(B. 
@item
@code{dp_sp_mod()} $B$NF~NO$O(B, $BA4$FM-8BBN78?t$KJQ49$5$l$F$$$kI,MW$,$"$k(B. 
@item
$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
$BG\$5$l$F$$$k2DG=@-$,$"$k(B. 
\E
\BEG
@item
This function computes the S-polynomial of @var{dpoly1} and @var{dpoly2}.
@item
Inputs of @code{dp_sp_mod()} must be polynomials with coefficients in a
finite field.
@item
The result may be multiplied by a constant in the ground field in order to
make the result integral.
\E
@end itemize

@example
[227] X=dp_ptod(x^2*y+x*y,[x,y]);
(1)*<<2,1>>+(1)*<<1,1>>
[228] Y=dp_ptod(x*y^2+x*y,[x,y]);
(1)*<<1,2>>+(1)*<<1,1>>
[229] dp_sp(X,Y);
(-1)*<<2,1>>+(1)*<<1,2>>
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_mod dp_rat}.
@end table
\JP @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, Functions for Groebner basis computation
@subsection @code{p_nf}, @code{p_nf_mod}, @code{p_true_nf}, @code{p_true_nf_mod}
@findex p_nf
@findex p_nf_mod
@findex p_true_nf
@findex p_true_nf_mod

@table @t
@item p_nf(@var{poly},@var{plist},@var{vlist},@var{order})
@itemx p_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
\JP :: $BI=8=B?9`<0$N@55,7A$r5a$a$k(B. ($B7k2L$ODj?tG\$5$l$F$$$k2DG=@-$"$j(B)
\BEG
:: Computes the normal form of the given polynomial. 
(The result may be multiplied by a constant.)
\E
@item p_true_nf(@var{poly},@var{plist},@var{vlist},@var{order})
@itemx p_true_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
\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)
\BEG
:: Computes the normal form of the given polynomial. (The result is returned
as a form of @code{[numerator, denominator]})
\E
@end table

@table @var
@item return
\JP @code{p_nf} : $BB?9`<0(B, @code{p_true_nf} : $B%j%9%H(B
\EG @code{p_nf} : polynomial, @code{p_true_nf} : list
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item plist vlist
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
@samp{gr} $B$GDj5A$5$l$F$$$k(B. 
@item
$BB?9`<0$N(B, $BB?9`<0%j%9%H$K$h$k@55,7A$r5a$a$k(B. 
@item
@code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()}, @code{dp_true_nf_mod}
$B$KBP$9$k%$%s%?%U%'!<%9$G$"$k(B. 
@item
@var{poly} $B$*$h$S(B @var{plist} $B$O(B, $BJQ?t=g=x(B @var{vlist} $B$*$h$S(B
$BJQ?t=g=x7?(B @var{otype} $B$K=>$C$FJ,;6I=8=B?9`<0$KJQ49$5$l(B, 
@code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
@code{dp_true_nf_mod()} $B$KEO$5$l$k(B. 
@item
@code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
@code{dp_true_nf_mod()} $B$O(B @var{fullreduce} $B$,(B 1 $B$G8F$S=P$5$l$k(B. 
@item
$B7k2L$OB?9`<0$KJQ49$5$l$F=PNO$5$l$k(B. 
@item
@code{p_true_nf()}, @code{p_true_nf_mod()} $B$N=PNO$K4X$7$F$O(B,
@code{dp_true_nf()}, @code{dp_true_nf_mod()} $B$N9`$r;2>H(B. 
\E
\BEG
@item
Defined in the package @samp{gr}.
@item
Obtains the normal form of a polynomial by a polynomial list.
@item
These are interfaces to @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
 @code{dp_true_nf_mod}
@item
The polynomial @var{poly} and the polynomials in @var{plist} is
converted, according to the variable ordering @var{vlist} and
type of term ordering @var{otype}, into their distributed polynomial
counterparts and passed to @code{dp_nf()}.
@item
@code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()} and
@code{dp_true_nf_mod()}
is called with value 1 for @var{fullreduce}.
@item
The result is converted back into an ordinary polynomial.
@item
As for @code{p_true_nf()}, @code{p_true_nf_mod()}
refer to @code{dp_true_nf()} and @code{dp_true_nf_mod()}.
\E
@end itemize

@example
[79] K = katsura(5)$
[80] V = [u5,u4,u3,u2,u1,u0]$
[81] G = hgr(K,V,2)$
[82] p_nf(K[1],G,V,2);
0
[83] L = p_true_nf(K[1]+1,G,V,2);
[-1503...,-1503...]
[84] L[0]/L[1];
1
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_ptod},
@fref{dp_dtop},
@fref{dp_ord},
@fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod}.
@end table

\JP @node p_terms,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node p_terms,,, Functions for Groebner basis computation
@subsection @code{p_terms}
@findex p_terms

@table @t
@item p_terms(@var{poly},@var{vlist},@var{order})
\JP :: $BB?9`<0$K$"$i$o$l$kC19`$r%j%9%H$K$9$k(B. 
\EG :: Monomials appearing in the given polynomial is collected into a list.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item vlist
\JP $B%j%9%H(B
\EG list
@item order
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@end table

@itemize @bullet
\BJP
@item
@samp{gr} $B$GDj5A$5$l$F$$$k(B. 
@item
$BB?9`<0$rC19`$KE83+$7$?;~$K8=$l$k9`$r%j%9%H$K$7$FJV$9(B.
@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
$B$,%j%9%H$N@hF,$KMh$k$h$&$K%=!<%H$5$l$k(B. 
@item
$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
$B$$$k$N$+$r8+$k$?$a$J$I$KMQ$$$k(B. 
\E
\BEG
@item
Defined in the package @samp{gr}.
@item
This returns a list which contains all non-zero monomials in the given
polynomial.  The monomials are ordered according to the current
type of term ordering and @var{vlist}.
@item
Since polynomials in a Groebner base often have very large coefficients,
examining a polynomial as it is may sometimes be difficult to perform.
For such a case, this function enables to examine which term is really
exists.
\E
@end itemize

@example
[233] G=gr(katsura(5),[u5,u4,u3,u2,u1,u0],2)$
[234] p_terms(G[0],[u5,u4,u3,u2,u1,u0],2);
[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,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,u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]
@end example

\JP @node gb_comp,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node gb_comp,,, Functions for Groebner basis computation
@subsection @code{gb_comp}
@findex gb_comp

@table @t
@item gb_comp(@var{plist1}, @var{plist2})
\JP :: $BB?9`<0%j%9%H$,(B, $BId9f$r=|$$$F=89g$H$7$FEy$7$$$+$I$&$+D4$Y$k(B. 
\EG :: Checks whether two polynomial lists are equal or not as a set
@end table

@table @var
\JP @item return 0 $B$^$?$O(B 1
\EG @item return 0 or 1
@item plist1  plist2
@end table

@itemize @bullet
\BJP
@item
@var{plist1}, @var{plist2} $B$K$D$$$F(B, $BId9f$r=|$$$F=89g$H$7$FEy$7$$$+$I$&$+(B
$BD4$Y$k(B. 
@item
$B0[$J$kJ}K!$G5a$a$?%0%l%V%J4pDl$O(B, $B4pDl$N=g=x(B, $BId9f$,0[$J$k>l9g$,$"$j(B, 
$B$=$l$i$,Ey$7$$$+$I$&$+$rD4$Y$k$?$a$KMQ$$$k(B. 
\E
\BEG
@item
This function checks whether @var{plist1} and @var{plist2} are equal or
not as a set .
@item
For the same input and the same term ordering different
functions for Groebner basis computations may produce different outputs
as lists. This function compares such lists whether they are equal
as a generating set of an ideal.
\E
@end itemize

@example
[243] C=cyclic(6)$
[244] V=[c0,c1,c2,c3,c4,c5]$
[245] G0=gr(C,V,0)$
[246] G=tolex(G0,V,0,V)$
[247] GG=lex_tl(C,V,0,V,0)$
[248] gb_comp(G,GG);
1
@end example

\JP @node katsura hkatsura cyclic hcyclic,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node katsura hkatsura cyclic hcyclic,,, Functions for Groebner basis computation
@subsection @code{katsura}, @code{hkatsura}, @code{cyclic}, @code{hcyclic}
@findex katsura
@findex hkatsura
@findex cyclic
@findex hcyclic

@table @t
@item katsura(@var{n})
@item hkatsura(@var{n})
@item cyclic(@var{n})
@item hcyclic(@var{n})
\JP :: $BB?9`<0%j%9%H$N@8@.(B
\EG :: Generates a polynomial list of standard benchmark.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item n
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
@code{katsura()} $B$O(B @samp{katsura}, @code{cyclic()} $B$O(B @samp{cyclic}
$B$GDj5A$5$l$F$$$k(B. 
@item
$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}, 
@code{cyclic} $B$*$h$S$=$N@F<!2=$r@8@.$9$k(B. 
@item
@code{cyclic} $B$O(B @code{Arnborg}, @code{Lazard}, @code{Davenport} $B$J$I$N(B
$BL>$G8F$P$l$k$3$H$b$"$k(B. 
\E
\BEG
@item
Function @code{katsura()} is defined in @samp{katsura}, and
function @code{cyclic()} in  @samp{cyclic}.
@item
These functions generate a series of polynomial sets, respectively,
which are often used for testing and bench marking:
@code{katsura}, @code{cyclic} and their homogenized versions.
@item
Polynomial set @code{cyclic} is sometimes called by other name:
@code{Arnborg}, @code{Lazard}, and @code{Davenport}.
\E
@end itemize

@example
[74] load("katsura")$
[79] load("cyclic")$ 
[89] katsura(5);
[u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
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,2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[90] hkatsura(5);
[-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
-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,
-u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
-u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
-u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[91] cyclic(6);
[c5*c4*c3*c2*c1*c0-1,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
[92] hcyclic(6);
[-c^6+c5*c4*c3*c2*c1*c0,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{dp_dtop}.
@end table

\JP @node primadec primedec,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node primadec primedec,,, Functions for Groebner basis computation
@subsection @code{primadec}, @code{primedec}
@findex primadec
@findex primedec

@table @t
@item primadec(@var{plist},@var{vlist})
@item primedec(@var{plist},@var{vlist})
\JP :: $B%$%G%"%k$NJ,2r(B
\EG :: Computes decompositions of ideals.
@end table

@table @var
@item return
@itemx plist
\JP $BB?9`<0%j%9%H(B
\EG list of polynomials
@item vlist
\JP $BJQ?t%j%9%H(B
\EG list of variables
@end table

@itemize @bullet
\BJP
@item
@code{primadec()}, @code{primedec} $B$O(B @samp{primdec} $B$GDj5A$5$l$F$$$k(B.
@item
@code{primadec()}, @code{primedec()} $B$O$=$l$>$lM-M}?tBN>e$G$N%$%G%"%k$N(B
$B=`AGJ,2r(B, $B:,4p$NAG%$%G%"%kJ,2r$r9T$&(B.
@item
$B0z?t$OB?9`<0%j%9%H$*$h$SJQ?t%j%9%H$G$"$k(B. $BB?9`<0$OM-M}?t78?t$N$_$,5v$5$l$k(B. 
@item
@code{primadec} $B$O(B @code{[$B=`AG@.J,(B, $BIUB0AG%$%G%"%k(B]} $B$N%j%9%H$rJV$9(B. 
@item
@code{primadec} $B$O(B $BAG0x;R$N%j%9%H$rJV$9(B. 
@item
$B7k2L$K$*$$$F(B, $BB?9`<0%j%9%H$H$7$FI=<($5$l$F$$$k3F%$%G%"%k$OA4$F(B
$B%0%l%V%J4pDl$G$"$k(B. $BBP1~$9$k9`=g=x$O(B, $B$=$l$>$l(B 
$BJQ?t(B @code{PRIMAORD}, @code{PRIMEORD} $B$K3JG<$5$l$F$$$k(B. 
@item
@code{primadec} $B$O(B @code{[Shimoyama,Yokoyama]} $B$N=`AGJ,2r%"%k%4%j%:%`(B
$B$r<BAu$7$F$$$k(B. 
@item
$B$b$7AG0x;R$N$_$r5a$a$?$$$J$i(B, @code{primedec} $B$r;H$&J}$,$h$$(B. 
$B$3$l$O(B, $BF~NO%$%G%"%k$,:,4p%$%G%"%k$G$J$$>l9g$K(B, @code{primadec}
$B$N7W;;$KM>J,$J%3%9%H$,I,MW$H$J$k>l9g$,$"$k$+$i$G$"$k(B. 
\E
\BEG
@item
Function @code{primadec()} and @code{primedec} are defined in @samp{primdec}.
@item
@code{primadec()}, @code{primedec()} are the function for primary
ideal decomposition and prime decomposition of the radical over the
rationals respectively.
@item
The arguments are a list of polynomials and a list of variables.
These functions accept ideals with rational function coefficients only.
@item
@code{primadec} returns the list of pair lists consisting a primary component
and its associated prime.
@item
@code{primedec} returns the list of prime components.
@item
Each component is a Groebner basis and the corresponding term order
is indicated by the global variables @code{PRIMAORD}, @code{PRIMEORD}
respectively.
@item
@code{primadec} implements the primary decompostion algorithm 
in @code{[Shimoyama,Yokoyama]}.
@item
If one only wants to know the prime components of an ideal, then
use @code{primedec} because @code{primadec} may need additional costs
if an input ideal is not radical.
\E
@end itemize

@example
[84] load("primdec")$
[102] primedec([p*q*x-q^2*y^2+q^2*y,-p^2*x^2+p^2*x+p*q*y,
(q^3*y^4-2*q^3*y^3+q^3*y^2)*x-q^3*y^4+q^3*y^3,
-q^3*y^4+2*q^3*y^3+(-q^3+p*q^2)*y^2],[p,q,x,y]);
[[y,x],[y,p],[x,q],[q,p],[x-1,q],[y-1,p],[(y-1)*x-y,q*y^2-2*q*y-p+q]]
[103] primadec([x,z*y,w*y^2,w^2*y-z^3,y^3],[x,y,z,w]);
[[[x,z*y,y^2,w^2*y-z^3],[z,y,x]],[[w,x,z*y,z^3,y^3],[w,z,y,x]]]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{fctr sqfr},
\JP @fref{$B9`=g=x$N@_Dj(B}.
\EG @fref{Setting term orderings}.
@end table

\JP @node primedec_mod,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node primedec_mod,,, Functions for Groebner basis computation
@subsection @code{primedec_mod}
@findex primedec_mod

@table @t
@item primedec_mod(@var{plist},@var{vlist},@var{ord},@var{mod},@var{strategy})
\JP :: $B%$%G%"%k$NJ,2r(B
\EG :: Computes decompositions of ideals over small finite fields.
@end table

@table @var
@item return
@itemx plist
\JP $BB?9`<0%j%9%H(B
\EG list of polynomials
@item vlist
\JP $BJQ?t%j%9%H(B
\EG list of variables
@item ord
\JP $B?t(B, $B%j%9%H$^$?$O9TNs(B
\EG number, list or matrix
@item mod
\JP $B@5@0?t(B
\EG positive integer
@item strategy
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
@code{primedec_mod()} $B$O(B @samp{primdec_mod}
$B$GDj5A$5$l$F$$$k(B. @code{[Yokoyama]} $B$NAG%$%G%"%kJ,2r%"%k%4%j%:%`(B
$B$r<BAu$7$F$$$k(B. 
@item
@code{primedec_mod()} $B$OM-8BBN>e$G$N%$%G%"%k$N(B
$B:,4p$NAG%$%G%"%kJ,2r$r9T$$(B, $BAG%$%G%"%k$N%j%9%H$rJV$9(B. 
@item
@code{primedec_mod()} $B$O(B, GF(@var{mod}) $B>e$G$NJ,2r$rM?$($k(B. 
$B7k2L$N3F@.J,$N@8@.85$O(B, $B@0?t78?tB?9`<0$G$"$k(B. 
@item
$B7k2L$K$*$$$F(B, $BB?9`<0%j%9%H$H$7$FI=<($5$l$F$$$k3F%$%G%"%k$OA4$F(B
[@var{vlist},@var{ord}] $B$G;XDj$5$l$k9`=g=x$K4X$9$k%0%l%V%J4pDl$G$"$k(B.
@item
@var{strategy} $B$,(B 0 $B$G$J$$$H$-(B, incremental $B$K(B component $B$N6&DL(B
$BItJ,$r7W;;$9$k$3$H$K$h$k(B early termination $B$r9T$&(B. $B0lHL$K(B, 
$B%$%G%"%k$N<!85$,9b$$>l9g$KM-8z$@$,(B, 0 $B<!85$N>l9g$J$I(B, $B<!85$,>.$5$$(B
$B>l9g$K$O(B overhead $B$,Bg$-$$>l9g$,$"$k(B. 
@item
$B7W;;ESCf$GFbIt>pJs$r8+$?$$>l9g$K$O!"(B
$BA0$b$C$F(B @code{dp_gr_print(2)} $B$r<B9T$7$F$*$1$P$h$$(B.
\E
\BEG
@item
Function @code{primedec_mod()}
is defined in @samp{primdec_mod} and implements the prime decomposition
algorithm in @code{[Yokoyama]}.
@item
@code{primedec_mod()}
is the function for prime ideal decomposition 
of the radical of a polynomial ideal over small finite field,
and they return a list of prime ideals, which are associated primes
of the input ideal.
@item
@code{primedec_mod()} gives the decomposition over GF(@var{mod}).
The generators of each resulting component consists of integral polynomials.
@item
Each resulting component is a Groebner basis with respect to
a term order specified by [@var{vlist},@var{ord}].
@item
If @var{strategy} is non zero, then the early termination strategy
is tried by computing the intersection of obtained components
incrementally. In general, this strategy is useful when the krull
dimension of the ideal is high, but it may add some overhead
if the dimension is small.
@item
If you want to see internal information during the computation,
execute @code{dp_gr_print(2)} in advance.
\E
@end itemize

@example
[0] load("primdec_mod")$
[246] PP444=[x^8+x^2+t,y^8+y^2+t,z^8+z^2+t]$
[247] primedec_mod(PP444,[x,y,z,t],0,2,1);
[[y+z,x+z,z^8+z^2+t],[x+y,y^2+y+z^2+z+1,z^8+z^2+t],
[y+z+1,x+z+1,z^8+z^2+t],[x+z,y^2+y+z^2+z+1,z^8+z^2+t],
[y+z,x^2+x+z^2+z+1,z^8+z^2+t],[y+z+1,x^2+x+z^2+z+1,z^8+z^2+t],
[x+z+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z+1,x+z,z^8+z^2+t],
[x+y+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z,x+z+1,z^8+z^2+t]]
[248] 
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{modfctr},
@fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
\JP @fref{$B9`=g=x$N@_Dj(B}.
\EG @fref{Setting term orderings},
@fref{dp_gr_flags dp_gr_print}.
@end table

\JP @node bfunction bfct generic_bfct,,, $B%0%l%V%J4pDl$K4X$9$kH!?t(B
\EG @node bfunction bfct generic_bfct,,, Functions for Groebner basis computation
@subsection @code{bfunction}, @code{bfct}, @code{generic_bfct}
@findex bfunction
@findex bfct
@findex generic_bfct

@table @t
@item bfunction(@var{f})
@item bfct(@var{f})
@item generic_bfct(@var{plist},@var{vlist},@var{dvlist},@var{weight})
\JP :: b $B4X?t$N7W;;(B
\EG :: Computes the global b function of a polynomial or an ideal
@end table
@table @var
@item return
@itemx f
\JP $BB?9`<0(B
\EG polynomial
@item plist
\JP $BB?9`<0%j%9%H(B
\EG list of polynomials
@item vlist dvlist
\JP $BJQ?t%j%9%H(B
\EG list of variables
@end table

@itemize @bullet
\BJP
@item @samp{bfct} $B$GDj5A$5$l$F$$$k(B. 
@item @code{bfunction(@var{f})}, @code{bfct(@var{f})} $B$OB?9`<0(B @var{f} $B$N(B global b $B4X?t(B @code{b(s)} $B$r(B
$B7W;;$9$k(B. @code{b(s)} $B$O(B, Weyl $BBe?t(B @code{D} $B>e$N0lJQ?tB?9`<04D(B @code{D[s]}
$B$N85(B @code{P(x,s)} $B$,B8:_$7$F(B, @code{P(x,s)f^(s+1)=b(s)f^s} $B$rK~$?$9$h$&$J(B
$BB?9`<0(B @code{b(s)} $B$NCf$G(B, $B<!?t$,:G$bDc$$$b$N$G$"$k(B. 
@item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
$B$O(B, @var{plist} $B$G@8@.$5$l$k(B @code{D} $B$N:8%$%G%"%k(B @code{I} $B$N(B, 
$B%&%'%$%H(B @var{weight} $B$K4X$9$k(B global b $B4X?t$r7W;;$9$k(B. 
@var{vlist} $B$O(B @code{x}-$BJQ?t(B, @var{vlist} $B$OBP1~$9$k(B @code{D}-$BJQ?t(B
$B$r=g$KJB$Y$k(B. 
@item @code{bfunction} $B$H(B @code{bfct} $B$G$OMQ$$$F$$$k%"%k%4%j%:%`$,(B
$B0[$J$k(B. $B$I$A$i$,9bB.2=$OF~NO$K$h$k(B.
@item $B>\:Y$K$D$$$F$O(B, [Saito,Sturmfels,Takayama] $B$r8+$h(B. 
\E
\BEG
@item These functions are defined in @samp{bfct}.
@item @code{bfunction(@var{f})} and @code{bfct(@var{f})} compute the global b-function @code{b(s)} of
a polynomial @var{f}.
@code{b(s)} is a polynomial of the minimal degree 
such that there exists @code{P(x,s)} in D[s], which is a polynomial
ring over Weyl algebra @code{D}, and @code{P(x,s)f^(s+1)=b(s)f^s} holds.
@item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
computes the global b-function of a left ideal @code{I} in @code{D}
generated by @var{plist}, with respect to @var{weight}.
@var{vlist} is the list of @code{x}-variables, 
@var{vlist} is the list of corresponding @code{D}-variables.
@item @code{bfunction(@var{f})} and @code{bfct(@var{f})} implement
different algorithms and the efficiency depends on inputs.
@item See [Saito,Sturmfels,Takayama] for the details.
\E
@end itemize

@example
[0] load("bfct")$
[216] bfunction(x^3+y^3+z^3+x^2*y^2*z^2+x*y*z);
-9*s^5-63*s^4-173*s^3-233*s^2-154*s-40
[217] fctr(@@);
[[-1,1],[s+2,1],[3*s+4,1],[3*s+5,1],[s+1,2]]
[218] F = [4*x^3*dt+y*z*dt+dx,x*z*dt+4*y^3*dt+dy,
x*y*dt+5*z^4*dt+dz,-x^4-z*y*x-y^4-z^5+t]$
[219] generic_bfct(F,[t,z,y,x],[dt,dz,dy,dx],[1,0,0,0]);
20000*s^10-70000*s^9+101750*s^8-79375*s^7+35768*s^6-9277*s^5
+1278*s^4-72*s^3
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
\JP @fref{Weyl $BBe?t(B}.
\EG @fref{Weyl algebra}.
@end table