[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
gr
, hgr
, gr_mod
, dgr
:: Groebner basis computation
list
list
number, list or matrix
prime less than 2^27
nd_gr
families should be used (nd_gr
, nd_gr_trace
, nd_f4
, nd_f4_trace
, nd_weyl_gr
, nd_weyl_gr_trace
).
gr()
and hgr()
compute a Groebner basis over the rationals
and gr_mod
computes over GF(p).
gr()
uses trace-lifting (an improvement by modular computation)
and sugar strategy.
hgr()
uses trace-lifting and a cured sugar strategy
by using homogenization.
dgr()
executes gr()
, dgr()
simultaneously on
two process in a child process list 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.
dgr()
indicates
that of the master process, and most of the time corresponds to the time
for communication.
dp_sort
and the Grobner basis computation is started.
Variables must be given in vlist even in this case
(these variables are dummy).
[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
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_ord
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
lex_hensel
, lex_tl
, tolex
, tolex_d
, tolex_tl
: Groebner basis computation with respect to a lex order by change of ordering
:: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis
list
list
number, list or matrix
flag
lex_hensel()
and lex_tl()
first compute a Groebner basis
with respect to the variable order vlist1 and the order type order.
Then the Groebner basis is converted into a lex order Groebner basis
with respect to the varable order vlist2.
tolex()
and tolex_tl()
convert a Groebner basis plist
with respect to the variable order vlist1 and the order type order
into a lex order Groebner basis
with respect to the varable order vlist2.
tolex_d()
does computations of basis elements in tolex()
in parallel on the processes in a child process list procs.
lex_hensel()
and tolex_hensel()
a lex order Groebner basis
is computed as follows.(Refer to [Noro,Yokoyama]
.)
lex_hensel()
. )
lex_tl()
and tolex_tl()
a lex order Groebner basis
is computed as follows.(Refer to [Noro,Yokoyama]
.)
lex_tl()
. )
lex_tl()
and tolex_tl()
.
homo
is not equal to 0, homogenization is used in Buchberger
algorithm.
tolex_d()
indicates
that of the master process, and it does not include the time in child
processes.
[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
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_ord
, Distributed computation
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
lex_hensel_gsl
, tolex_gsl
, tolex_gsl_d
::Computation of an GSL form ideal basis
:: Computation of an GSL form ideal basis stating from a Groebner basis
list
list
number, list or matrix
flag
lex_hensel_gsl()
and lex_hensel()
are variants of
tolex_gsl()
and tolex()
respectively. The results are
Groebner basis or a kind of ideal basis, called GSL form.
tolex_gsl_d()
does basis computations in parallel on child
processes specified in procs
.
[f0,x1-f1,...,xn-fn]
(f0
,...,fn
are
univariate polynomials of x0
; SL form), then this these
functions return a list such as
[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]
(GSL form). In this list
gi
is a univariate polynomial of x0
such that
di*f0'*fi-gi
divides f0
and the roots of the input ideal is
[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]
for x0
such that 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 tolex()
.
tolex_gsl_d()
indicates
that of the master process, and it does not include the time in child
processes.
[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-...]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
gr_minipoly
, minipoly
:: Computation of the minimal polynomial of a polynomial modulo an ideal
:: Computation of the minimal polynomial of a polynomial modulo an ideal
polynomial
list
number, list or matrix
polynomial
indeterminate
flag
gr_minipoly()
begins by computing a Groebner basis.
minipoly()
regards an input as a Groebner basis with respect to
the variable order vlist and the order type order.
gr_minipoly()
and minipoly()
computes the minimal polynomial
of a polynomial p and returns it as a polynomial of v.
minipoly()
and gr_minipoly()
can compute it more efficiently
than methods using Groebner basis computation.
gr_minipoly()
.
[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
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
tolexm
, minipolym
:: Groebner basis computation modulo mod by change of ordering.
:: Minimal polynomial computation modulo mod the same method as
tolexm()
: list, minipolym()
: polynomial
list
number, list or matrix
prime
minipolym()
executes the same computation as in minipoly
.
tolexm()
computes a lex order Groebner basis modulo mod
with respect to the variable order vlist2, by using FGLM algorithm.
[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+...
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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
:: Groebner basis computation (built-in functions)
list
list
number, list or matrix
flag
flag or prime
gr()
,hgr()
and gr_mod()
are all interfaces to these functions. Functions whose names
contain weyl are those for computation in Weyl algebra.
dp_gr_f_main()
and 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 setmod_ff()
.
dp_gr_mod_main()
, modular means a computation over
GF(modular).
For dp_gr_main()
, modular has the following mean.
lprime()
, starting from lprime(0)
, until
the computation succeeds.
gr(P,V,O)
, hgr(P,V,O)
and gr_mod(P,V,O,M)
execute
dp_gr_main(P,V,0,1,O)
, dp_gr_main(P,V,1,1,O)
and dp_gr_mod_main(P,V,0,M,O)
respectively.
dp_gr_flags()
, other then by homo and modular.
dp_ord
,
dp_gr_flags
, dp_gr_print
,
gr
, hgr
, gr_mod
, dgr
,
setmod_ff
,
Controlling Groebner basis computations
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_f4_main
, dp_f4_mod_main
, dp_weyl_f4_main
, dp_weyl_f4_mod_main
:: Groebner basis computation by F4 algorithm (built-in functions)
list
list
number, list or matrix
dp_f4_main()
uses Chinese Remainder theorem and not highly optimized.
dp_gr_main()
, dp_gr_mod_main()
,
dp_weyl_gr_main()
, dp_weyl_gr_mod_main()
,
except for lack of the argument for controlling homogenization.
dp_ord
,
dp_gr_flags
, dp_gr_print
,
gr
, hgr
, gr_mod
, dgr
,
Controlling Groebner basis computations
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
nd_gr
, nd_gr_trace
, nd_f4
, nd_f4_trace
, nd_weyl_gr
, nd_weyl_gr_trace
:: Groebner basis computation (built-in functions)
list
list
number, list or matrix
flag
flag or prime
nd_gr
executes Buchberger algorithm over the rationals
if p
is 0, and that over GF(p) if p
is a prime.
nd_gr_trace
executes the trace algorithm over the rationals.
If p
is 0 or 1, the trace algorithm is executed until it succeeds
by using automatically chosen primes.
If p
a positive prime,
the trace is comuted over GF(p).
If the trace algorithm fails 0 is returned.
If p
is negative,
the Groebner basis check and ideal-membership check are omitted.
In this case, an automatically chosen prime if p
is 1,
otherwise the specified prime is used to compute a Groebner basis
candidate.
Execution of nd_f4_trace
is done as follows:
For each total degree, an F4-reduction of S-polynomials over a finite field
is done, and S-polynomials which give non-zero basis elements are gathered.
Then F4-reduction over Q is done for the gathered S-polynomials.
The obtained polynomial set is a Groebner basis candidate and the same
check procedure as in the case of nd_gr_trace
is done.
nd_f4
executes F4 algorithm over Q if modular
is equal to 0,
or over a finite field GF(modular
)
if modular
is a prime number of machine size (<2^29).
If plist is a list of polynomials, then a Groebner basis of the ideal generated by plist
is computed. If plist is a list of lists of polynomials, then each list of polynomials are regarded
as an element of a free module over a polynomial ring and a Groebner basis of the sub-module generated by plist
in the free module. In the latter case a term order in the free module should be specified.
This is specified by [s,ord]. If s is 0 then it means TOP (Term Over Position).
If s is 1 then it means POT 1 (Position Over Term). ord is a term order in the base polynomial ring.
nd_weyl_gr
, nd_weyl_gr_trace
are for Weyl algebra computation.
dp_gr_main
, dp_gr_mod_main
, especially over finite fields.
homo
If set to 1, the computation is done via homogenization. (only for nd_gr
and nd_f4
)
dp
If set to 1, the functions return a list of distributed polynomials (a list of module polynomials when the input is a sub-module).
nora
If set to 1, the inter-reduction is not performed.
[38] load("cyclic")$ [49] C=cyclic(7)$ [50] V=vars(C)$ [51] cputime(1)$ [52] dp_gr_mod_main(C,V,0,31991,0)$ 26.06sec + gc : 0.313sec(26.4sec) [53] nd_gr(C,V,31991,0)$ ndv_alloc=1477188 5.737sec + gc : 0.1837sec(5.921sec) [54] dp_f4_mod_main(C,V,31991,0)$ 3.51sec + gc : 0.7109sec(4.221sec) [55] nd_f4(C,V,31991,0)$ 1.906sec + gc : 0.126sec(2.032sec)
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
nd_gr_postproc
, nd_weyl_gr_postproc
:: Check of Groebner basis candidate and inter-reduction
list or 0
list
prime or 0
number, list or matrix
0 or 1
nd_weyl_gr_postproc
is for Weyl algebra.
afo
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_gr_flags
, dp_gr_print
and showing informations.
value currently set
list
integer
dp_gr_flags()
sets and shows various parameters for Groebner basis
computation.
["Print",1,"NoSugar",1,...]
. Names of parameters must be character
strings.
dp_gr_print()
is used to set and show the value of a parameter
Print
and PrintShort
.
Print=0
, PrintShort=0
Print=1
, PrintShort=0
Print=0
, PrintShort=1
This functions is prepared to get quickly the value
when a user defined function calling dp_gr_main()
etc.
uses the value as a flag for showing intermediate informations.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_ord
:: Set and show the ordering type.
ordering type (number, list or matrix)
number, list or matrix
gr()
, which need a ordering type as an argument,
call 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.
[0,Ord]
then a TOP ordering based on the ordering type specified
by Ord
is set.
If the argument is [1,Ord]
then a POT ordering is set.
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_set_weight
, dp_set_top_weight
, dp_weyl_set_weight
:: Set and show the sugar weight.
:: Set and show the top weight.
:: Set and show the weyl weight.
a vector
a list or vector of integers
dp_set_weight
sets the sugar weight=weight. It returns the current sugar weight.
A sugar weight is a vector with positive integer components and it represents the weights of variables.
It is used for computing the weight of a monomial in a graded ordering.
It is recommended to append a component 1 at the end of the weight vector for a homogenizing variable.
dp_set_top_weight
sets the top weight=weight. It returns the current top weight.
It a top weight is set, the weights of monomials under the top weight are firstly compared.
If the the weights are equal then the current term ordering is applied as a tie breaker, but
the top weight is not used in the tie breaker.
dp_weyl_set_weight
sets the weyl weigh=weight. It returns the current weyl weight.
If a weyl weight w is set, in the comparsion by the term order type 11, a term order with
the top weight=(-w,w) and the tie breaker=graded reverse lex is applied.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_ptod
:: Converts an ordinary polynomial into a distributed polynomial.
distributed polynomial
polynomial
list
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_dptodpm
:: Converts a distributed polynomial into a module polynomial.
module polynomial
distributed polynomial
positive integer
dpoly e_pos
.
[50] dp_ord([0,0])$ [51] D=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_dptodpm(D,2); (1)*<<2,0,0:2>>+(2)*<<1,1,0:2>>+(1)*<<0,2,0:2>>+(2)*<<1,0,1:2>> +(2)*<<0,1,1:2>>+(1)*<<0,0,2:2>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_ltod
:: Converts a list of polynomials into a module polynomial.
module polynomial
list of polynomials
list of variables
[p1,...,pm]
is converted into p1 e1+...+pm em
.
[2126] dp_ord([0,0])$ [2127] dpm_ltod([x^2+y^2,x,y-z],[x,y,z]); (1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>> +(-1)*<<0,0,1:3>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_dtol
:: Converts a module polynomial into a list of polynomials.
list of polynomials
module polynomial
list of variables
p1 e1+...+pm em
is converted into [p1,...,pm]
.
poly
.
[2126] dp_ord([0,0])$ [2127] D=(1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>> +(-1)*<<0,0,1:3>>$ [2128] dpm_dtol(D,[x,y,z]); [x^2+y^2,x,y-z]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_dtop
:: Converts a distributed polynomial into an ordinary polynomial.
polynomial
distributed polynomial
list
[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
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_mod
, dp_rat
:: Converts a disributed polynomial into one with coefficients in a finite field.
:: Converts a distributed polynomial with coefficients in a finite field into one with coefficients in the rationals.
distributed polynomial
distributed polynomial
prime
list
dp_nf_mod()
and dp_true_nf_mod()
require
distributed polynomials with coefficients in a finite field as arguments.
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. dp_rat()
is used for such cases.
setmod()
.
[[var,value],...]
.
This is valid when the ground field of the input polynomial is a
rational function field. var’s are variables in the ground field and
the list means that value is substituted for var before
converting the coefficients into elements of a finite field.
dp_nf
, dp_nf_mod
, dp_true_nf
, dp_true_nf_mod
,
subst
, psubst
,
setmod
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_homo
, dp_dehomo
:: Homogenize a distributed polynomial
:: Dehomogenize a homogenious distributed polynomial
distributed polynomial
distributed polynomial
dp_homo()
makes a copy of dpoly, extends
the length of the exponent vector of each term t in the copy by 1,
and sets the value of the newly appended
component to d-deg(t)
, where d is the total
degree of dpoly.
dp_dehomo()
make a copy of dpoly and removes the last component
of each terms in the copy.
hgr()
etc.
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_ptozp
, dp_prim
:: Converts a distributed polynomial poly with rational coefficients into an integral distributed polynomial such that GCD of all its coefficients is 1.
:: Converts a distributed polynomial poly with rational function coefficients into an integral distributed polynomial such that polynomial GCD of all its coefficients is 1.
distributed polynomial
distributed polynomial
dp_ptozp()
executes the same operation as ptozp()
for
a distributed polynomial. If the coefficients include polynomials,
polynomial contents included in the coefficients are not removed.
dp_prim()
removes polynomial contents.
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_nf
, dp_nf_mod
, dp_true_nf
, dp_true_nf_mod
:: Computes the normal form of a distributed polynomial. (The result may be multiplied by a constant in the ground field.)
:: Computes the normal form of a distributed polynomial. (The true result
is returned in such a list as [numerator, denominator]
)
dp_nf()
: distributed polynomial, dp_true_nf()
: list
list
distributed polynomial
array of distributed polynomial
flag
prime
weyl
compute normal forms in Weyl algebra. The description below also applies to
the functions for Weyl algebra.
dp_nf_mod()
and dp_true_nf_mod()
require
distributed polynomials with coefficients in a finite field as arguments.
dp_nf()
may be multiplied by a constant in the
ground field in order to make the result integral. The same is true
for dp_nf_mod()
, but it returns the true normal form if
the ground field is a finite field.
dp_true_nf()
and dp_true_nf_mod()
return
such a list as [nm,dn]
.
Here nm is a distributed polynomial whose coefficients are integral
in the ground field, dn is an integral element in the ground
field and nm/dn is the true normal form.
p_nf
and p_true_nf
are sufficient.
[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
dp_dtop
,
dp_ord
,
dp_mod
, dp_rat
,
p_nf
, p_nf_mod
, p_true_nf
, p_true_nf_mod
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_nf
, dpm_nf_and_quotient
:: Computes the normal form of a module polynomial. (The result may be multiplied by a constant in the ground field.)
:: Computes the normal form of a module polynomial and the quotient.
dpm_nf()
: module polynomial, dpm_nf_and_quotient()
: list
list
module polynomial
array of module polynomial
dpm_nf()
may be multiplied by a constant in the
ground field in order to make the result integral.
dpm_nf_and_quotient()
returns
such a list as [nm,dn,quo]
.
Here nm is a module polynomial whose coefficients are integral
in the ground field, dn is an integral element in the ground
field and nm/dn is the true normal form.
quo is an array containing the quotients of the division satisfying
dndpoly=nm+quo[0]dpolyarray[0]+....
[2126] dp_ord([1,0])$ [2127] S=ltov([(1)*<<0,0,2,0:1>>+(1)*<<0,0,1,1:1>>+(1)*<<0,0,0,2:1>> +(-1)*<<3,0,0,0:2>>+(-1)*<<0,0,2,1:2>>+(-1)*<<0,0,1,2:2>> +(1)*<<3,0,1,0:3>>+(1)*<<3,0,0,1:3>>+(1)*<<0,0,2,2:3>>, (-1)*<<0,1,0,0:1>>+(-1)*<<0,0,1,0:1>>+(-1)*<<0,0,0,1:1>> +(-1)*<<3,0,0,0:3>>+(1)*<<0,1,1,1:3>>,(1)*<<0,1,0,0:2>> +(1)*<<0,0,1,0:2>>+(1)*<<0,0,0,1:2>>+(-1)*<<0,1,1,0:3>> +(-1)*<<0,1,0,1:3>>+(-1)*<<0,0,1,1:3>>])$ [2128] U=dpm_sp(S[0],S[1]); (1)*<<0,0,3,0:1>>+(-1)*<<0,1,1,1:1>>+(1)*<<0,0,2,1:1>> +(-1)*<<0,1,0,2:1>>+(1)*<<3,1,0,0:2>>+(1)*<<0,1,2,1:2>> +(1)*<<0,1,1,2:2>>+(-1)*<<3,1,1,0:3>>+(1)*<<3,0,2,0:3>> +(-1)*<<3,1,0,1:3>>+(-1)*<<0,1,3,1:3>>+(-1)*<<0,1,2,2:3>> [2129] dpm_nf(U,S,1); 0 [2130] L=dpm_nf_and_quotient(U,S)$ [2131] Q=L[2]$ [2132] D=L[1]$ [2133] D*U-(Q[1]*S[1]+Q[2]*S[2]); 0
@ref{dpm_sp},
dp_ord
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_hm
, dp_ht
, dp_hc
, dp_rest
:: Gets the head monomial.
:: Gets the head term.
:: Gets the head coefficient.
:: Gets the remainder of the polynomial where the head monomial is removed.
dp_hm()
, dp_ht()
, dp_rest()
: distributed polynomial
dp_hc()
: number or polynomial
distributed polynomial
p = dp_hm(p) + dp_rest(p)
dp_hm(p) = dp_hc(p) dp_ht(p)
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_hm
, dpm_ht
, dpm_hc
, dpm_hp
, dpm_rest
:: Gets the head monomial of a module polynomial.
:: Gets the head term of a module polynomial.
:: Gets the head coefficient of a module polynomial.
:: Gets the head position of a module polynomial.
:: Gets the remainder of a module polynomial where the head monomial is removed.
dpm_hm()
, dpm_ht()
, dpm_rest()
: module polynomial
dpm_hc()
: monomial
distributed polynomial
dpm_hc()
returns the monomial that is the coefficient of dpm_hm()
with respect to the
standard base.
For getting its scalar coefficient apply dp_hc()
.
dpm_hp()
returns the index of the standard base conteind in the head module monomial.
[2126] dp_ord([1,0]); [1,0] [2127] F=2*<<1,2,0:2>>-3*<<1,0,2:3>>+<<2,1,0:2>>; (1)*<<2,1,0:2>>+(2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>> [2128] M=dpm_hm(F); (1)*<<2,1,0:2>> [2129] C=dpm_hc(F); (1)*<<2,1,0>> [2130] R=dpm_rest(F); (2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>> [2131] dpm_hp(F); 2
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_td
, dp_sugar
:: Gets the total degree of the head term.
:: Gets the sugar
of a polynomial.
non-negative integer
distributed polynomial
flag
dp_td()
returns the total degree of the head term,
i.e., the sum of all exponent of variables in that term.
sugar
is associated. This value is
the total degree of the virtually homogenized one of the original
polynomial.
sugar
is an important guide to determine the
selection strategy of critical pairs in Groebner basis computation.
[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
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_lcm
:: Returns the least common multiple of the head terms of the given two polynomials.
distributed polynomial
distributed polynomial
[100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>); (1)*<<5,4,3,4,5>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_redble
:: Checks whether one head term is divisible by the other head term.
integer
distributed polynomial
[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
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_redble
:: Checks whether one head term is divisible by the other head term.
integer
module polynomial
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_subd
:: Returns the quotient monomial of the head terms.
distributed polynomial
distributed polynomial
dp_ht(dpoly1)/dp_ht(dpoly2)
.
The coefficient of the result is always set to 1.
[162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>); (1)*<<0,1,1,1,1>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_vtoe
, dp_etov
:: Converts an exponent vector into a term.
:: Convert the head term of a distributed polynomial into an exponent vector.
dp_vtoe
: distributed polynomial, dp_etov
: vector
vector
distributed polynomial
dp_vtoe()
generates a term whose exponent vector is vect.
dp_etov()
generates a vector which is the exponent vector of the
head term of dpoly
.
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_mbase
:: Computes the monomial basis
list of distributed polynomial
list of distributed polynomial
[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]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_mag
:: Computes the sum of bit lengths of coefficients of a distributed polynomial.
integer
distributed polynomial
ShowMag
and Print
for dp_gr_flags()
are on,
values of dp_mag()
for intermediate basis elements are shown.
[221] X=dp_ptod((x+2*y)^10,[x,y])$ [222] dp_mag(X); 115
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_red
, dp_red_mod
:: Single reduction operation
list
distributed polynomial
list
prime
dp_red_mod()
must be converted into a distributed
polynomial with coefficients in a finite field.
[a dpoly1,a dpoly2 - bt dpoly3]
.
[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>>]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dp_sp
, dp_sp_mod
:: Computation of an S-polynomial
distributed polynomial
distributed polynomial
prime
dp_sp_mod()
must be polynomials with coefficients in a
finite field.
[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>>
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
dpm_sp
:: Computation of an S-polynomial
module polynomial or list
module polynomial
[S,t1,t2]
,
where S
is the S-polynmial and t1
, t2
are monomials satisfying S=t1 dpoly1-t2 dpoly2
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
p_nf
, p_nf_mod
, p_true_nf
, p_true_nf_mod
:: Computes the normal form of the given polynomial. (The result may be multiplied by a constant.)
:: Computes the normal form of the given polynomial. (The result is returned
as a form of [numerator, denominator]
)
p_nf
: polynomial, p_true_nf
: list
polynomial
list
number, list or matrix
prime
dp_nf()
, dp_true_nf()
, dp_nf_mod()
,
dp_true_nf_mod
dp_nf()
.
dp_nf()
, dp_true_nf()
, dp_nf_mod()
and
dp_true_nf_mod()
is called with value 1 for fullreduce.
p_true_nf()
, p_true_nf_mod()
refer to dp_true_nf()
and dp_true_nf_mod()
.
[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
dp_ptod
,
dp_dtop
,
dp_ord
,
dp_nf
, dp_nf_mod
, dp_true_nf
, dp_true_nf_mod
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
p_terms
:: Monomials appearing in the given polynomial is collected into a list.
list
polynomial
list
number, list or matrix
[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]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
gb_comp
:: Checks whether two polynomial lists are equal or not as a set
[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
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
katsura
, hkatsura
, cyclic
, hcyclic
:: Generates a polynomial list of standard benchmark.
list
integer
katsura()
is defined in ‘katsura’, and
function cyclic()
in ‘cyclic’.
katsura
, cyclic
and their homogenized versions.
cyclic
is sometimes called by other name:
Arnborg
, Lazard
, and Davenport
.
[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]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
primadec
, primedec
:: Computes decompositions of ideals.
list of polynomials
list of variables
primadec()
and primedec
are defined in ‘primdec’.
primadec()
, primedec()
are the function for primary
ideal decomposition and prime decomposition of the radical over the
rationals respectively.
primadec
returns the list of pair lists consisting a primary component
and its associated prime.
primedec
returns the list of prime components.
PRIMAORD
, PRIMEORD
respectively.
primadec
implements the primary decompostion algorithm
in [Shimoyama,Yokoyama]
.
primedec
because primadec
may need additional costs
if an input ideal is not radical.
[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]]]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
primedec_mod
:: Computes decompositions of ideals over small finite fields.
list of polynomials
list of variables
number, list or matrix
positive integer
integer
primedec_mod()
is defined in ‘primdec_mod’ and implements the prime decomposition
algorithm in [Yokoyama]
.
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.
primedec_mod()
gives the decomposition over GF(mod).
The generators of each resulting component consists of integral polynomials.
dp_gr_print(2)
in advance.
[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]
modfctr
,
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
,
Setting term orderings,
dp_gr_flags
, dp_gr_print
.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
bfunction
, bfct
, generic_bfct
, ann
, ann0
:: Computes the global b function of a polynomial or an ideal
:: Computes the annihilator of a power of polynomial
polynomial or list
polynomial
list of polynomials
list of variables
bfunction(f)
and bfct(f)
compute the global b-function b(s)
of
a polynomial f.
b(s)
is a polynomial of the minimal degree
such that there exists P(x,s)
in D[s], which is a polynomial
ring over Weyl algebra D
, and P(x,s)f^(s+1)=b(s)f^s
holds.
generic_bfct(f,vlist,dvlist,weight)
computes the global b-function of a left ideal I
in D
generated by plist, with respect to weight.
vlist is the list of x
-variables,
vlist is the list of corresponding D
-variables.
bfunction(f)
and bfct(f)
implement
different algorithms and the efficiency depends on inputs.
ann(f)
returns the generator set of the annihilator
ideal of f^s
.
ann(f)
returns a list [a,list]
,
where a is the minimal integral root of the global b-function
of f, and list is a list of polynomials obtained by
substituting s
in ann(f)
with a.
[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 [220] P=x^3-y^2$ [221] ann(P); [2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y+6*s] [222] ann0(P); [-1,[2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y-6]]
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] |
This document was generated on December 14, 2019 using texi2html 5.0.