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.

$\mathrm{with}\left(\mathrm{Groebner}\right)\:$

$\mathrm{F1}≔\left[10xz-6x^3-8y^2{z}^2\,-6z+5y^3\right]$

$\mathrm{F1}≔\left[-8y^2{z}^2-6x^3+10xz\,5y^3-6z\right]$

$\mathrm{G1}≔\mathrm{Basis}\left(\mathrm{F1}\,\mathrm{tdeg}\left(x\,y\,z\right)\right)$

$\mathrm{G1}≔\left[5y^3-6z\,4y^2{z}^2+3x^3-5xz\,15x^{3}y-25xyz+24z^3\,45x^6-96y{z}^5-150x^{4}z+125x^2{z}^2\right]$

$\mathrm{Walk}\left(\mathrm{G1}\,\mathrm{tdeg}\left(x\,y\,z\right)\,\mathrm{plex}\left(x\,y\,z\right)\right)$

$\left[5y^3-6z\,4y^2{z}^2+3x^3-5xz\right]$

$\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left(z^2+z+5\right)\right)$

$\mathrm{\alpha }$

$\mathrm{F2}≔\left[-10yx-9x^3+2z{\mathrm{\alpha }}^2-4y^3\mathrm{\alpha }\,6{\mathrm{\alpha }}^2-2x^2\mathrm{\alpha }+9x{\mathrm{\alpha }}^2-8y^{3}x\right]\:$

$\mathrm{G2}≔\mathrm{Basis}\left(\mathrm{F2}\,\mathrm{tdeg}\left(x\,y\,z\right)\right)$

$\mathrm{G2}≔\left[10yx+4y^3\mathrm{\alpha }+9x^3+\left(2\mathrm{\alpha }+10\right)z\,6\mathrm{\alpha }+30+2x^2\mathrm{\alpha }+8y^{3}x+\left(9\mathrm{\alpha }+45\right)x\,-24\mathrm{\alpha }+30-16\mathrm{\alpha }{y}^{3}z+32y^6+\left(56\mathrm{\alpha }+10\right)x^2+\left(36\mathrm{\alpha }+180\right)y^3+\left(4\mathrm{\alpha }+20\right)xz+\left(-72\mathrm{\alpha }+90\right)z+\left(-36\mathrm{\alpha }+45\right)x+60\mathrm{\alpha }y\right]$

$\mathrm{Walk}\left(\mathrm{G2}\,\mathrm{tdeg}\left(x\,y\,z\right)\,\mathrm{plex}\left(x\,y\,z\right)\right)$

$\left[9216y^{12}-4608\mathrm{\alpha }{y}^{9}z+31104\mathrm{\alpha }{y}^9+155520y^9+16640\mathrm{\alpha }{y}^7-62208\mathrm{\alpha }{y}^{6}z+293616\mathrm{\alpha }{y}^6-3200y^7+77760y^{6}z+1280\mathrm{\alpha }{y}^{4}z+724480y^6+149040\mathrm{\alpha }{y}^4-215080\mathrm{\alpha }{y}^{3}z-1600y^{4}z+670680y^3\mathrm{\alpha }-208800y^4+732600z{y}^3-4800\mathrm{\alpha }{y}^2+3960\mathrm{\alpha }yz+896\mathrm{\alpha }{z}^2+984150y^3+298890\mathrm{\alpha }y-156735\mathrm{\alpha }z+6000y^2-16200yz+880z^2+96228\mathrm{\alpha }-854550y+1676700z-393660\,-314125516800\mathrm{\alpha }{y}^9{z}^4-15975784120320\mathrm{\alpha }{y}^{10}{z}^2-5536014336000\mathrm{\alpha }{y}^9{z}^3+300987187200y^9{z}^4-546360629280768\mathrm{\alpha }{y}^{11}-32882551603200\mathrm{\alpha }{y}^{10}z-10435297443840\mathrm{\alpha }{y}^9{z}^2-322486272000\mathrm{\alpha }{y}^6{z}^5-8668550430720y^{10}{z}^2-14135648256000y^9{z}^3+1967799836731392\mathrm{\alpha }{y}^{10}+1947158001561600\mathrm{\alpha }{y}^{9}z-4917019852800\mathrm{\alpha }{y}^7{z}^3+1310100480000\mathrm{\alpha }{y}^6{z}^4-1139103470665728y^{11}-359455142707200y^{10}z-524766413168640y^9{z}^2-725594112000y^6{z}^5+27199544370884352\mathrm{\alpha }{y}^9+235447336673280\mathrm{\alpha }{y}^{8}z-14674245120000\mathrm{\alpha }{y}^7{z}^2+163796824166400\mathrm{\alpha }{y}^6{z}^3-37324800000\mathrm{\alpha }{y}^3{z}^6-7560832848058368y^{10}-670150659686400y^{9}z-39028901068800y^7{z}^3-7759825920000y^6{z}^4-7519204604620800\mathrm{\alpha }{y}^8+3675750562759680\mathrm{\alpha }{y}^{7}z+227541778560000\mathrm{\alpha }{y}^6{z}^2+66355200000\mathrm{\alpha }{y}^4{z}^4-4534963200000\mathrm{\alpha }{y}^3{z}^5+32041679675265792y^9-1409502931845120y^{8}z-42639851520000y^7{z}^2-175841686425600y^6{z}^3-37324800000y^3{z}^6+2614664021875200\mathrm{\alpha }{y}^7+16968987770878080\mathrm{\alpha }{y}^{6}z+5039700480000\mathrm{\alpha }{y}^5{z}^2-129548782080000\mathrm{\alpha }{y}^4{z}^3+21017180160000\mathrm{\alpha }{y}^3{z}^4-7353752910796800y^8+257997550049280y^{7}z-1314534666240000y^6{z}^2-213580800000y^4{z}^4-7054387200000y^3{z}^5-629856000000\mathrm{\alpha }x{z}^5+321705392979406400\mathrm{\alpha }{y}^6-1018259361792000\mathrm{\alpha }{y}^{5}z+347786987328000\mathrm{\alpha }{y}^4{z}^2+2203937994240000\mathrm{\alpha }{y}^3{z}^3+139968000000\mathrm{\alpha }y{z}^5-209952000000\mathrm{\alpha }{z}^6+46656000000x{z}^6-107487335683180800y^7+39860784187015680y^{6}z-2537233920000y^5{z}^2-380772679680000y^4{z}^3-209844224640000y^3{z}^4-18743464800000\mathrm{\alpha }x{z}^4-39416496242604800\mathrm{\alpha }{y}^5+45006197725728000\mathrm{\alpha }{y}^{4}z+18852048082512000\mathrm{\alpha }{y}^3{z}^2+4076179200000\mathrm{\alpha }{y}^2{z}^3+58320000000\mathrm{\alpha }y{z}^4-15446376000000\mathrm{\alpha }{z}^5+88088744959114400y^6-18392297260032000y^{5}z-2230302304512000y^4{z}^2-3045221256960000y^3{z}^3+139968000000y{z}^5+94478400000000\mathrm{\alpha }x{z}^3-23046304810528800\mathrm{\alpha }{y}^4+163552851034668000\mathrm{\alpha }{y}^{3}z-32611248000000\mathrm{\alpha }{y}^2{z}^2-528160248000000\mathrm{\alpha }y{z}^3-2927664000000\mathrm{\alpha }{z}^4-38688904800000x{z}^4-26046898913260800y^5-25470717458112000y^{4}z+31476478240152000y^3{z}^2+11844403200000y^2{z}^3+6298560000000y{z}^4-17937936000000z^5+5550200727030000\mathrm{\alpha }x{z}^2+841574249783608500y^3\mathrm{\alpha }-11336483045680000\mathrm{\alpha }{y}^{2}z-1020432054600000\mathrm{\alpha }y{z}^2+6063266599200000\mathrm{\alpha }{z}^3-737167716000000x{z}^3-568616554967464800y^4+682176021898628000z{y}^3+94950792000000y^2{z}^2-696965508000000y{z}^3-870738012000000z^4+38444953961075000\mathrm{\alpha }xz-104840997530040000\mathrm{\alpha }{y}^2+95020410601170000\mathrm{\alpha }yz+85139930065725000\mathrm{\alpha }{z}^2-3875300052120000x{z}^2-307559853657459000y^3-49118173405280000y^{2}z-8777828946600000z^{2}y-12373762321800000z^3+94086819258781500\mathrm{\alpha }x-200252907899415000\mathrm{\alpha }y+597219742017708750\mathrm{\alpha }z+84698873079075000xz-22027797731340000y^2-187882578562680000yz+109342506627225000z^2-17319759203700000\mathrm{\alpha }+991358206562039625x-1534072805076652500y+2118938395306196250z+48514014178143750\,40326912\mathrm{\alpha }{y}^9-205141248y^9+121150080\mathrm{\alpha }{y}^{6}z-51710400\mathrm{\alpha }{y}^6+78382080y^{6}z+10425600\mathrm{\alpha }{y}^3{z}^2-2779336800y^6-460252800\mathrm{\alpha }{y}^4+1331445600\mathrm{\alpha }{y}^{3}z-3960000y^3{z}^2-3596400\mathrm{\alpha }x{z}^2-1130633900y^3\mathrm{\alpha }-378064800y^4-246564000z{y}^3+42460200\mathrm{\alpha }xz-39096000\mathrm{\alpha }yz+42460200\mathrm{\alpha }{z}^2-13032000x{z}^2-7894611000y^3+1702428300\mathrm{\alpha }x-2617839000\mathrm{\alpha }y+3396141950\mathrm{\alpha }z+579121000yx-80919000xz+14850000yz-80919000z^2+92534400\mathrm{\alpha }+238838625x+22477500y-2853557750z+159225750\,-896\mathrm{\alpha }{y}^6-736y^6-80\mathrm{\alpha }{y}^{3}z-4860y^3\mathrm{\alpha }-2240z{y}^3-540\mathrm{\alpha }xz+900y^3-1440\mathrm{\alpha }x+300\mathrm{\alpha }y-2880\mathrm{\alpha }z+7610x^2+100xz-960\mathrm{\alpha }-6075x+8400y-12150z-4050\right]$

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.