Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: degBound & std
PostPosted: Mon Aug 22, 2011 5:21 pm 

Joined: Fri Oct 17, 2008 11:22 pm
Posts: 7
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.


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: degBound & std
PostPosted: Tue Aug 23, 2011 10:47 am 
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


Report this post
Top
  
Reply with quote  
 Post subject: Re: degBound & std
PostPosted: Wed Aug 24, 2011 11:34 am 
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:


Report this post
Top
  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Fri May 13, 2022 10:56 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group