Back to Forum | View unanswered posts | View active topics



Post new topic Reply to topic  Page 1 of 1
  [ 3 posts ] 
  Print view | E-mail friend Previous topic | Next topic 
Author Message
Guest
 Post subject: Groebner basis computation efficiency
PostPosted: Thu Mar 10, 2022 4:34 am 
Hi. I have the following ideal, which turns out to be the maximal ideal generated by all the variables. Magma can compute a Groebner basis in a few seconds, while in Singular, "std(I)" seems to take forever. Is there a trick that one can use to speed up the computation, or is Magma using voodoo magic? Thanks!

Code:
ring R = 0,(x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28),dp;
ideal I = -x6*x9+x5*x10-x8*x11+x7*x12,-2*x1*x10-x2*x11-x2*x12+x3*x12,x3*x9+2*x0*x10+x4*x10-2*x6,-x3*x10-x8*x10+x0*x11+x0*x12+x6*x12-x3-x7-x8,-x1*x9+x2*x10-x0*x12+x2+x4+x8,-x7*x9-x1*x10+x5*x11-x3,x7*x10-x4*x11-x6*x11-x10,-x7*x9+x5*x11-x2*x12+2*x1+x9,x4*x9+x6*x9-x5*x10+x2-x12,x2*x10+x2-x3+x11,-x6*x13+x5*x14-x8*x15+x7*x16,-2*x1*x14-x2*x15-x2*x16+x3*x16+2*x6,x3*x13+2*x0*x14+x4*x14,-x3*x14-x8*x14+x0*x15+x0*x16+x6*x16+x4,-x1*x13+x2*x14-x0*x16+x5,-x7*x13-x1*x14+x5*x15-x2+x6,x7*x14-x4*x15-x6*x15-x3-x14,-x7*x13+x5*x15-x2*x16-2*x0-x4+x13,x4*x13+x6*x13-x5*x14-x16,x2*x14+x15,-x6*x17+x5*x18-x8*x19+x7*x20,-2*x1*x18-x2*x19-x2*x20+x3*x20+x3+x7+x8,x3*x17+2*x0*x18+x4*x18-x4,-x3*x18-x8*x18+x0*x19+x0*x20+x6*x20,-x1*x17+x2*x18-x0*x20-x0-x6,-x7*x17-x1*x18+x5*x19+x1,x7*x18-x4*x19-x6*x19-x18,-x7*x17+x5*x19-x2*x20+x3+x8+x17,x4*x17+x6*x17-x5*x18-x0-x20,x2*x18-x0-x6+x19,-x6*x21+x5*x22-x8*x23+x7*x24,-2*x1*x22-x2*x23-x2*x24+x3*x24-x2-x4-x8,x3*x21+2*x0*x22+x4*x22-x5,-x3*x22-x8*x22+x0*x23+x0*x24+x6*x24+x0+x6,-x1*x21+x2*x22-x0*x24,-x7*x21-x1*x22+x5*x23+x0,x7*x22-x4*x23-x6*x23+x1-x22,-x7*x21+x5*x23-x2*x24-x2+x21,x4*x21+x6*x21-x5*x22-x24,x2*x22+x0+x23,-x6*x25+x5*x26-x8*x27+x7*x28,-2*x1*x26-x2*x27-x2*x28+x3*x28+x3,x3*x25+2*x0*x26+x4*x26+x2-x6,-x3*x26-x8*x26+x0*x27+x0*x28+x6*x28-x1,-x1*x25+x2*x26-x0*x28-x0,-x7*x25-x1*x26+x5*x27,x7*x26-x4*x27-x6*x27+x7-x26,-x7*x25+x5*x27-x2*x28+x1+x25,x4*x25+x6*x25-x5*x26-x5-x28,x2*x26+x27;


Report this post
Top
  
Reply with quote  
hannes
 Post subject: Re: Groebner basis computation efficiency
PostPosted: Fri Mar 18, 2022 4:01 pm 

Joined: Wed May 25, 2005 4:16 pm
Posts: 275
Groebner bases algorithms use ops lot of heuristics: heuristics are often good strategies,
but fails sometime horribly.
To solve your example one may choose the following approach:
- compute a GB in characteristic p1_, ...p_n with slimgb
- lift the results via chinese reamider theorem
- check the result to be a GB and to contain all initial generators
https://www.singular.uni-kl.de/ft ... /modgb.lib
provides this:
Code:
LIB"modgb.lib";
ring r=0,....
ideal I=....
ideal J=modGB("slimgb",I,0);


Report this post
Top
 Profile  
Reply with quote  
Guest
 Post subject: Re: Groebner basis computation efficiency
PostPosted: Mon Mar 21, 2022 11:25 am 
Thank you, that's very helpful! Indeed over finite fields the computation is a lot faster.

I have another question. For my example say, I can guess before hand that my ideal is the maximal ideal, is there an easy way to test this?

More precisely, I guess that at the last step of the modular method, one only needs to test one inclusion, since the other one is automatic by the GB computation. But what about an arbitrary set of generators? (x0,...,x28 in my example)


Report this post
Top
  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 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:53 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group