Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Difficult set of equations for groebner
PostPosted: Thu Mar 08, 2012 4:02 pm 

Joined: Thu Mar 08, 2012 6:14 am
Posts: 6
I have a set of equations that all must be equal to zero. Due to Hilbert's Nullstellensatz, a solution is guaranteed to exist and, furthermore, if I set one of the variables in these equations equal to zero the surprisingly simple groebner basis is calculated almost instantly. The problem is that, if I do not set this variable equal to zero the process maxes out 8GB of RAM after running for about 24 hours.

The file which I load as "3degcmc/S" is located on pastebin. I cannot post the URL due to a board restriction, but it is ID 3xg0Qn85 (if you append that to the normal pastebin URL you should find it).

Code:
> LIB "poly.lib";
> option(redSB);
> <"3degcmc/S";
> I = simplify(I,1);
> ideal J = substitute(I,a17,0);
> ideal GBJ = groebner(J);
> GBJ;
GBJ[1]=a20
GBJ[2]=a19
GBJ[3]=a18
GBJ[4]=a15
GBJ[5]=a13-a16
GBJ[6]=a12-a16
GBJ[7]=a7-a10
GBJ[8]=a6-a10
GBJ[9]=a4-a9
GBJ[10]=a3-a9-1
> ideal GBI = groebner(I);


The polynomial equations are generated by an iterative process, and I can generate as many as I wish (I do this using Mathematica, I would be happy to post the code if you would like). I know that, if I make a17=0, only the first 20 equations of I are needed to compute the Groebner Basis that you see above. Is there some property that the equations hold (when I do not substitute a17=0) which explains why the Groebner Basis becomes so much more difficult to compute?

I was thinking of renting some time on an Amazon EC2 server with 64GB of RAM to see if it would compute if I gave it more time. Would this be worthwhile?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Sat Mar 10, 2012 7:28 pm 
Hi,

so I tried it on a machine with 64GB Ram using the modStd() command and it finished in 1380 seconds. So modStd() computes does the computations modular w.r.t. different prime numbers and then lifts the result back to the rationals.

Christian


Report this post
Top
  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Mon Mar 12, 2012 10:58 am 

Joined: Sun Feb 28, 2010 10:32 am
Posts: 7
Hi,

just a short update. I have also started the usual std() computation on your example on a bigger compute server here in Kaiserslautern. It is still running after 40 hours, consuming more than 14 GB RAM right now.

It seems that your set of equations is quite a good example for the benefits of modular computations, could you provide the script generating these sets of examples? It would be helpful to scale our tests on it a bit.

Christian


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Mon Mar 12, 2012 4:42 pm 

Joined: Thu Mar 08, 2012 6:14 am
Posts: 6
Sure thing. I actually generated the equations in Mathematica, not Singular (I would be interested if someone could translate their generation to Singular). The method is based on the work in this paper:
h_ttp://arxiv_org/abs/1002.0174

(remove the underlines from the url)

As you can see, the paper uses two cases to prove the result. The first case assumes that the principal curvatures are 0 and 1, and this corresponds to the set of equations I provided substituting a17=0. Without substituting a17=0, we remove this assumption with the hope of obviating the need for the second case. Here is the mathematica file:
h_ttp://www_mediafire_com/?df4qrd4dy37y1v2

The set of equations in "q" is the set which succumb to modStd() quite easily. On my machine it didn't take more than 100mb of RAM to compute these with this method (thanks for the tip!). You can extend the calculation of these equations by adjusting the line "iterate[22222]" to, say, "iterate[222222]". I normally saved the variable from Mathematica to a file, which I then imported to Singular.

Can I ask, in general, how do you approach computing a groebner basis? What I mean is, how did you come to realize that using modStd would provide a result quickly and with a small amount of RAM? I assume most of it is just based on experience, but is there a list of procedures I should try on a set of equations in general?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Tue Mar 13, 2012 2:12 pm 

Joined: Sun Feb 28, 2010 10:32 am
Posts: 7
Thank you for the generating code.

Well, the modular methods of modStd computing modulo some prime numbers help to keep the coefficients small. So std is much slower in this computation (still running) and consumes much more memory due to the fact that the coefficients of the polynomials over the rationals are not bounded.

Christian


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Tue Mar 13, 2012 3:37 pm 

Joined: Thu Mar 08, 2012 6:14 am
Posts: 6
The basis returned from modStd, even with option(redSB), contains 61 elements. When I import these equations into Mathematica and run the standard Buchberger algorithm on them via the GroebnerBasis command they reduce to just 16 equations. I went back to Singular and ran the "groebner" command on the 61 element basis, but it did not make any simplifications. Any reason why?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Tue Mar 13, 2012 9:16 pm 

Joined: Thu Mar 08, 2012 6:14 am
Posts: 6
I figured out the reason why - I was running the GroebnerBasis command without specifying the variable ordering, so Mathematica picked the ordering of the variables which matched the order in which they were encountered, which happened to be convenient.


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Tue Mar 13, 2012 11:03 pm 

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 108
Location: Germany, Münster
But does this really answer your question?

Groebnerbases depend on the order of the variables and the term order.
Experiments, not the documentation, show that Mathematica returns
a lexicographical Groebnerbasis.
So recalculate your basis w.r.t. lp ordering.

Inital computations in lp ordering are often very hard
but recalculations from dp are easier.
Code:
> ring R = 0,(a3,a4,a6,a7,a9,a10,a12,a13,a15,a16,a17,a18,a19,a20),dp;
> ideal I = ...;
> ideal J = modStd(I);
> ring Rlp = 0,(a3,a4,a6,a7,a9,a10,a12,a13,a15,a16,a17,a18,a19,a20),lp;
> ideal J = imap(R,J);
> option(redSB);
> std(J);

I guess, this will yield the same result with 16 entries as Mathematica does.


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Sat Mar 17, 2012 6:33 pm 

Joined: Thu Mar 08, 2012 6:14 am
Posts: 6
Yes, it was also due to the lp ordering, thanks for explaining.

Does anyone have any tips on deciding which algorithm to apply? I have tried modStd on a few other difficult sets of polynomials and it has not been as successful as the original set I posted. What is the typical approach to try and compute a groebner basis?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Difficult set of equations for groebner
PostPosted: Sun Mar 18, 2012 7:03 pm 

Joined: Sun Feb 28, 2010 10:32 am
Posts: 7
Hi,

you should have a look at http://www.singular.uni-kl.de/Manual/3-1-4/sing_749.htm#SEC801, there different approaches for computing Groebner bases in Singular are explained. Moreover, we are working on some other Groebner basis algorithms which are based on signatures. This work is still experimental, but I could check your examples with them if you can provide us with your example code.

Best regards,
Christian


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 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