Difficult set of equations for groebner

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).



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?

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

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

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?

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

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?

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.

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.

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

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?

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