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 ? On Friday, June 9, 2023 at 10:26:13 PM UTC+2 Brent W. Baccala wrote:
> 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 > > > On Friday, June 9, 2023 at 6:37:44 AM UTC-4 parisse wrote: > >> 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. >> >> On Monday, June 5, 2023 at 9:19:04 PM UTC+2 Brent W. Baccala wrote: >> >>> 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 >>> >>> -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9e42aa8e-d1cb-4ef6-b438-c4fcd99fed9bn%40googlegroups.com.
