# Fast computation of a Groebner basis - What is Possible

I need to compute a Groebner basis of 18 polynomials in 19 variables the terms of which have degree at most 3. My aim is to exploit a symmetry in a PDE problem and I am not an expert in algebra or computer algebra. Mathematica is now running for 10 days without answer.

A similar question description here was asked a couple of years ago but because there was no satisfying answer I raise this question again. I would appreciate if anyone could tell help me with the following two questions

1. if there is any hope to compute the Groebner basis?
2. if so are there fast at best parallel ready to use programms for computing the Groebner basis?

• Macaulay2 is what people use most of the time for Groebner basis computations. – Per Alexandersson Sep 20 '14 at 8:19
• In my experience, Mathematica is particularly not fast at doing this. – Mariano Suárez-Álvarez Sep 20 '14 at 8:44
• You may try sage. I believe it uses Singular for the computation, though is more user friendly. – joro Sep 20 '14 at 9:31
• arguably the fastest Groebner bases implementations are www-salsa.lip6.fr/~jcf/Software – Dima Pasechnik Sep 20 '14 at 13:02

Note that the Groebner basis engine in Maple has been Faugère's (and colleagues)'s for a few versions now. So that is as state-of-the-art as it goes.

The sizes you mention should be well in-scope of current engines if the final answer is reasonably sized, and you pick a good variable order.

Another item to consider is: do you have all the information you know coded up in your polynomials? For example, if you know that some variables are never 0, then actually adding a variable and an equation that state this fact may make the problem much easier! I have had some personal experience where computations went from days to minutes when doing this. It is really all about the structure of the answer, and not so much the raw size of the input.

I guess what I am really saying is: you need to give us a lot more information about your problem. First, the polynomials would help. [Maybe post them up on github?] Second, the actual derivation of the polynomials from your context might help even more. Thirdly, what you are actually trying to do with the answer: few people really want a Groebner basis per se, it is just a waypoint in a larger computation. But knowing what that actually is can lead to asking for a different GB-related question which might turn out to be much easier.

• Could you elaborate on how exactly one can introduce a polynomial equation which encodes that a variable can never be zero? – Kagaratsch Nov 10 '15 at 0:20
• @DavidE.Roberson see here: math.stackexchange.com/questions/1521748/… – Kagaratsch Aug 23 '16 at 7:21
• @lightweight If you know that (say) 't' is never 0, then introduce a new variable, say t_inv, and a new equation, $t t_{inv} -1 = 0$. This basically says that t_inv is 1/t. You can do this for whole expressions as well. Such inequalities then to remove "solutions at infinity" which can take a lot of computation time without contributing to the solution you want. – Jacques Carette Sep 26 '17 at 0:24
• Are you interested in ideals or in geometry? If ideals, then GBs are your only choice. If geometry, then GBs are only one tool. One 'similar' example is the recent sc-square effort (www.sc-square.org) where computing GB/CAD are overkill. – Jacques Carette Oct 6 '17 at 12:10
• Oh, sorry. See en.wikipedia.org/wiki/… – Jacques Carette Oct 6 '17 at 16:33

Symmetry may enter the process in two steps:

• Choosing which $f,g$ is best taken to construct next $S(f,g)$.
• Deciding en-masse to discard a lot of such pairs.

Both approaches where explored in finite characteristic by Faugere and his colleagues; however, he mostly dealt with the general case (where symmetries sometimes accidentally pop), if you have a specific system in mind, you can probably do better.

Moving to implementation details:

• You usually want to find generators $\mod p$, and then lift.

• Last time I had anything to do with computational algebra (years ago), the standard systems did not compress vectors in small characteristic to long registers (a plain vanilla modern x86 has eight 256 bit registers). This is messy from a programming point of view (even though modern compilers may take you some of the way - if you want an example assume every four consecutive bits are a number in $\mathbb{F}_{13}$, and you want to compute the entry by entry products of these 64 pairs of numbers), and only gives you a constant factor, but the constant factor is rather nice; cryptographers have used these tricks for years.

Sadly all these suggestions involve getting your hands dirty. Such is life I guess.

Assume for simplicity that your polynomials are homogeneous of degree three. If you have a complete intersection, it has Hilbert series $$(1-t^3)^{18}/(1-t)^{19} = (1+t+t^2)^{18}/(1-t)$$ It is conceivable that the Groebner basis is just ridiculously large (too many polynomials). After all, if you add one more linear relation, you are supposed to describe a monomial ideal of codimension $3^{18}$.

Importantly, one must be very careful with the choice of the monomial order. I am not an expert on this, but reverse lexicographic order is reputed to be "good" (experts please correct me on this).

Finally, if the polynomials don't have rational or at least algebraic coefficients, you better hope for complete intersection case, else the result is unstable.

The best choice for you is going to be highly dependent on your specific polynomials, but MAGMA used to be a lot faster than M2 or Singular (http://magma.maths.usyd.edu.au/~allan/gb/, not sure if there are any recent timings). Most likely the GB of your problem is going to be huge. What do you want to do with it? For example, if you want to find some complex solutions of polynomial equations, then you can try numerical homotopy continuation methods (softwares include Bertini, Macaulay2, PHC Pack, ...). They are highly parallelizable (unlike GB) and I think will also behave better with respect to symmetry (also unlike GB).