Ask Your Question
1

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

asked 2020-09-04 06:52:30 +0200

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2020-09-04 10:30:55 +0200

torres gravatar image

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.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 239 times

Last updated: Sep 04 '20