giac limits number of variables in Gröbner basis calc

[Brent W. Baccala]

Hi -

I don't think giac can handle more than 15 variables in a Gröbner basis calculation.

This limitation isn't really documented anywhere, but if you look in giac's src/cocoa.cc around lines 490-500, function swap_indices and think about it a few minutes, you'll see that it can't handle more than 15 variables, I think.  I'm looking at giac 1.9.0.

I tried a calculation on a ring with 67 variables and the algorithm went into an infinite loop because it couldn't compare monomial exponents properly.  It produced a polynomial with two terms, both with the same monomial (different coefficients), and that triggered the infinite loop in the reduction code.

I hope somebody working with this code will check my work and verify that giac is so limited.  If so, we should add a check to the groebner_basis routine in src/sage/libs/giac/__init__.py

    agape

    brent

[Dima Pasechnik]

Thanks. Filed as https://github.com/sagemath/sage/issues/35744

Best,
Dima
>
> agape
> brent
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/83301b12-14ff-44e1-a0f6-33021050161bn%40googlegroups.com.

[parisse]

There is code for up to 64 variables. I'm not sure for more. Can you send your input? That way I can check with gdb.

[Brent W. Baccala]

I'll attach my script.  It's 26 KB and uses 67 variables.

I'm just suggesting checking the number of variables (whatever it is) at the beginning and returning an error message, rather than me checking with gdb, which I've already done!

    agape

    brent

[parisse]

I eventually checked. You are requesting a lexicographic Groebner basis, but since it's much slower than reverse lex. ordering, Giac tries first revlex ordering, because if the ideal is 0 dimensional it would call FGLM. The revlex basis computation is fast (about 2 seconds on my PC) but the ideal is not 0 dimensional. Then we are back to lex ordering for 806 generators, 67 variables, and total degree of the generators varying from 2 to 4.

Running with export GIAC_DEBUG=2 gives some insightfull informations. There is indeed a bug inside the lexicographic ordering routine. This ordering bug is now fixed.

https://github.com/geogebra/giac/commit/12e1d788c2452ffea1ee22e63fc4b0a250f2fb4a

Of course there might be other bugs, since nobody really tried lex ordering with such a large number of variables, but it's hard to know, I stopped the computation in a reduction of a polynomial with 15327 monomials over a list of 76 polynomials (including some with more than 10 000 monomials). Unless there are simplifications (which I doubt since the first element of the revlex basis has 842 terms), I would not be surprised to see that the lex computation would take years or more (moreover, it's done using plain Buchberger, not F4...)

BTW, I also checked, there is no limit on the number of variables, for large number of variables, the monomials are dynamically allocated. There is a limit on the total degree: it should not be larger than 2^14.

I don't want to add a general limit on the number of variables, as it works here for revlex. Maybe it would make sense for lex ordering, but where ?