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

F1:=8y2z26x3+10xz,5y36z

(1)

G1BasisF1,tdegx,y,z

G1:=5y36z,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

G2:=2RootOf_Z2+_Z+5+10z+9x3+4y3RootOf_Z2+_Z+5+10yx,6RootOf_Z2+_Z+5+30+2x2RootOf_Z2+_Z+5+9RootOf_Z2+_Z+5+45x+8y3x,24RootOf_Z2+_Z+5+30+32y6+56RootOf_Z2+_Z+5+10x2+72RootOf_Z2+_Z+5+90z+36RootOf_Z2+_Z+5+45x+60RootOf_Z2+_Z+5y16RootOf_Z2+_Z+5y3z+36RootOf_Z2+_Z+5+180y3+4RootOf_Z2+_Z+5+20xz

(5)

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

3936601600y4z208800y416200yz+77760y6z+155520y9+724480y6+96228RootOf_Z2+_Z+5+880z2+31104RootOf_Z2+_Z+5y9+16640RootOf_Z2+_Z+5y7+293616RootOf_Z2+_Z+5y6+149040RootOf_Z2+_Z+5y44800RootOf_Z2+_Z+5y2+896RootOf_Z2+_Z+5z24608RootOf_Z2+_Z+5y9z62208RootOf_Z2+_Z+5y6z+1280RootOf_Z2+_Z+5y4z+3960RootOf_Z2+_Z+5yz+9216y12+1676700z854550y156735RootOf_Z2+_Z+5z+298890RootOf_Z2+_Z+5y+732600y3z215080RootOf_Z2+_Z+5y3z3200y7+984150y3+6000y2+670680y3RootOf_Z2+_Z+5,14135648256000y9z3175841686425600y6z33045221256960000y3z3737167716000000xz3359455142707200y10z+257997550049280y7z25470717458112000y4z+300987187200y9z4725594112000y6z57759825920000y6z437324800000y3z67054387200000y3z5+46656000000xz6209844224640000y3z4+139968000000yz538688904800000xz48777828946600000z2y8668550430720y10z239028901068800y7z342639851520000y7z2213580800000y4z4380772679680000y4z32230302304512000y4z2+11844403200000y2z3+6298560000000yz4696965508000000yz31409502931845120y8z2537233920000y5z218392297260032000y5z49118173405280000y2z870738012000000z417937936000000z57353752910796800y826046898913260800y5568616554967464800y41139103470665728y11187882578562680000yz3875300052120000xz2+39860784187015680y6z+32041679675265792y9+88088744959114400y617319759203700000RootOf_Z2+_Z+5+109342506627225000z2+27199544370884352RootOf_Z2+_Z+5y9+2614664021875200RootOf_Z2+_Z+5y7+321705392979406400RootOf_Z2+_Z+5y623046304810528800RootOf_Z2+_Z+5y4104840997530040000RootOf_Z2+_Z+5y2+85139930065725000RootOf_Z2+_Z+5z2546360629280768RootOf_Z2+_Z+5y11+1967799836731392RootOf_Z2+_Z+5y107519204604620800RootOf_Z2+_Z+5y8209952000000RootOf_Z2+_Z+5z639416496242604800RootOf_Z2+_Z+5y515446376000000RootOf_Z2+_Z+5z52927664000000RootOf_Z2+_Z+5z4+6063266599200000RootOf_Z2+_Z+5z315975784120320RootOf_Z2+_Z+5y10z25536014336000RootOf_Z2+_Z+5y9z332882551603200RootOf_Z2+_Z+5y10z10435297443840RootOf_Z2+_Z+5y9z2322486272000RootOf_Z2+_Z+5y6z54917019852800RootOf_Z2+_Z+5y7z3+1310100480000RootOf_Z2+_Z+5y6z4+235447336673280RootOf_Z2+_Z+5y8z14674245120000RootOf_Z2+_Z+5y7z2+163796824166400RootOf_Z2+_Z+5y6z337324800000RootOf_Z2+_Z+5y3z6+3675750562759680RootOf_Z2+_Z+5y7z+227541778560000RootOf_Z2+_Z+5y6z2+66355200000RootOf_Z2+_Z+5y4z44534963200000RootOf_Z2+_Z+5y3z5+5039700480000RootOf_Z2+_Z+5y5z2129548782080000RootOf_Z2+_Z+5y4z3+21017180160000RootOf_Z2+_Z+5y3z4629856000000RootOf_Z2+_Z+5xz51018259361792000RootOf_Z2+_Z+5y5z+347786987328000RootOf_Z2+_Z+5y4z2+2203937994240000RootOf_Z2+_Z+5y3z3+139968000000RootOf_Z2+_Z+5yz518743464800000RootOf_Z2+_Z+5xz4+18852048082512000RootOf_Z2+_Z+5y3z2+4076179200000RootOf_Z2+_Z+5y2z3+58320000000RootOf_Z2+_Z+5yz4+94478400000000RootOf_Z2+_Z+5xz332611248000000RootOf_Z2+_Z+5y2z2528160248000000RootOf_Z2+_Z+5yz3+5550200727030000RootOf_Z2+_Z+5xz211336483045680000RootOf_Z2+_Z+5y2z1020432054600000RootOf_Z2+_Z+5yz2+1947158001561600RootOf_Z2+_Z+5y9z+16968987770878080RootOf_Z2+_Z+5y6z+45006197725728000RootOf_Z2+_Z+5y4z+95020410601170000RootOf_Z2+_Z+5yz314125516800RootOf_Z2+_Z+5y9z4+2118938395306196250z+991358206562039625x1534072805076652500y+597219742017708750RootOf_Z2+_Z+5z+94086819258781500RootOf_Z2+_Z+5x200252907899415000RootOf_Z2+_Z+5y+94950792000000y2z2524766413168640y9z21314534666240000y6z212373762321800000z3+682176021898628000y3z+163552851034668000RootOf_Z2+_Z+5y3z+38444953961075000RootOf_Z2+_Z+5xz7560832848058368y10107487335683180800y7307559853657459000y322027797731340000y2+84698873079075000xz670150659686400y9z+31476478240152000y3z2+841574249783608500y3RootOf_Z2+_Z+5+48514014178143750,159225750378064800y4+14850000yz13032000xz2+78382080y6z205141248y92779336800y6+92534400RootOf_Z2+_Z+580919000z2+40326912RootOf_Z2+_Z+5y951710400RootOf_Z2+_Z+5y6460252800RootOf_Z2+_Z+5y4+42460200RootOf_Z2+_Z+5z2+10425600RootOf_Z2+_Z+5y3z23596400RootOf_Z2+_Z+5xz2+121150080RootOf_Z2+_Z+5y6z39096000RootOf_Z2+_Z+5yz2853557750z+238838625x+22477500y+3396141950RootOf_Z2+_Z+5z+1702428300RootOf_Z2+_Z+5x2617839000RootOf_Z2+_Z+5y246564000y3z+1331445600RootOf_Z2+_Z+5y3z+42460200RootOf_Z2+_Z+5xz7894611000y380919000xz3960000y3z2+579121000yx1130633900y3RootOf_Z2+_Z+5,896RootOf_Z2+_Z+5y6736y680RootOf_Z2+_Z+5y3z4860y3RootOf_Z2+_Z+52240y3z540RootOf_Z2+_Z+5xz+900y31440RootOf_Z2+_Z+5x+300RootOf_Z2+_Z+5y2880RootOf_Z2+_Z+5z+7610x2+100xz960RootOf_Z2+_Z+56075x+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

 


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