Groebner - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/MultivariateCyclicVector

Groebner

  

MultivariateCyclicVector

  

general-purpose and parametrizable iteration algorithm

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

MultivariateCyclicVector(NFproc, FDproc, TMproc, M)

Parameters

NFproc

-

function to compute normal forms

FDproc

-

function to find dependencies

TMproc

-

function to decide when to terminate

M

-

monomial order on an Ore algebra

Description

• 

The MultivariateCyclicVector command performs an iteration algorithm (similar to FGLM) to compute a Groebner basis with respect to M of (skew) polynomials whose normal forms under NFproc are zero.

• 

Common uses of the MultivariateCyclicVector command are the following.

  

(i) - To compute Groebner bases by change of ordering (a first Groebner basis is known for a monomial order, a second one is computed for another order).

  

(ii) - To find equations defining a function. See the Examples section.

• 

More specifically, NFproc takes three arguments.

m

a monomial in the algebra Malgebra;

NF

a table with monomials already dealt with as indices and normal forms already computed as corresponding entries;

M

a monomial order (actually, the table M of the call to MultivariateCyclicVector).

  

It returns a normal form for the monomial m and stores it as NFm into NF.

• 

FDproc takes two arguments:

mi

a list of monomials that generate a monoideal (that is, a set of monomials that is stable under product);

NF

is a table of the same type as above.

  

It returns either a nontrivial linear combination of the indices of NF that evaluates to 0 under NFproc, or FAIL when no such dependency exists.  This function must not use entries in NF corresponding to indices that are elements of the monoideal generated by mi.

• 

The procedure TMproc is used to decide when to stop the algorithm.  It takes three arguments.

border

 

a list of monomials still to be dealt with by the algorithm;

monoideal

 

a list of monomials that generate a monoideal (that is, a set of monomials that is stable under product);

TOrd

 

the monomial order with respect to which they are enumerated.

• 

The MultivariateCyclicVector command returns an expseq NF, EQ, where NF is the table of all normal forms computed during the calculations and EQ is a table of all linear dependencies found.

  

Note: The algorithm cannot detect non-zero-dimensional cases; it may loop forever when called on such cases.

• 

For the purpose of computing changes of orderings in the commutative case, the alternative command FGLM is more efficient.

Examples

Change of orderings

The FGLM algorithm was originally introduced to compute Groebner bases by a change of monomial orderings.

withOre_algebra:

withGroebner:

Apoly_algebrax,y,z,t:

Gx31x6xy,x8z,x10t,x2+y2+z2t2:

MorgMonomialOrderA,wdeg1,31,8,10,x,y,z,t:

Here is the initial Groebner basis.

GBorgBasisG,Morg

GBorg:=x8z,x2zt,tx6+z2,x6t3x+x+y,2t3x7+t6x2+tx6+2x72t3x2+tx2t2+2x2,t2x6+t6z2t4x32t3z+t2x2+2tx3+tz+2z,2t4x5+t7+t2x4+2tx52t4t2z+t2+2t

(1)

Check that you are in the zero-dimensional case.

HilbertDimension,Morg

0

(2)

Define NFproc and FDproc in view of a call to MultivariateCyclicVector.

NFproc:=proc(m,NF,MOrd)
    NF[m]:=NormalForm(m,GB[org],M[org])
end proc:

FDproc:=proc(M,NF)
    local ind_lst,term,eta,sol;
    ind_lst:=map(op,[indices(NF)]);
    for term in M do
        ind_lst:=remove(divide,ind_lst,term)
    end do;
    expand(numer(normal(add(eta[term]*NF[term],term=ind_lst))));
    sol:=[solve({coeffs(%,{x,y,z,t})},{seq(eta[term],term=ind_lst)})];
    subs(op(1,sol),add(eta[term]*term,term=ind_lst));
    `if`(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,
        map2(op,1,select(evalb,sol[1]))),%)),[x,y,z,t]),
        [x,y,z,t],distributed,factor))
end proc:

TMproc:=proc(border,monoideal,MOrd)
    border<>[]
end proc:

MnewMonomialOrderA&comma;tdegx&comma;y&comma;z&comma;t&colon;

fglmMultivariateCyclicVectorNFproc&comma;FDproc&comma;TMproc&comma;Mnew&colon;

Up to reordering, here is the final Groebner basis.

mapop&comma;entriesfglm2

t4t2xy&plus;2t2y2&plus;tz3&plus;xy3&plus;xyz2y4&plus;z4&plus;2tzxz&comma;t4yt3z2t2xz&plus;xz3&plus;t2x&plus;txty&plus;z2&comma;xz4t2xt2y&plus;xy2&plus;xz2&plus;y3&plus;yz2z&comma;t4z&plus;t3xy&plus;t2xy2xyz2&plus;z4&plus;t3ty2tz2t2txtytz2xy&comma;tz4t3txy&plus;ty2&plus;tz2xz2&comma;t3xy&plus;t2xz2z4t3&plus;ty2&plus;tz2&plus;t2&plus;2xyz2&comma;t4x&plus;tx&plus;ty&plus;z2&comma;2t4yt3xz&plus;ty42t2xztxyz&plus;xz3&plus;2z4t3&plus;2t2x2t2ztxy&plus;ty2&plus;tz2xz2t2&plus;2tx2ty&plus;xz&plus;yz&plus;2z2&comma;t3xyt2yz2&plus;xz3z4t2x&plus;txy&plus;t22y2z2&comma;txyz3&plus;2t3xt2z2z3&plus;t2&plus;txty2x2y&comma;t2z&plus;y2z&plus;z3&plus;t&comma;t2&plus;x2&plus;y2&plus;z2&comma;2t4yt4z&plus;4t2y3&plus;txz3&plus;tyz32y52t3x&plus;2t3z&plus;2txy2&plus;2txz2&plus;xyz2&plus;2t2y&plus;txz&plus;4tyz&plus;2xy2xyz2y32yz2&plus;tzt2z&comma;t4y&plus;t3y2t2xztxyz&plus;z4&plus;t2xt2&plus;txty&plus;z2&comma;z5t4&comma;t4z&plus;t3xz&plus;t3yzt2z3txz2xyz2&plus;txztz2yz&comma;yz4&plus;t3xt3ztxy2txz2t2yxy2&plus;y3&plus;yz2&plus;z&comma;t5&plus;txyz&plus;xz3&plus;t2

(3)

Computation of dependencies

Find equations that define the product φx&comma;yPnx, where P&lsqb;n&rsqb;x is the n-th Legendre polynomial and φx&comma;y is the generating function of the Legendre polynomials.

&phi;112xy&plus;y2

&phi;:=12xy&plus;y2&plus;1

(4)

Compute the derivative Q&lsqb;n&rsqb;x of P&lsqb;n&rsqb;x.

`diff/P`:=proc(x,v) Q[op(1,procname)](x)*diff(args) end proc:

Compute the derivative of Q&lsqb;n&rsqb;x.

`diff/Q`:=proc(x,v)
    local n;
    n:=op(1,procname);
    (2*x*Q[n](x)-n*(n+1)*P[n](x))*diff(args)/(1-x^2)
end proc:

Shift P&lsqb;n&rsqb;x and Q&lsqb;n&rsqb;x.

P&lsqb;n&plus;2&rsqb;x2n&plus;3xP&lsqb;n&plus;1&rsqb;xn&plus;1P&lsqb;n&rsqb;xn&plus;2

Pn&plus;2x:=2n&plus;3xPn&plus;1xn&plus;1Pnxn&plus;2

(5)

Q&lsqb;n&plus;1&rsqb;xn&plus;1P&lsqb;n&rsqb;xxQ&lsqb;n&rsqb;x1x2

Qn&plus;1x:=n&plus;1PnxxQnxx2&plus;1

(6)

Declare an Ore algebra and a monomial order to define phi, P and Q.

Askew_algebrashift&equals;Sn&comma;n&comma;diff&equals;Dx&comma;x&comma;diff&equals;Dy&comma;y&colon;

MMonomialOrderA&comma;tdegSn&comma;Dx&comma;Dy&colon;

Define NFproc and FDproc in view of a call to MultivariateCyclicVector.

NFproc:=proc(t,NF,MOrd)
    NF[t]:=normal(eval(subs(n=n+degree(t,Sn),
        diff(P[n](x)*phi,[x$degree(t,Dx),y$degree(t,Dy)]))))
end proc:

FDproc:=proc(M,NF)
    local ind_lst,t,eta,sol;
    ind_lst:=map(op,[indices(NF)]);
    for t in M do
        ind_lst:=remove(divide,ind_lst,t)
    end do;
    expand(numer(normal(add(eta[t]*NF[t],t=ind_lst))));
    coeffs(%,[P[n](x),P[n+1](x),Q[n](x)]);
    sol:=[solve({%},{seq(eta[t],t=ind_lst)})];
    subs(op(1,sol),add(eta[t]*t,t=ind_lst));
    `if`(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,
        map2(op,1,select(evalb,sol[1]))),%)),[Dx,Dy,Sn]),
        [Dx,Dy,Sn],distributed,factor))
end proc:

TMproc:=proc(border,monoideal,MOrd)
    border<>[]
end proc:

Compute equations satisfied by φx&comma;yPnx.

fglmMultivariateCyclicVectorNFproc&comma;FDproc&comma;TMproc&comma;M&colon;

mapop&comma;entriesfglm2

2xyy21Dy&plus;xy&comma;x1x&plus;12xyy21SnDxxn&plus;12xyy21Dx&plus;yx1x&plus;1Sn&plus;xyy21n&plus;1&comma;Sn2n&plus;2x2n&plus;3Sn&plus;n&plus;1&comma;x1x&plus;12xyy212Dx2&plus;22xyy213x2yxy2xyDx4n2x2y2&plus;4n2xy3n2y44nx2y2&plus;4nxy3ny4&plus;4n2xy2n2y2&plus;3x2y22xy3&plus;4nxy2ny2n22xy&plus;y2n

(7)

normalevalmapapplyopr&comma;&comma;&phi;P&lsqb;n&rsqb;x&comma;A

0&comma;0&comma;0&comma;0

(8)

References

  

Faugere, J. C.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient Computation of Zero-dimensional Grobner Bases by Change of Ordering." J. Symbolic Comput., Vol. 16, (1993): 329-344.

See Also

Groebner

Groebner[FGLM]

Groebner[MonomialOrder]

Ore_algebra

proc

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam