Ask Your Question

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

1 Answer

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Stats

Asked: 2020-09-04 06:52:30 +0100

Seen: 227 times

Last updated: Sep 04 '20