minimal Grobner basis

[Vanessa Bava]

Hello!

I've to compute a Minimal Grobner basis for I. 

Is mingens gb ideal the correct comamnd?

Thanks to everyone!

[Douglas Leonard]

gens gb I

---

From: maca...@googlegroups.com [maca...@googlegroups.com] on behalf of Vanessa Bava [vaness...@gmail.com]
Sent: Tuesday, February 11, 2014 4:02 AM
To: maca...@googlegroups.com
Subject: [Macaulay2] minimal Grobner basis

--
You received this message because you are subscribed to the Google Groups "Macaulay2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaulay2+...@googlegroups.com.
To post to this group, send email to maca...@googlegroups.com.
Visit this group at http://groups.google.com/group/macaulay2.
For more options, visit https://groups.google.com/groups/opt_out.

[Michael Stillman]

Hi Vanessa,

gb I 

returns an internal object from which one can access a number of aspects of the Groebner basis.

gens gb I  — gives you a matrix whose columns are the elements of the Groebner basis.  This is a minimal Groebner basis, whenever it can be.

groebnerBasis I — same thing as ‘gens gb I’.

mingens gb I

If I is homogeneous (in a positively graded ring), this returns a matrix whose columns form a minimal generating set.  

If I is NOT homogeneous, or if it is, but in a non-positively graded ring, then it returns some subset of the Groebner basis which is known to generate.  It attempts to be as minimal as possible, but sometimes fails quite badly at that.  This is what both ‘trim I’ as well as ‘mingens I’ return.

Probably, ‘mingens’ should complain in the cases when it is not returning an actual minimal generating set, but at this point, that might be hard to change (it might break too much code).

Best,

Mike

[Douglas Leonard]

Mike--

So I guess I should not be surprised that the first small example (below)
that I tried using mingens is pretty bad, as it returns the input when a gens gb returns a smaller set.

----------------------------------------------------------------------------------------------------------------
R=QQ[x,y]
I=ideal(x^3*y-x, x*y^3-y, x^2*y^2-y)
mingens gb I
gens gb I
----------------------------------------------------------------------------------------------------------------
I rely on
      gens gb
as column reduction of matrices over a polynomial ring,
usually together with MonomialOrder=>{Position=>Up}.
----------------------------------------------------------------------------------------------------------------
(And again, to beat a dead horse unmercifully,
Position=>Up should be a module ordering option,
not part of a ring monomial ordering;
as I might wish to compare several module ordering results over the same polynomial ring
without changing the ring monomial order.)

Doug

---

From: maca...@googlegroups.com [maca...@googlegroups.com] on behalf of Michael Stillman [mikest...@gmail.com]
Sent: Tuesday, February 11, 2014 10:41 AM
To: maca...@googlegroups.com
Subject: Re: [Macaulay2] minimal Grobner basis

[Vanessa Bava]

Thank you both!!!!!!!!

[Paul Zinn-Justin]

Maybe I should create a new thread rather than reopening a dead one, but I'm still confused about the exact same issue, gens vs mingens. Let me provide an even simpler example than Doug's:

R=QQ[x]; P=ideal(x^2+1,x^3-2);

P==R

-- output is: true, as should be. so P=ideal(1_R), but trim P doesn't see it. let's investigate...

g=gb (P, StopWithMinimalGenerators=>true, Syzygies=>false, ChangeMatrix=>false);

-- copy/pasted from the code of trim

mingens g

-- output is   | x+2 x^2 +1 |, same as what trim P would produce

gens g

-- output is   | 1 |

Can anyone explain to me the difference in this case?

--

[Douglas Leonard]

gens gb I

computes a minimal Gr\"obner basis
----------------------------------------------------------------------------------------------------
mingens I

seems to try to find a minimal set of generators, which has nothing to do with a Gr\"obner basis
(and doesn't find a minimum set of generators).
------------------------------------------------------------------------------------------------------
[There are reasons to think that a quick and dirty attempt at finding a small set of generators
could speed up the computation of a Gr\"obner basis using a signature-based algorithm.
Maybe there are other reasons to look for a small set of generators. But again, don't confuse
a minimal set of generators with a minimal Gr\"obner basis, just because both have the word minimal in them.]

Doug

---

From: maca...@googlegroups.com [maca...@googlegroups.com] on behalf of Paul Zinn-Justin [pzinn...@gmail.com]
Sent: Monday, February 24, 2014 6:56 PM
To: maca...@googlegroups.com
Subject: Re: [Macaulay2] Re: minimal Grobner basis

[Paul Zinn-Justin]

I see, thanks. independently of Grobner basis considerations, I still wish trim / mingens would do a better job. e.g. in QQ[x]

trim ideal(x^2-1,x)

gives

ideal(1,x)

why, oh why? couldn't it at least get rid of generators which are obviously generated by others?

[Michael Stillman]

The ‘trim’ function (and unfortunately, also ‘mingens’) in the inhomogeneous case doesn’t always do a good job, as you have noted.  What it is currently doing is while M2 computes a Groebner basis, it keeps track of which of the original generators doesn’t immediately reduce to 0.  In the homogeneous case, the way it does this is guaranteed to give a minimal generating set.  But in the inhomogeneous case, it doesn’t look to see if the GB is simpler (especially if the GB is much simpler than the original generating set).  It should do this.  However, in the inhomogeneous case, remember that there is no decent notion of minimal generating set.

Perhaps M2 should also perhaps spend more computation time to try to find a better (smaller) generating set?

I do wish that ‘mingens’ could give an error in the inhomogeneous case, as this has tripped up a number of people.  It might be too late to change that functionality though, as it might break too much existing code.

The intent of ‘mingens’ (and ‘trim’) is what Doug said: It will find a minimal set of generators in the homogeneous case, and it tries (sometimes with poor results) to find a smaller generating set in the inhomogeneous case (BUT: with no guarantee!).  It is not related with minimal Groebner bases.

— Mike