Groebner - Maple Programming Help

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

Groebner

 SuggestVariableOrder
 choose a good variable order

 Calling Sequence SuggestVariableOrder(J, X)

Parameters

 J - a list or set of polynomials or a PolynomialIdeal X - (optional) a list or set of variables

Description

 • SuggestVariableOrder attempts to choose heuristically good variable orderings that should result in faster Groebner basis computations for both plex and tdeg orders. In practice, this is one of the most important considerations for performance, since a bad variable ordering can make an otherwise simple problem infeasible. The set of variables can be explicitly specified by an optional second argument.
 • The heuristics used are based on the degree of the polynomials in each respective variable and on the size of the coefficients.  They do not always produce an optimal order, but they should rarely select a bad order.
 • SuggestVariableOrder is called by Groebner[Basis] when the second argument is a name and no appropriate basis is known.

Examples

Our first example is a problem of Trinks'.  We compute a total degree Groebner basis without specifying an order.  Groebner[Basis] calls SuggestVariableOrder automatically.

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $\mathrm{trinks}≔\left[-9w+15pt+20zs,99w-11sb+3{b}^{2},wp+2zt-11{b}^{3},45p+35s-165b-36,35p+40z+25t-27s,15w+25ps+30z-18t-165{b}^{2}\right]:$
 > $G≔{\mathrm{Groebner}}_{\mathrm{Basis}}\left(\mathrm{trinks},'\mathrm{tord}',\mathrm{order}=\mathrm{tdeg}\right):$
 > $\mathrm{tord}$
 ${\mathrm{tdeg}}{}\left({w}{,}{z}{,}{t}{,}{p}{,}{s}{,}{b}\right)$ (1)

Next we compare lexicographic bases for the order suggested, its reverse, and a random permutation of $\left\{b,p,s,t,w,z\right\}$.

 > $V≔\mathrm{SuggestVariableOrder}\left(\mathrm{trinks}\right)$
 ${V}{≔}{w}{,}{z}{,}{t}{,}{p}{,}{s}{,}{b}$ (2)
 > $G≔{\mathrm{Groebner}}_{\mathrm{Basis}}\left(\mathrm{trinks},\mathrm{plex}\left(V\right)\right):$
 > $\mathrm{length}\left(G\right)$
 ${4208}$ (3)
 > $\mathrm{map}\left(\mathrm{length}@\mathrm{maxnorm},G\right)$
 $\left[{21}{,}{66}{,}{68}{,}{67}{,}{67}{,}{65}\right]$ (4)
 > $\mathrm{V2}≔\mathrm{seq}\left({V}_{-i},i=1..6\right)$
 ${\mathrm{V2}}{≔}{b}{,}{s}{,}{p}{,}{t}{,}{z}{,}{w}$ (5)
 > $\mathrm{G2}≔{\mathrm{Groebner}}_{\mathrm{Basis}}\left(\mathrm{trinks},\mathrm{plex}\left(\mathrm{V2}\right)\right):$
 > $\mathrm{length}\left(\mathrm{G2}\right)$
 ${9262}$ (6)
 > $\mathrm{map}\left(\mathrm{length}@\mathrm{maxnorm},\mathrm{G2}\right)$
 $\left[{40}{,}{158}{,}{161}{,}{161}{,}{159}{,}{158}\right]$ (7)
 > $\mathrm{V3}≔\mathrm{op}\left({\mathrm{combinat}}_{\mathrm{randperm}}\left(\left[V\right]\right)\right)$
 ${\mathrm{V3}}{≔}{t}{,}{p}{,}{s}{,}{b}{,}{w}{,}{z}$ (8)
 > $\mathrm{G3}≔{\mathrm{Groebner}}_{\mathrm{Basis}}\left(\mathrm{trinks},\mathrm{plex}\left(\mathrm{V3}\right)\right):$
 > $\mathrm{length}\left(\mathrm{G3}\right)$
 ${9125}$ (9)
 > $\mathrm{map}\left(\mathrm{length}@\mathrm{maxnorm},\mathrm{G3}\right)$
 $\left[{33}{,}{151}{,}{152}{,}{154}{,}{154}{,}{155}\right]$ (10)