Ask Your Question
1

Groebner basis computation extremely slow

asked 2025-06-30 07:49:54 +0200

Cynthia gravatar image

updated 2025-07-01 20:40:55 +0200

I wanted to compute the elimination ideal of some ideal. When I call elimination_ideal, it is unacceptably slow (+10 min), and when I tried to first compute the Groebner basis by hand then extract the elimination ideal, it is also very slow (+10 min).

Not sure what's wrong:

R2.<q10, q11, q12, q13, q14, q20, q21, q22, q23, q24, p,p0, p1, p2, p3, p4> = PolynomialRing(QQ,order = 'lex(11),lex(5)')
R2.inject_variables()
M1=Matrix([[q10,q11/4,q12/6,q13/4],[q11/4,q12/6,q13/4,q14]])
M2=Matrix([[q20,q21/4,q22/6,q23/4],[q21/4,q22/6,q23/4,q24]])
I1=R2.ideal(M1.minors(2))+R2.ideal(q10+q11+q12+q13+q14-1)
I2=R2.ideal(M2.minors(2))+R2.ideal(q20+q21+q22+q23+q24-1)
graph_ideal=[p0-p*q10-(1-p)*q20, p1-p*q11 - (1-p)*q21, p2-p*q12-(1-p)*q22, p3-p*q13-(1-p)*q23,p4-p*q14-(1-p)*q24]
J=I1+I2+R2.ideal(graph_ideal)
Jgb=J.groebner_basis()

Then my computer just froze there for a good 10-ish min. I tried to switch different backends (libsingular:std, linsingular:slimgb, macaulay:gb), and they both just stop right there.

I want to know if it is something I did wrong, or it is just a very hard example to compute. If it is the latter situation, is there any way to allow GPU acceleration or just multi-threading in this situation?

As a reference, I also tried this computation with the following code on Macaulay2, and it seems to handle it with ease:

R2 = QQ[q10,q11,q12,q13,q14, q20,q21,q22,q23,q24, p,p0,p1,p2,p3,p4, MonomialOrder => Eliminate 11];
M1 = matrix{{q10, q11/4, q12/6, q13/4},{q11/4, q12/6, q13/4, q14}};
I1 = ideal(q10 + q11 + q12 + q13 + q14 -1) + minors(2, M1);
M2 = matrix{{q20, q21/4, q22/6, q23/4},{q21/4, q22/6, q23/4, q24}};
I2 = ideal(q20 + q21 + q22 + q23 + q24 -1) + minors(2, M2);
I3 = ideal(p0 - p*q10 - (1-p)*q20,p1 - p*q11 - (1-p)*q21,p2 - p*q12 - (1-p)*q22,p3 - p*q13 - (1-p)*q23,p4 - p*q14 - (1-p)*q24);
J = I1 + I2 + I3;
gens gb J
edit retag flag offensive close merge delete

Comments

Could you please add the equivalent Macaulay2 code that works faster?

rburing gravatar imagerburing ( 2025-07-01 14:22:31 +0200 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2025-07-01 19:16:04 +0200

Max Alekseyev gravatar image

lex order is typically slow when it comes to Groebner basis computation. Changing order = 'lex(11),lex(5)' to order = 'degrevlex(11),degrevlex(5)' makes your code complete within a few seconds.

PS. Perhaps, in Macaulay2 computation you also used some graded order, but if it were lexicographic one, it'd helpful to see the actual code.

edit flag offensive delete link more

Comments

In Macaulay2 I just used an elimination order flag provided by M2, not exactly the product order with two lex...

Cynthia gravatar imageCynthia ( 2025-07-01 19:24:37 +0200 )edit

Sage supports weighted orders as well.

Max Alekseyev gravatar imageMax Alekseyev ( 2025-07-01 20:38:56 +0200 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2025-06-30 07:49:54 +0200

Seen: 67 times

Last updated: Jul 01