Groebner - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Groebner

  

Walk

  

convert Groebner bases from one ordering to another

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

Walk(G, T1, T2, opts)

Parameters

G

-

Groebner basis with respect to starting order T1 or a PolynomialIdeal

T1,T2

-

monomial orders (of type ShortMonomialOrder)

opts

-

optional arguments of the form keyword=value

Description

• 

The Groebner walk algorithm converts a Groebner basis of commutative polynomials from one monomial order to another.  It is frequently applied when a Groebner basis is too difficult to compute directly.

• 

The Walk command takes as input a Groebner basis G with respect to a monomial order T1, and outputs the reduced Groebner basis for G with respect to T2.  If the first argument G is a PolynomialIdeal then a Groebner basis for G with respect to T1 is computed if one is not already known.  

• 

The orders T1 and T2 must be proper monomial orders on the polynomial ring, so 'min' orders such as 'plex_min' and 'tdeg_min' are not supported. Walk does not check that G is a Groebner basis with respect to T1.

• 

Unlike FGLM, the ideal defined by G can have an infinite number of solutions. The Groebner walk is typically not as fast as FGLM on zero-dimensional ideals.

• 

The optional argument characteristic=p specifies the characteristic of the coefficient field. The default is zero.  This option is ignored if G is a PolynomialIdeal.

• 

The optional argument elimination=true forces the Groebner walk to terminate early, before a Groebner basis with respect to T2 is obtained.  If T2 is a lexdeg order with two blocks of variables the resulting list will contain a generating set of the elimination ideal.

• 

The optional argument output=basislm returns the basis in an extended format containing leading monomials and coefficients.  Each element is a list of the form [leading coefficient, leading monomial, polynomial].

• 

Setting infolevel[Walk] to a positive integer value directs the Walk command to output increasingly detailed information about its performance and progress.

Examples

withGroebner:

F110xz6x38y2z2,6z+5y3

F18y2z26x3+10xz,5y36z

(1)

G1BasisF1,tdegx,y,z

G15y36z,4y2z2+3x35xz,15x3y25xyz+24z3,45x696yz5150x4z+125x2z2

(2)

WalkG1,tdegx,y,z,plexx,y,z

5y36z,4y2z2+3x35xz

(3)

aliasα=RootOfz2+z+5

α

(4)

F210yx9x3+2zα24y3α,6α22x2α+9xα28y3x:

G2BasisF2,tdegx,y,z

G210yx+2α+10z+9x3+4y3α,6α+30+8y3x+2x2α+9α+45x,24α+30+32y616αy3z+56α+10x2+72α+90z+36α+45x+60αy+4α+20xz+36α+180y3

(5)

WalkG2,tdegx,y,z,plexx,y,z

9216y124608αy9z+31104αy9+155520y9+16640αy762208αy6z+293616αy63200y7+77760y6z+1280αy4z+724480y6+149040αy4215080αy3z1600y4z+670680y3α208800y4+732600zy34800αy2+3960αyz+896αz2+984150y3+298890αy156735αz+6000y216200yz+880z2+96228α854550y+1676700z393660,314125516800αy9z415975784120320αy10z25536014336000αy9z3+300987187200y9z4546360629280768αy1132882551603200αy10z10435297443840αy9z2322486272000αy6z58668550430720y10z214135648256000y9z3+1967799836731392αy10+1947158001561600αy9z4917019852800αy7z3+1310100480000αy6z41139103470665728y11359455142707200y10z524766413168640y9z2725594112000y6z5+27199544370884352αy9+235447336673280αy8z14674245120000αy7z2+163796824166400αy6z337324800000αy3z67560832848058368y10670150659686400y9z39028901068800y7z37759825920000y6z47519204604620800αy8+3675750562759680αy7z+227541778560000αy6z2+66355200000αy4z44534963200000αy3z5+32041679675265792y91409502931845120y8z42639851520000y7z2175841686425600y6z337324800000y3z6+2614664021875200αy7+16968987770878080αy6z+5039700480000αy5z2129548782080000αy4z3+21017180160000αy3z47353752910796800y8+257997550049280y7z1314534666240000y6z2213580800000y4z47054387200000y3z5629856000000αxz5+321705392979406400αy61018259361792000αy5z+347786987328000αy4z2+2203937994240000αy3z3+139968000000αyz5209952000000αz6+46656000000xz6107487335683180800y7+39860784187015680y6z2537233920000y5z2380772679680000y4z3209844224640000y3z418743464800000αxz439416496242604800αy5+45006197725728000αy4z+18852048082512000αy3z2+4076179200000αy2z3+58320000000αyz415446376000000αz5+88088744959114400y618392297260032000y5z2230302304512000y4z23045221256960000y3z3+139968000000yz5+94478400000000αxz323046304810528800αy4+163552851034668000αy3z32611248000000αy2z2528160248000000αyz32927664000000αz438688904800000xz426046898913260800y525470717458112000y4z+31476478240152000y3z2+11844403200000y2z3+6298560000000yz417937936000000z5+5550200727030000αxz2+841574249783608500y3α11336483045680000αy2z1020432054600000αyz2+6063266599200000αz3737167716000000xz3568616554967464800y4+682176021898628000zy3+94950792000000y2z2696965508000000yz3870738012000000z4+38444953961075000αxz104840997530040000αy2+95020410601170000αyz+85139930065725000αz23875300052120000xz2307559853657459000y349118173405280000y2z8777828946600000z2y12373762321800000z3+94086819258781500αx200252907899415000αy+597219742017708750αz+84698873079075000xz22027797731340000y2187882578562680000yz+109342506627225000z217319759203700000α+991358206562039625x1534072805076652500y+2118938395306196250z+48514014178143750,40326912αy9205141248y9+121150080αy6z51710400αy6+78382080y6z+10425600αy3z22779336800y6460252800αy4+1331445600αy3z3960000y3z23596400αxz21130633900y3α378064800y4246564000zy3+42460200αxz39096000αyz+42460200αz213032000xz27894611000y3+1702428300αx2617839000αy+3396141950αz+579121000yx80919000xz+14850000yz80919000z2+92534400α+238838625x+22477500y2853557750z+159225750,896αy6736y680αy3z4860y3α2240zy3540αxz+900y31440αx+300αy2880αz+7610x2+100xz960α6075x+8400y12150z4050

(6)

References

  

Amrhein, B.; Gloor, O.; and Kuchlin, W. "On the Walk." Theoretical Comput. Sci., Vol. 187, (1997): 179-202.

  

Collart, S.; Kalkbrener, M.; and Mall, D. "Converting Bases with the Grobner Walk." J. Symbolic Comput., Vol. 3, No. 4, (1997): 465-469.

  

Tran, Q.N. "A Fast Algorithm for Grobner Basis Conversion and Its Applications." J. Symbolic Comput., Vol. 30, (2000): 451-467.

See Also

Basis

FGLM