Can we avoid to fall back to very slow toy implementation in the computation of Groebner basis under a finite field of large characteristic?

asked 2021-06-11 13:27:23 +0200

updated 2021-06-16 12:48:41 +0200

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 15 ms, sys: 16 ms, total: 31 ms
Wall time: 28.3 ms
[v0 + 357913941, v1 - 357913941]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
CPU times: user 125 ms, sys: 219 ms, total: 344 ms
Wall time: 3.09 s
[v0 + 357913943, v1 + 1789569716]

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?


Below is the code for function (it is a toy example):

def function(p):
    F=GF(p)
    R.<v0, v1>=PolynomialRing(F,2)
    Eq=[3*v0 + 5*v1 + 1/F(3), 
    9*v0^2 + 15*v1^2 - 2/F(3), 
    3*v0^3 + 5*v1^3 - v0^2 + 1/F(27)]
    Id=Ideal(Eq)
    G=Id.groebner_basis()
    return G
edit retag flag offensive close merge delete

Comments

The limitation is probably due to Singular having that limitation. Maybe try CoCoA.

rburing gravatar imagerburing ( 2021-06-11 23:00:15 +0200 )edit

Could you please provide the code of function ?

tmonteil gravatar imagetmonteil ( 2021-06-15 15:33:34 +0200 )edit