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 3 years ago

updated 3 years ago

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

If p<231 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>231 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<263)?


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
Preview: (hide)

Comments

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

rburing gravatar imagerburing ( 3 years ago )

Could you please provide the code of function ?

tmonteil gravatar imagetmonteil ( 3 years ago )