Singular
https://www.singular.uni-kl.de/forum/

degBound & std
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1960
Page 1 of 1

Author:  John Perry [ Mon Aug 22, 2011 5:21 pm ]
Post subject:  degBound & std

Suppose I set degBound = 7 & then call std(I) to compute the Gröbner basis of a homogeneous ideal. I end up with the truncated Gröbner basis up to degree 7.

Now suppose I want the higher degree, and raise degBound = 9, then call std(I) again.

Will Singular know not to recompute the S-polynomials of degree <= 7 in this case?

Edit: Oops, "code" didn't do what I expected.

Author:  ederc [ Tue Aug 23, 2011 10:47 am ]
Post subject:  Re: degBound & std

Hi John,

Singular will not use the information stored in the first computation as both computations are independent of each other and Singular does not check whether one is helpful for the other or not.
But why don't you just compute the new standard basis starting with the one computed up to degree 7?

Code:
ideal i = ...;
degBound = 7;
ideal g7 = std(i);
degBound = 10;
ideal g10 = std(g7);
...


In this way at least a part of the already done computations are taken into account and nearly all s-polynomials of degree <=7 should be rejected due to criteria not consuming too much computational time. Having done some tests the benefit in computational time is evident.

Best regards,
Chris

Author:  Guest [ Wed Aug 24, 2011 11:34 am ]
Post subject:  Re: degBound & std

Hi Chris,

Actually I'm not so interested in using this; it's a matter of curiosity to me. The question was prompted by a conversation at Sage Days 32. Someone said that a "dirty trick" is to compute, cache, and use a basis (non-Gröbner probably) up to degree d for a system. In Sage, caching such a result raises the issue of later computing the actual basis, and someone (either Simon King or Volker Braun) pointed out the same as you did just now. I can dig up the trac ticket if you'd like to read that conversation (I may have described it slightly inaccurately, but you get the idea.)

Of course, it would be even more efficient not to re-consider the S-polynomials already considered. For an inhomogeneous ideal that's almost certainly impractical, but for a homogeneous ideal it would be relatively easy***; basically a field recording that s-polynomials have been computed up to a certain degree. That got me curious: does Singular do anything at all with it? I don't know if it's worth the trouble to do this in code; I was just curious.

I hope that gives you some context for the question. You've answered it, so I'm happy. :D

john

*** Almost as easy as implementing good linear algebra! :roll: :wink:

Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/