# Too long to compute the Groebner basis of a not so big system

Consider the following polynomial system:

sage: R.<a, di, p, q, v0, v1, v2, v3, v4, v5>=PolynomialRing(QQ,order='invlex')
sage: Eq
[q^7 - 1,
-q + p^2,
a*p - 1,
7*di^2 + 7*di - 1,
v0^2 + di - 1/7,
v1*v6 - 1/7*a,
v2*v5 - 1/7*a^4,
v3*v4 - 1/7*a^9,
v3*v4 - 1/7*a^2,
v2*v5 - 1/7*a^11,
-1/7*a^8 + v1*v6,
1/7*p^11*v2*v5 + 1/7*p^9*v3*v4 + 1/7*p^8*v1*v6 + 1/7*p^4*v2*v5 + 1/7*p^2*v3*v4 - v0^3 + 1/7*p*v1*v6 + 1/7*v0^2 - di,
1/7*p^11*q^2*v3*v5 + 1/7*p^9*q^4*v3*v5 + 1/7*p^8*q*v2*v6 + 1/7*p^4*q^5*v2*v6 + 1/7*p*q^6*v0*v1 + 1/7*p^2*q^3*v4^2 - v0*v1*v6 + 1/7*v0*v1,
1/7*p^11*q^4*v4*v5 + 1/7*p^9*q*v3*v6 + 1/7*p^8*q^2*v3*v6 + 1/7*p^2*q^6*v4*v5 + 1/7*p^4*q^3*v0*v2 + 1/7*p*q^5*v1^2 - v0*v2*v5 + 1/7*v0*v2,
1/7*p^11*q^6*v5^2 + 1/7*p^9*q^5*v0*v3 + 1/7*p^8*q^3*v4*v6 + 1/7*p^4*q*v1*v2 + 1/7*p*q^4*v1*v2 + 1/7*p^2*q^2*v4*v6 - v0*v3*v4 + 1/7*v0*v3,
1/7*p^11*q*v5*v6 + 1/7*p^8*q^4*v5*v6 + 1/7*p^9*q^2*v1*v3 + 1/7*p^4*q^6*v2^2 + 1/7*p^2*q^5*v0*v4 + 1/7*p*q^3*v1*v3 - v0*v3*v4 + 1/7*v0*v4,
1/7*p^9*q^6*v2*v3 + 1/7*p^11*q^3*v0*v5 + 1/7*p^8*q^5*v6^2 + 1/7*p^4*q^4*v2*v3 + 1/7*p^2*q*v1*v4 + 1/7*p*q^2*v1*v4 - v0*v2*v5 + 1/7*v0*v5,
1/7*p^11*q^5*v1*v5 + 1/7*p^8*q^6*v0*v6 + 1/7*p^9*q^3*v3^2 + 1/7*p^4*q^2*v2*v4 + 1/7*p^2*q^4*v2*v4 + 1/7*p*q*v1*v5 - v0*v1*v6 + 1/7*v0*v6]
sage: Id=Ideal(Eq)


Then it required one week to compute its Groebner basis:

sage: L=list(Id.groebner_basis())
sage: L
[v5 + v1 + 1/2*a^3*di - 1/2*a^2*di + 1/2*a*di + di - 1/6*a^3 + 1/6*a^2 + 1/3*a + 1/6,
v4 - a^2*v1 - a*v1 - a^2*di - 1/6*a^3 - 1/2*a^2 - 1/6*a,
v3 + 1/6*a^3 + 1/3*a^2 - 1/3*a - 1/6,
v2 + a^2*v1 + a*v1 + 1/2*a^3*di + 1/2*a^2*di + 1/2*a*di + 1/6*a^3 + 1/6*a,
v1^2 + 1/2*a^3*di*v1 - 1/2*a^2*di*v1 + 1/2*a*di*v1 + di*v1 - 1/6*a^3*v1 + 1/6*a^2*v1 + 1/3*a*v1 + 1/6*v1 + 1/6*a,
v0 + di,
q + a^2 - 1,
p + a^3 - a,
di^2 + di - 1/6,
a^4 - a^2 + 1]


whereas the system looks not so big.

Question: Why is it so long? Is there a way to make the computation much quicker?

edit retag close merge delete

Sort by » oldest newest most voted

Consider that there are many algorithms to compute a Groebner Base in Sage (by default you use std but there is also slimgb, etc...), and the efficiency of each one can differ by the monomial ordering you choose for your ring (in your case invlex): my suggestion is to try different combination of them, to see at least an improvement.

more