[ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

## 8.10 Functions for Groebner basis computation

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.1 `gr`, `hgr`, `gr_mod`, `dgr`

gr(plist,vlist,order)
hgr(plist,vlist,order)
gr_mod(plist,vlist,order,p)
dgr(plist,vlist,order,procs)

:: Groebner basis computation

return

list

plist vlist procs

list

order

number, list or matrix

p

prime less than 2^27

• These functions are defined in ‘gr’ in the standard library directory.
• Functions of which names contains gr are obsolted. Functions of `nd_gr` families should be used (`nd_gr`, `nd_gr_trace`, `nd_f4`, `nd_f4_trace`, `nd_weyl_gr`, `nd_weyl_gr_trace`).
• They compute a Groebner basis of a polynomial list plist with respect to the variable order vlist and the order type order. `gr()` and `hgr()` compute a Groebner basis over the rationals and `gr_mod` computes over GF(p).
• Variables not included in vlist are regarded as included in the ground field.
• `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.
• The CPU time shown after an exection of `dgr()` indicates that of the master process, and most of the time corresponds to the time for communication.
• When the elements of plist are distributed polynomials, the result is also a list of distributed polynomials. In this case, firstly the elements of plist is sorted by `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")\$
[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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.2 `lex_hensel`, `lex_tl`, `tolex`, `tolex_d`, `tolex_tl`

lex_hensel(plist,vlist1,order,vlist2,homo)
lex_tl(plist,vlist1,order,vlist2,homo)

: Groebner basis computation with respect to a lex order by change of ordering

tolex(plist,vlist1,order,vlist2)
tolex_d(plist,vlist1,order,vlist2,procs)
tolex_tl(plist,vlist1,order,vlist2,homo)

:: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis

return

list

plist vlist1 vlist2 procs

list

order

number, list or matrix

homo

flag

• These functions are defined in ‘gr’ in the standard library directory.
• `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.
• In `lex_hensel()` and `tolex_hensel()` a lex order Groebner basis is computed as follows.(Refer to `[Noro,Yokoyama]`.)
1. Compute a Groebner basis G0 with respect to vlist1 and order. (Only in `lex_hensel()`. )
2. Choose a prime which does not divide head coefficients of elements in G0 with respect to vlist1 and order. Then compute a lex order Groebner basis Gp over GF(p) with respect to vlist2.
3. Compute NF, the set of all the normal forms with respect to G0 of terms appearing in Gp.
4. For each element f in Gp, replace coefficients and terms in f with undetermined coefficients and the corresponding polynomials in NF respectively, and generate a system of liear equation Lf by equating the coefficients of terms in the replaced polynomial with 0.
5. Solve Lf by Hensel lifting, starting from the unique mod p solution.
6. If all the linear equations generated from the elements in Gp could be solved, then the set of solutions corresponds to a lex order Groebner basis. Otherwise redo the whole process with another p.
• In `lex_tl()` and `tolex_tl()` a lex order Groebner basis is computed as follows.(Refer to `[Noro,Yokoyama]`.)
1. Compute a Groebner basis G0 with respect to vlist1 and order. (Only in `lex_tl()`. )
2. If G0 is not zero-dimensional, choose a prime which does not divide head coefficients of elements in G0 with respect to vlist1 and order. Then compute a candidate of a lex order Groebner basis via trace lifting with p. If it succeeds the candidate is indeed a lex order Groebner basis without any check. Otherwise redo the whole process with another p.
3. If G0 is zero-dimensional, starting from G0, compute a Groebner basis G1 with respect to an elimination order to eliminate variables other than the last varibale in vlist2. Then compute a lex order Groebner basis stating from G1. These computations are done by trace lifting and the selection of a mudulus p is the same as in non zero-dimensional cases.
• Computations with rational function coefficients can be done only by `lex_tl()` and `tolex_tl()`.
• If `homo` is not equal to 0, homogenization is used in Buchberger algorithm.
• The CPU time shown after an execution of `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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.3 `lex_hensel_gsl`, `tolex_gsl`, `tolex_gsl_d`

lex_hensel_gsl(plist,vlist1,order,vlist2,homo)

::Computation of an GSL form ideal basis

tolex_gsl(plist,vlist1,order,vlist2)
tolex_gsl_d(plist,vlist1,order,vlist2,procs)

:: Computation of an GSL form ideal basis stating from a Groebner basis

return

list

plist vlist1 vlist2 procs

list

order

number, list or matrix

homo

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`.
• If the input is zero-dimensional and a lex order Groebner basis has the form `[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()`.
• 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 `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-...]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.4 `gr_minipoly`, `minipoly`

gr_minipoly(plist,vlist,order,poly,v,homo)

:: Computation of the minimal polynomial of a polynomial modulo an ideal

minipoly(plist,vlist,order,poly,v)

:: Computation of the minimal polynomial of a polynomial modulo an ideal

return

polynomial

plist vlist

list

order

number, list or matrix

poly

polynomial

v

indeterminate

homo

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.
• Let K be a field. If an ideal I in K[X] is zero-dimensional, then, for a polynomial p in K[X], the kernel of a homomorphism from K[v] to K[X]/I which maps f(v) to f(p) mod I is generated by a polynomial. The generator is called the minimal polynomial of p modulo I.
• `gr_minipoly()` and `minipoly()` computes the minimal polynomial of a polynomial p and returns it as a polynomial of v.
• The minimal polynomial can be computed as an element of a Groebner basis. But if we are only interested in the minimal polynomial, `minipoly()` and `gr_minipoly()` can compute it more efficiently than methods using Groebner basis computation.
• It is recommended to use a degree reverse lex order as a term order for `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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.5 `tolexm`, `minipolym`

tolexm(plist,vlist1,order,vlist2,mod)

:: Groebner basis computation modulo mod by change of ordering.

minipolym(plist,vlist1,order,poly,v,mod)

:: Minimal polynomial computation modulo mod the same method as

return

`tolexm()` : list, `minipolym()` : polynomial

plist vlist1 vlist2

list

order

number, list or matrix

mod

prime

• An input plist must be a Groebner basis modulo mod with respect to the variable order vlist1 and the order type order.
• `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+...
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.6 `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_gr_main(plist,vlist,homo,modular,order)
dp_gr_mod_main(plist,vlist,homo,modular,order)
dp_gr_f_main(plist,vlist,homo,order)
dp_weyl_gr_main(plist,vlist,homo,modular,order)
dp_weyl_gr_mod_main(plist,vlist,homo,modular,order)
dp_weyl_gr_f_main(plist,vlist,homo,order)

:: Groebner basis computation (built-in functions)

return

list

plist vlist

list

order

number, list or matrix

homo

flag

modular

flag or prime

• These functions are fundamental built-in functions for Groebner basis computation and `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()`.
• If homo is not equal to 0, homogenization is applied before entering Buchberger algorithm
• For `dp_gr_mod_main()`, modular means a computation over GF(modular). For `dp_gr_main()`, modular has the following mean.
1. If modular is 1 , trace lifting is used. Primes for trace lifting are generated by `lprime()`, starting from `lprime(0)`, until the computation succeeds.
2. If 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.
3. If modular is negative, the above rule is applied for -modular but the Groebner basis check and ideal-membership check are omitted in the last stage of trace lifting.
• `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.
• Actual computation is controlled by various parameters set by `dp_gr_flags()`, other then by homo and modular.
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.7 `dp_f4_main`, `dp_f4_mod_main`, `dp_weyl_f4_main`, `dp_weyl_f4_mod_main`

dp_f4_main(plist,vlist,order)
dp_f4_mod_main(plist,vlist,order)
dp_weyl_f4_main(plist,vlist,order)
dp_weyl_f4_mod_main(plist,vlist,order)

:: Groebner basis computation by F4 algorithm (built-in functions)

return

list

plist vlist

list

order

number, list or matrix

• These functions compute Groebner bases by F4 algorithm.
• F4 is a new generation algorithm for Groebner basis computation invented by J.C. Faugere. The current implementation of `dp_f4_main()` uses Chinese Remainder theorem and not highly optimized.
• Arguments and actions are the same as those of `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.
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.8 `nd_gr`, `nd_gr_trace`, `nd_f4`, `nd_f4_trace`, `nd_weyl_gr`, `nd_weyl_gr_trace`

nd_gr(plist,vlist,p,order[|option=value,...])
nd_gr_trace(plist,vlist,homo,p,order[|option=value,...])
nd_f4(plist,vlist,modular,order[|option=value,...])
nd_f4_trace(plist,vlist,homo,p,order[|option=value,...])
nd_weyl_gr(plist,vlist,p,order[|option=value,...])
nd_weyl_gr_trace(plist,vlist,homo,p,order[|option=value,...])

:: Groebner basis computation (built-in functions)

return

list

plist vlist

list

order

number, list or matrix

homo

flag

modular

flag or prime

• These functions are new implementations for computing Groebner bases.
• `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.
• Functions except for F4 related ones can handle rational coeffient cases.
• In general these functions are more efficient than `dp_gr_main`, `dp_gr_mod_main`, especially over finite fields.
• The fallowing options can be specified.
`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)
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.9 `nd_gr_postproc`, `nd_weyl_gr_postproc`

nd_gr_postproc(plist,vlist,p,order,check)
nd_weyl_gr_postproc(plist,vlist,p,order,check)

:: Check of Groebner basis candidate and inter-reduction

return

list or 0

plist vlist

list

p

prime or 0

order

number, list or matrix

check

0 or 1

• Perform the inter-reduction for a Groebner basis (candidate).
• `nd_weyl_gr_postproc` is for Weyl algebra.
• If check=1 then the check whether plist is a Groebner basis with respect to a term order in a polynomial ring or Weyl algebra specified by vlist, p and order.
• This function is used for inter-reduction of a non-reduced Groebner basis that is obtained by dehomogenizing a Groebner basis computed via homogenization, or Groebner basis check of a Groebner basis candidate computed by CRT.
```afo
```

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.10 `dp_gr_flags`, `dp_gr_print`

dp_gr_flags([list])
dp_gr_print([i])

and showing informations.

return

value currently set

list

list

i

integer

• `dp_gr_flags()` sets and shows various parameters for Groebner basis computation.
• If no argument is specified the current settings are returned.
• Arguments must be specified as a list such as `["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`.
i=0

`Print=0`, `PrintShort=0`

i=1

`Print=1`, `PrintShort=0`

i=2

`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.

References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.11 `dp_ord`

dp_ord([order])

:: Set and show the ordering type.

return

ordering type (number, list or matrix)

order

number, list or matrix

• If an argument is specified, the function sets the current ordering type to order. If no argument is specified, the function returns the ordering type currently set.
• 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.
• Functions such as `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.

• Type of term ordering must be correctly set by this function when functions other than top level functions are called directly.
• If the argument is a list, then an ordering type in a free module is set. If the argument is `[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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.12 `dp_set_weight`, `dp_set_top_weight`, `dp_weyl_set_weight`

dp_set_weight([weight])

:: Set and show the sugar weight.

dp_set_top_weight([weight])

:: Set and show the top weight.

dp_weyl_set_weight([weight])

:: Set and show the weyl weight.

return

a vector

weight

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.
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.13 `dp_ptod`

dp_ptod(poly,vlist)

:: Converts an ordinary polynomial into a distributed polynomial.

return

distributed polynomial

poly

polynomial

vlist

list

• According to the variable ordering vlist and current type of term ordering, this function converts an ordinary polynomial into a distributed polynomial.
• Indeterminates not included in vlist are regarded to belong to the coefficient field.
```[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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.14 `dpm_dptodpm`

dpm_dptodpm(dpoly,pos)

:: Converts a distributed polynomial into a module polynomial.

return

module polynomial

dpoly

distributed polynomial

pos

positive integer

• This function converts a distributed polynomial into a module polynomial.
• The output is `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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.15 `dpm_ltod`

dpm_dptodpm(plist,vlist)

:: Converts a list of polynomials into a module polynomial.

return

module polynomial

plist

list of polynomials

vlist

list of variables

• This function converts a list of polynomials into a module polynomial.
• `[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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.16 `dpm_dtol`

dpm_dptodpm(poly,vlist)

:: Converts a module polynomial into a list of polynomials.

return

list of polynomials

poly

module polynomial

vlist

list of variables

• This function converts a module polynomial into a list of polynomials.
• `p1 e1+...+pm em` is converted into `[p1,...,pm]`.
• The length of the output list is equal to the largest index among those of the standard bases containd in `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]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.17 `dp_dtop`

dp_dtop(dpoly,vlist)

:: Converts a distributed polynomial into an ordinary polynomial.

return

polynomial

dpoly

distributed polynomial

vlist

list

• This function converts a distributed polynomial into an ordinary polynomial according to a list of indeterminates vlist.
• vlist is such a list that its length coincides with the number of variables of dpoly.
```[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] [ ? ]

### 8.10.18 `dp_mod`, `dp_rat`

dp_mod(p,mod,subst)

:: Converts a disributed polynomial into one with coefficients in a finite field.

dp_rat(p)

:: Converts a distributed polynomial with coefficients in a finite field into one with coefficients in the rationals.

return

distributed polynomial

p

distributed polynomial

mod

prime

subst

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.
• The ground finite field must be set in advance by using `setmod()`.
• subst is such a list as `[[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.
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.19 `dp_homo`, `dp_dehomo`

dp_homo(dpoly)

:: Homogenize a distributed polynomial

dp_dehomo(dpoly)

:: Dehomogenize a homogenious distributed polynomial

return

distributed polynomial

dpoly

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.
• Appropriate term orderings must be set when the results are used as inputs of some operations.
• These are used internally in `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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.20 `dp_ptozp`, `dp_prim`

dp_ptozp(dpoly)

:: Converts a distributed polynomial poly with rational coefficients into an integral distributed polynomial such that GCD of all its coefficients is 1.

dp_prim(dpoly)

:: Converts a distributed polynomial poly with rational function coefficients into an integral distributed polynomial such that polynomial GCD of all its coefficients is 1.

return

distributed polynomial

dpoly

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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.21 `dp_nf`, `dp_nf_mod`, `dp_true_nf`, `dp_true_nf_mod`

dp_nf(indexlist,dpoly,dpolyarray,fullreduce)
dp_weyl_nf(indexlist,dpoly,dpolyarray,fullreduce)
dp_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)
dp_weyl_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)

:: Computes the normal form of a distributed polynomial. (The result may be multiplied by a constant in the ground field.)

dp_true_nf(indexlist,dpoly,dpolyarray,fullreduce)
dp_true_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)

:: Computes the normal form of a distributed polynomial. (The true result is returned in such a list as `[numerator, denominator]`)

return

`dp_nf()` : distributed polynomial, `dp_true_nf()` : list

indexlist

list

dpoly

distributed polynomial

dpolyarray

array of distributed polynomial

fullreduce

flag

mod

prime

• Computes the normal form of a distributed polynomial.
• Functions whose name contain `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.
• The result of `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.
• dpolyarray is a vector whose components are distributed polynomials and indexlist is a list of indices which is used for the normal form computation.
• When argument fullreduce has non-zero value, all terms are reduced. When it has value 0, only the head term is reduced.
• As for the polynomials specified by indexlist, one specified by an index placed at the preceding position has priority to be selected.
• In general, the result of the function may be different depending on indexlist. However, the result is unique for Groebner bases.
• 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 `p_nf` and `p_true_nf` are sufficient.
```[0] load("gr")\$
[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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.22 `dpm_nf`, `dpm_nf_and_quotient`

dpm_nf([indexlist,]dpoly,dpolyarray,fullreduce)

:: Computes the normal form of a module polynomial. (The result may be multiplied by a constant in the ground field.)

dpm_nf_and_quotient([indexlist,]dpoly,dpolyarray)

:: Computes the normal form of a module polynomial and the quotient.

return

`dpm_nf()` : module polynomial, `dpm_nf_and_quotient()` : list

indexlist

list

dpoly

module polynomial

dpolyarray

array of module polynomial

• Computes the normal form of a module polynomial.
• The result of `dpm_nf()` may be multiplied by a constant in the ground field in order to make the result integral.
• dpolyarray is a vector whose components are module polynomials and indexlist is a list of indices which is used for the normal form computation.
• If indexlist is given, only the polynomials in dpolyarray specified in indexlist is used in the division. An index placed at the preceding position has priority to be selected. If indexlist is not given, all the polynomials in dpolyarray are used.
• `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]+....
• When argument fullreduce has non-zero value, all terms are reduced. When it has value 0, only the head term is reduced.
```[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
```
References

@ref{dpm_sp}, `dp_ord`.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.23 `dp_hm`, `dp_ht`, `dp_hc`, `dp_rest`

dp_hm(dpoly)

dp_ht(dpoly)

dp_hc(dpoly)

dp_rest(dpoly)

:: Gets the remainder of the polynomial where the head monomial is removed.

return

`dp_hm()`, `dp_ht()`, `dp_rest()` : distributed polynomial `dp_hc()` : number or polynomial

dpoly

distributed polynomial

• These are used to get various parts of a distributed polynomial.
• The next equations hold for a distributed polynomial p.
`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] [ ? ]

### 8.10.24 `dpm_hm`, `dpm_ht`, `dpm_hc`, `dpm_hp`, `dpm_rest`

dpm_hm(dpoly)

:: Gets the head monomial of a module polynomial.

dpm_ht(dpoly)

:: Gets the head term of a module polynomial.

dpm_hc(dpoly)

:: Gets the head coefficient of a module polynomial.

dpm_hp(dpoly)

:: Gets the head position of a module polynomial.

dpm_rest(dpoly)

:: Gets the remainder of a module polynomial where the head monomial is removed.

return

`dpm_hm()`, `dpm_ht()`, `dpm_rest()` : module polynomial `dpm_hc()` : monomial

dpoly

distributed polynomial

• These are used to get various parts of a module 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] [ ? ]

### 8.10.25 `dp_td`, `dp_sugar`

dp_td(dpoly)

:: Gets the total degree of the head term.

dp_sugar(dpoly)

:: Gets the `sugar` of a polynomial.

return

non-negative integer

dpoly

distributed polynomial

onoff

flag

• Function `dp_td()` returns the total degree of the head term, i.e., the sum of all exponent of variables in that term.
• Upon creation of a distributed polynomial, an integer called `sugar` is associated. This value is the total degree of the virtually homogenized one of the original polynomial.
• The quantity `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] [ ? ]

### 8.10.26 `dp_lcm`

dp_lcm(dpoly1,dpoly2)

:: Returns the least common multiple of the head terms of the given two polynomials.

return

distributed polynomial

dpoly1 dpoly2

distributed polynomial

• Returns the least common multiple of the head terms of the given two polynomials, where coefficient is always set to 1.
```[100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
(1)*<<5,4,3,4,5>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.27 `dp_redble`

dp_redble(dpoly1,dpoly2)

:: Checks whether one head term is divisible by the other head term.

return

integer

dpoly1 dpoly2

distributed polynomial

• Returns 1 if the head term of dpoly2 divides the head term of dpoly1; otherwise 0.
• Used for finding candidate terms at reduction of polynomials.
```[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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.28 `dpm_redble`

dpm_redble(dpoly1,dpoly2)

:: Checks whether one head term is divisible by the other head term.

return

integer

dpoly1 dpoly2

module polynomial

• Returns 1 if the head term of dpoly2 divides the head term of dpoly1; otherwise 0.
• Used for finding candidate terms at reduction of polynomials.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.29 `dp_subd`

dp_subd(dpoly1,dpoly2)

:: Returns the quotient monomial of the head terms.

return

distributed polynomial

dpoly1 dpoly2

distributed polynomial

• Gets `dp_ht(dpoly1)/dp_ht(dpoly2)`. The coefficient of the result is always set to 1.
• Divisibility assumed.
```[162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
(1)*<<0,1,1,1,1>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.30 `dp_vtoe`, `dp_etov`

dp_vtoe(vect)

:: Converts an exponent vector into a term.

dp_etov(dpoly)

:: Convert the head term of a distributed polynomial into an exponent vector.

return

`dp_vtoe` : distributed polynomial, `dp_etov` : vector

vect

vector

dpoly

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] [ ? ]

### 8.10.31 `dp_mbase`

dp_mbase(dplist)

:: Computes the monomial basis

return

list of distributed polynomial

dplist

list of distributed polynomial

• Assuming that dplist is a list of distributed polynomials which is a Groebner basis with respect to the current ordering type and that the ideal I generated by dplist in K[X] is zero-dimensional, this function computes the monomial basis of a finite dimenstional K-vector space K[X]/I.
• The number of elements in the monomial basis is equal to the K-dimenstion of K[X]/I.
```[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]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.32 `dp_mag`

dp_mag(p)

:: Computes the sum of bit lengths of coefficients of a distributed polynomial.

return

integer

p

distributed polynomial

• This function computes the sum of bit lengths of coefficients of a distributed polynomial p. If a coefficient is non integral, the sum of bit lengths of the numerator and the denominator is taken.
• 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.
• If `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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.33 `dp_red`, `dp_red_mod`

dp_red(dpoly1,dpoly2,dpoly3)
dp_red_mod(dpoly1,dpoly2,dpoly3,mod)

:: Single reduction operation

return

list

dpoly1 dpoly2 dpoly3

distributed polynomial

vlist

list

mod

prime

• Reduces a distributed polynomial, dpoly1 + dpoly2, by dpoly3 for single time.
• An input for `dp_red_mod()` must be converted into a distributed polynomial with coefficients in a finite field.
• This implies that the divisibility of the head term of dpoly2 by the head term of dpoly3 is assumed.
• When integral coefficients, computation is so carefully performed that no rational operations appear in the reduction procedure. It is computed for integers a and b, and a term t as: a(dpoly1 + dpoly2)-bt dpoly3.
• The result is a list `[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>>]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.34 `dp_sp`, `dp_sp_mod`

dp_sp(dpoly1,dpoly2)
dp_sp_mod(dpoly1,dpoly2,mod)

:: Computation of an S-polynomial

return

distributed polynomial

dpoly1 dpoly2

distributed polynomial

mod

prime

• This function computes the S-polynomial of dpoly1 and dpoly2.
• Inputs of `dp_sp_mod()` must be polynomials with coefficients in a finite field.
• The result may be multiplied by a constant in the ground field in order to make the result integral.
```[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>>
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.35 `dpm_sp`

dpm_sp(dpoly1,dpoly2[|coef=1])

:: Computation of an S-polynomial

return

module polynomial or list

dpoly1 dpoly2

module polynomial

• This function computes the S-polynomial of dpoly1 and dpoly2.
• If an option coef=1 is specified, it returns a list `[S,t1,t2]`, where `S` is the S-polynmial and `t1`, `t2` are monomials satisfying `S=t1 dpoly1-t2 dpoly2`.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.36 `dpm_schreyer_base`

dpm_schreyer_base(G)

:: Computation of a Groebner basis of the syzygy module

return

list of module polynomials

G

list of module polynomials

• This function computes a minimal Groebner basis of syz(G) for a Groenber basis G that is represented as a list of module polynomials.
• The result is a Groebner basis with respect to a Schreyer ordering determined by the leading terms of G. As a side effect, this Schreyer ordering is autoatically set.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.37 `dpm_schreyer_frame`

dpm_schreyer_frame(G)

:: Computation of the Schreyer frame

return

a list of lists of module monomials

G

list of module polynomials

• This function computes the Schreyer frame starting from a Groebner basis G, that is the lists of leading monomials of Groebner bases of syzygy modules with respect to Schreyer orderings in the Schreyer free resolution.
• The result is a list [M_m,...,M_1], where M_i is the list of leading monomials of the images of standard bases of the free module F_i in the Schreyer free resolution.
• As a by-product, data for setting a Schreyer order in each level are created. The date are used by `dpm_set_schreyer_level` for setting a Schreyer order in each level.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.38 `dpm_set_schreyer_level`

dpm_set_schreyer_level(L)

:: Setting the Schreyer ordering of a specified level

return

a non-negative integer

G

a non-negative integer

• This function computes the Schreyer frame starting from a Groebner basis G, that is the lists of leading monomials of Groebner bases of syzygy modules with respect to Schreyer orderings in the Schreyer free resolution.
• The result is a list [M_m,...,M_1], where M_i is the list of leading monomials of the images of standard bases of the free module F_i in the Schreyer free resolution.
• As a by-product, data for setting a Schreyer order in each level are created. The date are used by `dpm_set_schreyer_level` for setting a Schreyer order in each level.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.39 `dpm_sp_nf`

dpm_sp_nf(C,Z,P,Q)

:: Computation of a remainder of an S-polynomial modulo a polynomial array

return

a list of module monomials

C

an array of module polynomials

Z

an array of integer lists

P
Q

integers

• When the remainder of the S-polynomial of C[P] and C[Q] modulo C is represented as ct C[P]-c’t’C[Q]=g_1C[1]+...+g_LC[L]+f, this function returns a list [g’,f], where g’=ct eP-c’t’ eQ-(g_1 e1+...+gL e_L).
• The I-th element of an array Z is a list of indices of elements of C whose leading position is I.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.40 `p_nf`, `p_nf_mod`, `p_true_nf`, `p_true_nf_mod`

p_nf(poly,plist,vlist,order)
p_nf_mod(poly,plist,vlist,order,mod)

:: Computes the normal form of the given polynomial. (The result may be multiplied by a constant.)

p_true_nf(poly,plist,vlist,order)
p_true_nf_mod(poly,plist,vlist,order,mod)

:: Computes the normal form of the given polynomial. (The result is returned as a form of `[numerator, denominator]`)

return

`p_nf` : polynomial, `p_true_nf` : list

poly

polynomial

plist vlist

list

order

number, list or matrix

mod

prime

• Defined in the package ‘gr’.
• Obtains the normal form of a polynomial by a polynomial list.
• These are interfaces to `dp_nf()`, `dp_true_nf()`, `dp_nf_mod()`, `dp_true_nf_mod`
• The polynomial poly and the polynomials in plist is converted, according to the variable ordering vlist and type of term ordering otype, into their distributed polynomial counterparts and passed to `dp_nf()`.
• `dp_nf()`, `dp_true_nf()`, `dp_nf_mod()` and `dp_true_nf_mod()` is called with value 1 for fullreduce.
• The result is converted back into an ordinary polynomial.
• As for `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
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.41 `p_terms`

p_terms(poly,vlist,order)

:: Monomials appearing in the given polynomial is collected into a list.

return

list

poly

polynomial

vlist

list

order

number, list or matrix

• Defined in the package ‘gr’.
• 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 vlist.
• 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.
```[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] [ ? ]

### 8.10.42 `gb_comp`

gb_comp(plist1, plist2)

:: Checks whether two polynomial lists are equal or not as a set

return 0 or 1
plist1 plist2
• This function checks whether plist1 and plist2 are equal or not as a set .
• 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.
```[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] [ ? ]

### 8.10.43 `katsura`, `hkatsura`, `cyclic`, `hcyclic`

katsura(n)
hkatsura(n)
cyclic(n)
hcyclic(n)

:: Generates a polynomial list of standard benchmark.

return

list

n

integer

• Function `katsura()` is defined in ‘katsura’, and function `cyclic()` in ‘cyclic’.
• These functions generate a series of polynomial sets, respectively, which are often used for testing and bench marking: `katsura`, `cyclic` and their homogenized versions.
• Polynomial set `cyclic` is sometimes called by other name: `Arnborg`, `Lazard`, and `Davenport`.
```[74] load("katsura")\$
[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]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.44 `primadec`, `primedec`

primedec(plist,vlist)

:: Computes decompositions of ideals.

return
plist

list of polynomials

vlist

list of variables

• A new package ‘noro_pd.rr’ provides more efficient functions for ideal decomposition.
• Function `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.
• The arguments are a list of polynomials and a list of variables. These functions accept ideals with rational function coefficients only.
• `primadec` returns the list of pair lists consisting a primary component and its associated prime.
• `primedec` returns the list of prime components.
• Each component is a Groebner basis and the corresponding term order is indicated by the global variables `PRIMAORD`, `PRIMEORD` respectively.
• `primadec` implements the primary decompostion algorithm in `[Shimoyama,Yokoyama]`.
• If one only wants to know the prime components of an ideal, then use `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]]
[[[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]]]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.45 `primedec_mod`

primedec_mod(plist,vlist,ord,mod,strategy)

:: Computes decompositions of ideals over small finite fields.

return
plist

list of polynomials

vlist

list of variables

ord

number, list or matrix

mod

positive integer

strategy

integer

• Function `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.
• Each resulting component is a Groebner basis with respect to a term order specified by [vlist,ord].
• If 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.
• If you want to see internal information during the computation, execute `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]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 8.10.46 `bfunction`, `bfct`, `generic_bfct`, `ann`, `ann0`

bfunction(f)
bfct(f)
generic_bfct(plist,vlist,dvlist,weight)

:: Computes the global b function of a polynomial or an ideal

ann(f)
ann0(f)

:: Computes the annihilator of a power of polynomial

return

polynomial or list

f

polynomial

plist

list of polynomials

vlist dvlist

list of variables

• These functions are defined in ‘bfct’.
• `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.
• See [Saito,Sturmfels,Takayama] for the details.
```[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]]
```
References

 [ << ] [ < ] [ Up ] [ > ] [ >> ]

This document was generated on July 15, 2024 using texi2html 5.0.