2
$\begingroup$

I've been calculating some Gröbner bases in preparation for finding non-commutative Hilbert series (and, once I recreate that, characters of group actions). Specifically, I've been using the letterplace implementation, which I believe calculates to degree $d$ the Gröbner basis for an ideal in the non-commutative free algebra with $n$ generators by passing to something in a commutative ring with $nd$ generators.

In the two cases I've worked with, I can get to degree $5$ with a $9$-generator algebra or to degree $4$ with a $12$-generator algebra; doing one degree higher has led to exceeding the 24GB (8GB RAM + 16GB swap) of the Linux machine with the most memory I can access. This suggests that I can get somewhere in the 40s in terms of number of variables but not the 50s. How hopeless is the growth in memory access for this algorithm; would trying to jerry-rig in a different algorithm for the commutative algebra part be worthwhile?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ For this sort of things, I think it is better to work experimentally ("profile, don't speculate" as the motto goes): try to find toy versions of your problem with different complexities, and see how the memory taken (or total final number of terms) increases with the parameters. (I also use this approach to try to find the most efficient term order, when there is choice and it's not obvious beforehand.) $\endgroup$
    – Gro-Tsen
    Sep 19, 2017 at 7:21

1 Answer 1

Reset to default
2
$\begingroup$

You want to make sure that you are using an implementation of Faugere's F4/F5. You also want to make sure that you are using a good variable ordering. GB is amazingly sensitive to that, and the known heuristics are not that good. So you really have to experiment.

Another thing to consider is: do you really need a full Groebner basis? If your ideal is not radical, the difference between computing the GB of the radical and the full basis can be enormous.

You should also consider what field to compute in. Could you get lots of useful information (approximation?) out of a GB computed over $\mathbb{Z}_p$ for example?

Lastly, you should examine the solutions you get for smaller cases. If they contain symmetries, you should figure out how to do a change of variables to factor that out. In the work I did with GB (but based on much older algorithms), that cut the time down from 1 hour to 4 seconds.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I could get useful information out of finite fields, probably. How much faster is that usually? Also the rings I'm working with have lots of symmetries and I think the letterplace correspondence gives even more in the actual ring being computed. How do you factor those out? $\endgroup$
    – W. Cadegan-Schlieper
    Sep 20, 2017 at 7:20
  • $\begingroup$ It depends on the size of the coefficients that appear in all intermediate computations. These are frequently huge, even for small output. [There are proofs that this is essentially inevitable]. So it often helps. But there are cases where the term # growth is even faster, and that becomes the stumbling block. $\endgroup$
    – Jacques Carette
    Sep 20, 2017 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.