Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Question: weight matrices and MonomialOrder for GroebnerBasis

• To: mathgroup at smc.vnet.net
• Subject: [mg50374] Re: [mg50358] Question: weight matrices and MonomialOrder for GroebnerBasis
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 31 Aug 2004 06:28:55 -0400 (EDT)
• References: <200408290754.DAA29972@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Robert Knighten wrote:
> An option for specifying the MonomialOrder in GroebnerBasis is to provide an
> explicit weight matrix.  But I do not understand the syntax for doing this.
> Are there examples of this available.  In addition I would like to see a
> weight matrix for some of the standard monomial orderings.
> 
> Thank you for any help.
> 
> -- Bob

What is required for n variables is an nxn rational (can be integers) 
matrix of full rank that comprises a well-founded term ordering. This in 
turn is fullfilled iff first nonzero entry in each column is positive.

Here is an example from a set of problems posed as a challenge for the 
ISSAC 1997 conference.

polys = {8*w^2 + 5*w*x - 4*w*y + 2*w*z + 3*w + 5*x^2 + 2*x*y -
     7*x*z - 7*x + 7*y^2 - 8*y*z - 7*y + 7*z^2 - 8*z + 8
   3*w^2 - 5*w*x - 3*w*y - 6*w*z + 9*w + 4*x^2 + 2*x*y -
     2*x*z + 7*x + 9*y^2 + 6*y*z + 5*y + 7*z^2 + 7*z + 5,
   -2*w^2 + 9*w*x + 9*w*y - 7*w*z - 4*w + 8*x^2 + 9*x*y - 3*x*z +
     8*x + 6*y^2 - 7*y*z + 4*y - 6*z^2 + 8*z + 2,
   7*w^2 + 5*w*x + 3*w*y - 5*w*z - 5*w + 2*x^2 + 9*x*y - 7*x*z +
     4*x - 4*y^2 - 5*y*z + 6*y - 4*z^2 - 9*z + 2};

vars = {x, y, z, w};

For lexicographic you can use, say an identity matrix.

gbl1 = GroebnerBasis[polys, vars];
gbl2 = GroebnerBasis[polys, vars, MonomialOrder->IdentityMatrix[4]];

In[24]:= gbl1 === gbl2
Out[24]= True

For degree reversee lexicographic ordering one can use a matrix with 
first row set to all ones, next row all zeros except last entry negative 
one, then move the negative one a step to the left in successive rows.

gbdrl1 = GroebnerBasis[polys, vars,
   MonomialOrder->DegreeReverseLexicographic];
drlmat4 = {{1,1,1,1},{0,0,0,-1},{0,0,-1,0},{0,-1,0,0}};
gbdrl2 = GroebnerBasis[polys, vars, MonomialOrder->drlmat4];

In[31]:= gbdrl1 === gbdrl2
Out[31]= True


Daniel Lichtblau
Wolfram Research

• References:
  • Question: weight matrices and MonomialOrder for GroebnerBasis
    • From: Robert Knighten <Robert@Knighten.org>