Walk - Maple Help

Groebner

 Walk
 convert Groebner bases from one ordering to another

 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

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $\mathrm{F1}≔\left[10xz-6{x}^{3}-8{y}^{2}{z}^{2},-6z+5{y}^{3}\right]$
 ${\mathrm{F1}}{≔}\left[{-}{8}{}{{y}}^{{2}}{}{{z}}^{{2}}{-}{6}{}{{x}}^{{3}}{+}{10}{}{x}{}{z}{,}{5}{}{{y}}^{{3}}{-}{6}{}{z}\right]$ (1)
 > $\mathrm{G1}≔\mathrm{Basis}\left(\mathrm{F1},\mathrm{tdeg}\left(x,y,z\right)\right)$
 ${\mathrm{G1}}{≔}\left[{5}{}{{y}}^{{3}}{-}{6}{}{z}{,}{4}{}{{y}}^{{2}}{}{{z}}^{{2}}{+}{3}{}{{x}}^{{3}}{-}{5}{}{x}{}{z}{,}{15}{}{{x}}^{{3}}{}{y}{-}{25}{}{x}{}{y}{}{z}{+}{24}{}{{z}}^{{3}}{,}{45}{}{{x}}^{{6}}{-}{96}{}{y}{}{{z}}^{{5}}{-}{150}{}{{x}}^{{4}}{}{z}{+}{125}{}{{x}}^{{2}}{}{{z}}^{{2}}\right]$ (2)
 > $\mathrm{Walk}\left(\mathrm{G1},\mathrm{tdeg}\left(x,y,z\right),\mathrm{plex}\left(x,y,z\right)\right)$
 $\left[{5}{}{{y}}^{{3}}{-}{6}{}{z}{,}{4}{}{{y}}^{{2}}{}{{z}}^{{2}}{+}{3}{}{{x}}^{{3}}{-}{5}{}{x}{}{z}\right]$ (3)
 > $\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left({z}^{2}+z+5\right)\right)$
 ${\mathrm{\alpha }}$ (4)
 > $\mathrm{F2}≔\left[-10yx-9{x}^{3}+2z{\mathrm{\alpha }}^{2}-4{y}^{3}\mathrm{\alpha },6{\mathrm{\alpha }}^{2}-2{x}^{2}\mathrm{\alpha }+9x{\mathrm{\alpha }}^{2}-8{y}^{3}x\right]:$
 > $\mathrm{G2}≔\mathrm{Basis}\left(\mathrm{F2},\mathrm{tdeg}\left(x,y,z\right)\right)$
 ${\mathrm{G2}}{≔}\left[{10}{}{y}{}{x}{+}\left({2}{}{\mathrm{\alpha }}{+}{10}\right){}{z}{+}{9}{}{{x}}^{{3}}{+}{4}{}{{y}}^{{3}}{}{\mathrm{\alpha }}{,}{6}{}{\mathrm{\alpha }}{+}{30}{+}{2}{}{{x}}^{{2}}{}{\mathrm{\alpha }}{+}{8}{}{{y}}^{{3}}{}{x}{+}\left({9}{}{\mathrm{\alpha }}{+}{45}\right){}{x}{,}{-}{24}{}{\mathrm{\alpha }}{+}{30}{+}{32}{}{{y}}^{{6}}{+}\left({56}{}{\mathrm{\alpha }}{+}{10}\right){}{{x}}^{{2}}{-}{16}{}{\mathrm{\alpha }}{}{{y}}^{{3}}{}{z}{+}\left({-}{72}{}{\mathrm{\alpha }}{+}{90}\right){}{z}{+}\left({-}{36}{}{\mathrm{\alpha }}{+}{45}\right){}{x}{+}{60}{}{\mathrm{\alpha }}{}{y}{+}\left({36}{}{\mathrm{\alpha }}{+}{180}\right){}{{y}}^{{3}}{+}\left({4}{}{\mathrm{\alpha }}{+}{20}\right){}{x}{}{z}\right]$ (5)
 > $\mathrm{Walk}\left(\mathrm{G2},\mathrm{tdeg}\left(x,y,z\right),\mathrm{plex}\left(x,y,z\right)\right)$
 $\left[{9216}{}{{y}}^{{12}}{-}{4608}{}{\mathrm{\alpha }}{}{{y}}^{{9}}{}{z}{+}{31104}{}{\mathrm{\alpha }}{}{{y}}^{{9}}{+}{155520}{}{{y}}^{{9}}{+}{16640}{}{\mathrm{\alpha }}{}{{y}}^{{7}}{-}{62208}{}{\mathrm{\alpha }}{}{{y}}^{{6}}{}{z}{+}{293616}{}{\mathrm{\alpha }}{}{{y}}^{{6}}{-}{3200}{}{{y}}^{{7}}{+}{77760}{}{{y}}^{{6}}{}{z}{+}{1280}{}{\mathrm{\alpha }}{}{{y}}^{{4}}{}{z}{+}{724480}{}{{y}}^{{6}}{+}{149040}{}{\mathrm{\alpha }}{}{{y}}^{{4}}{-}{215080}{}{\mathrm{\alpha }}{}{{y}}^{{3}}{}{z}{-}{1600}{}{{y}}^{{4}}{}{z}{+}{670680}{}{{y}}^{{3}}{}{\mathrm{\alpha }}{-}{208800}{}{{y}}^{{4}}{+}{732600}{}{z}{}{{y}}^{{3}}{-}{4800}{}{\mathrm{\alpha }}{}{{y}}^{{2}}{+}{3960}{}{\mathrm{\alpha }}{}{y}{}{z}{+}{896}{}{\mathrm{\alpha }}{}{{z}}^{{2}}{+}{984150}{}{{y}}^{{3}}{+}{298890}{}{\mathrm{\alpha }}{}{y}{-}{156735}{}{\mathrm{\alpha }}{}{z}{+}{6000}{}{{y}}^{{2}}{-}{16200}{}{y}{}{z}{+}{880}{}{{z}}^{{2}}{+}{96228}{}{\mathrm{\alpha }}{-}{854550}{}{y}{+}{1676700}{}{z}{-}{393660}{,}{-}{314125516800}{}{\mathrm{\alpha }}{}{{y}}^{{9}}{}{{z}}^{{4}}{-}{15975784120320}{}{\mathrm{\alpha }}{}{{y}}^{{10}}{}{{z}}^{{2}}{-}{5536014336000}{}{\mathrm{\alpha }}{}{{y}}^{{9}}{}{{z}}^{{3}}{+}{300987187200}{}{{y}}^{{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}}{-}{8668550430720}{}{{y}}^{{10}}{}{{z}}^{{2}}{-}{14135648256000}{}{{y}}^{{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}}{-}{1139103470665728}{}{{y}}^{{11}}{-}{359455142707200}{}{{y}}^{{10}}{}{z}{-}{524766413168640}{}{{y}}^{{9}}{}{{z}}^{{2}}{-}{725594112000}{}{{y}}^{{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}}{-}{7560832848058368}{}{{y}}^{{10}}{-}{670150659686400}{}{{y}}^{{9}}{}{z}{-}{39028901068800}{}{{y}}^{{7}}{}{{z}}^{{3}}{-}{7759825920000}{}{{y}}^{{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}}{+}{32041679675265792}{}{{y}}^{{9}}{-}{1409502931845120}{}{{y}}^{{8}}{}{z}{-}{42639851520000}{}{{y}}^{{7}}{}{{z}}^{{2}}{-}{175841686425600}{}{{y}}^{{6}}{}{{z}}^{{3}}{-}{37324800000}{}{{y}}^{{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}}{-}{7353752910796800}{}{{y}}^{{8}}{+}{257997550049280}{}{{y}}^{{7}}{}{z}{-}{1314534666240000}{}{{y}}^{{6}}{}{{z}}^{{2}}{-}{213580800000}{}{{y}}^{{4}}{}{{z}}^{{4}}{-}{7054387200000}{}{{y}}^{{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}}{+}{46656000000}{}{x}{}{{z}}^{{6}}{-}{107487335683180800}{}{{y}}^{{7}}{+}{39860784187015680}{}{{y}}^{{6}}{}{z}{-}{2537233920000}{}{{y}}^{{5}}{}{{z}}^{{2}}{-}{380772679680000}{}{{y}}^{{4}}{}{{z}}^{{3}}{-}{209844224640000}{}{{y}}^{{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}}{+}{88088744959114400}{}{{y}}^{{6}}{-}{18392297260032000}{}{{y}}^{{5}}{}{z}{-}{2230302304512000}{}{{y}}^{{4}}{}{{z}}^{{2}}{-}{3045221256960000}{}{{y}}^{{3}}{}{{z}}^{{3}}{+}{139968000000}{}{y}{}{{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}}{-}{38688904800000}{}{x}{}{{z}}^{{4}}{-}{26046898913260800}{}{{y}}^{{5}}{-}{25470717458112000}{}{{y}}^{{4}}{}{z}{+}{31476478240152000}{}{{y}}^{{3}}{}{{z}}^{{2}}{+}{11844403200000}{}{{y}}^{{2}}{}{{z}}^{{3}}{+}{6298560000000}{}{y}{}{{z}}^{{4}}{-}{17937936000000}{}{{z}}^{{5}}{+}{5550200727030000}{}{\mathrm{\alpha }}{}{x}{}{{z}}^{{2}}{+}{841574249783608500}{}{{y}}^{{3}}{}{\mathrm{\alpha }}{-}{11336483045680000}{}{\mathrm{\alpha }}{}{{y}}^{{2}}{}{z}{-}{1020432054600000}{}{\mathrm{\alpha }}{}{y}{}{{z}}^{{2}}{+}{6063266599200000}{}{\mathrm{\alpha }}{}{{z}}^{{3}}{-}{737167716000000}{}{x}{}{{z}}^{{3}}{-}{568616554967464800}{}{{y}}^{{4}}{+}{682176021898628000}{}{z}{}{{y}}^{{3}}{+}{94950792000000}{}{{y}}^{{2}}{}{{z}}^{{2}}{-}{696965508000000}{}{y}{}{{z}}^{{3}}{-}{870738012000000}{}{{z}}^{{4}}{+}{38444953961075000}{}{\mathrm{\alpha }}{}{x}{}{z}{-}{104840997530040000}{}{\mathrm{\alpha }}{}{{y}}^{{2}}{+}{95020410601170000}{}{\mathrm{\alpha }}{}{y}{}{z}{+}{85139930065725000}{}{\mathrm{\alpha }}{}{{z}}^{{2}}{-}{3875300052120000}{}{x}{}{{z}}^{{2}}{-}{307559853657459000}{}{{y}}^{{3}}{-}{49118173405280000}{}{{y}}^{{2}}{}{z}{-}{8777828946600000}{}{{z}}^{{2}}{}{y}{-}{12373762321800000}{}{{z}}^{{3}}{+}{94086819258781500}{}{\mathrm{\alpha }}{}{x}{-}{200252907899415000}{}{\mathrm{\alpha }}{}{y}{+}{597219742017708750}{}{\mathrm{\alpha }}{}{z}{+}{84698873079075000}{}{x}{}{z}{-}{22027797731340000}{}{{y}}^{{2}}{-}{187882578562680000}{}{y}{}{z}{+}{109342506627225000}{}{{z}}^{{2}}{-}{17319759203700000}{}{\mathrm{\alpha }}{+}{991358206562039625}{}{x}{-}{1534072805076652500}{}{y}{+}{2118938395306196250}{}{z}{+}{48514014178143750}{,}{40326912}{}{\mathrm{\alpha }}{}{{y}}^{{9}}{-}{205141248}{}{{y}}^{{9}}{+}{121150080}{}{\mathrm{\alpha }}{}{{y}}^{{6}}{}{z}{-}{51710400}{}{\mathrm{\alpha }}{}{{y}}^{{6}}{+}{78382080}{}{{y}}^{{6}}{}{z}{+}{10425600}{}{\mathrm{\alpha }}{}{{y}}^{{3}}{}{{z}}^{{2}}{-}{2779336800}{}{{y}}^{{6}}{-}{460252800}{}{\mathrm{\alpha }}{}{{y}}^{{4}}{+}{1331445600}{}{\mathrm{\alpha }}{}{{y}}^{{3}}{}{z}{-}{3960000}{}{{y}}^{{3}}{}{{z}}^{{2}}{-}{3596400}{}{\mathrm{\alpha }}{}{x}{}{{z}}^{{2}}{-}{1130633900}{}{{y}}^{{3}}{}{\mathrm{\alpha }}{-}{378064800}{}{{y}}^{{4}}{-}{246564000}{}{z}{}{{y}}^{{3}}{+}{42460200}{}{\mathrm{\alpha }}{}{x}{}{z}{-}{39096000}{}{\mathrm{\alpha }}{}{y}{}{z}{+}{42460200}{}{\mathrm{\alpha }}{}{{z}}^{{2}}{-}{13032000}{}{x}{}{{z}}^{{2}}{-}{7894611000}{}{{y}}^{{3}}{+}{1702428300}{}{\mathrm{\alpha }}{}{x}{-}{2617839000}{}{\mathrm{\alpha }}{}{y}{+}{3396141950}{}{\mathrm{\alpha }}{}{z}{+}{579121000}{}{y}{}{x}{-}{80919000}{}{x}{}{z}{+}{14850000}{}{y}{}{z}{-}{80919000}{}{{z}}^{{2}}{+}{92534400}{}{\mathrm{\alpha }}{+}{238838625}{}{x}{+}{22477500}{}{y}{-}{2853557750}{}{z}{+}{159225750}{,}{-}{896}{}{\mathrm{\alpha }}{}{{y}}^{{6}}{-}{736}{}{{y}}^{{6}}{-}{80}{}{\mathrm{\alpha }}{}{{y}}^{{3}}{}{z}{-}{4860}{}{{y}}^{{3}}{}{\mathrm{\alpha }}{-}{2240}{}{z}{}{{y}}^{{3}}{-}{540}{}{\mathrm{\alpha }}{}{x}{}{z}{+}{900}{}{{y}}^{{3}}{-}{1440}{}{\mathrm{\alpha }}{}{x}{+}{300}{}{\mathrm{\alpha }}{}{y}{-}{2880}{}{\mathrm{\alpha }}{}{z}{+}{7610}{}{{x}}^{{2}}{+}{100}{}{x}{}{z}{-}{960}{}{\mathrm{\alpha }}{-}{6075}{}{x}{+}{8400}{}{y}{-}{12150}{}{z}{-}{4050}\right]$ (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.