21
$\begingroup$

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?

Any answers, comments and reference are appreciated.

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ Macaulay2 is what people use most of the time for Groebner basis computations. $\endgroup$
    – Per Alexandersson
    Commented Sep 20, 2014 at 8:19
  • 6
    $\begingroup$ In my experience, Mathematica is particularly not fast at doing this. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Sep 20, 2014 at 8:44
  • 1
    $\begingroup$ You may try sage. I believe it uses Singular for the computation, though is more user friendly. $\endgroup$
    – joro
    Commented Sep 20, 2014 at 9:31
  • 5
    $\begingroup$ arguably the fastest Groebner bases implementations are www-salsa.lip6.fr/~jcf/Software $\endgroup$
    – Dima Pasechnik
    Commented Sep 20, 2014 at 13:02
  • $\begingroup$ Faugère's web page (Dima Pasechnik's recommendation) has moved to www-polsys.lip6.fr/~jcf $\endgroup$
    – Brent Baccala
    Commented Apr 5, 2023 at 15:59

5 Answers 5

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Could you elaborate on how exactly one can introduce a polynomial equation which encodes that a variable can never be zero? $\endgroup$
    – Kagaratsch
    Commented Nov 10, 2015 at 0:20
  • 1
    $\begingroup$ @DavidE.Roberson see here: math.stackexchange.com/questions/1521748/… $\endgroup$
    – Kagaratsch
    Commented Aug 23, 2016 at 7:21
  • 6
    $\begingroup$ @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. $\endgroup$
    – Jacques Carette
    Commented Sep 26, 2017 at 0:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jacques Carette
    Commented Oct 6, 2017 at 12:10
  • 1
    $\begingroup$ Oh, sorry. See en.wikipedia.org/wiki/… $\endgroup$
    – Jacques Carette
    Commented Oct 6, 2017 at 16:33
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

I have been trying to answer that question myself for some time and haven't found anything definitive in the literature. I can only point to the paper where M4GB is presented where there are some benchmarks comparing its performance against OpenF4, Magma, and FGb (Faugere algorithm that is used in Maple) for the case of $m$ polynomials of $n$ variables with $m=2n$ and $m=n+1$. It would be a very nice resource for the community to have an independent benchmark of the different libraries similar to the Mathematical Programming community benchmark service offered by Hans Mittelmann.

Exploring a little more, I found this dicussion in the Google group for the Sage developers where there is a comparison of several codes out there to compute Groebner basis. Keep in mind that the performance depends heavily on your ideal.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .