Ask Your Question

Revision history [back]

Quick (trivial) Groebner basis but too long lift of one

I have two (equivalent) sub-systems of polynomial equations of 10 variables and 12 equations, linked with one extra equations (so a total of 20 variable and 25 equations).

I can very quicky compute the Groebner basis of each sub-system. Then I can put them together, with the extra equation, and then I can quicky get the Groebner basis of the full system, which turns out to be trivial (total computation time: less than 3 minutes). See all the details in Appendix.

A direct computation of the Groebner basis of the full system is too long (I stopped after 1 day). The problem is that I need to compute the lift of 1 of the original full system (i.e. express 1 as a linear combination (with polynomial coefficients) of the original generators, by using the lift command list(R.one().lift(Id))), but it is also too long...

Now I expect that the application of a strategy involving the two sub-systems (as above) should exist to quickly get the lift of 1, but how?

I tried to compute this lift in two times, using the Groebner basis of the sub-systems, but it is also too long...


Appendix

First sub-system (10 variables and 12 equations)

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6>=PolynomialRing(QQ,10)
sage: A1=[u0 + 7/5*u1 + 7/5*u2 - 4/125,
....:   5*v0 + 5*v1 + 7*v3 + 7*v5 + 1/5,
....:   25*v0^2 + 25*v1^2 + 35*v3^2 + 35*v5^2 - 4/5,
....:   5*v0^3 + 5*v1^3 + 7*v3^3 + 7*v5^3 - v0^2 + 1/125,
....:   5*v0*v1^2 + 5*v1*v2^2 + 7*v3*v4^2 + 7*v5*v6^2 + 1/125,
....:   5*u0*v1 - v1^2 + 7*u1*v3 + 7*u2*v5 + 1/125,
....:   5*v1 + 5*v2 + 7*v4 + 7*v6 + 1/5,
....:   25*v0*v1 + 25*v1*v2 + 35*v3*v4 + 35*v5*v6 + 1/5,
....:   5*v0^2*v1 + 5*v1^2*v2 + 7*v3^2*v4 + 7*v5^2*v6 - v1^2 + 1/125,
....:   25*v1^2 + 25*v2^2 + 35*v4^2 + 35*v6^2 - 4/5,
....:   5*v1^3 + 5*v2^3 + 7*v4^3 + 7*v6^3 - u0 + 1/125,
....:   5*u0*v2 - v2^2 + 7*u1*v4 + 7*u2*v6 + 1/125]
sage: Id=R.ideal(A1)
sage: %time G1=Id.groebner_basis()
CPU times: user 1.33 s, sys: 0 ns, total: 1.33 s
Wall time: 1.33 s
sage: C1=[g for g in G1]

Second (equivalent) sub-system:

sage: R.<y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,10)
sage: A2=[y0 + 7/5*y1 + 7/5*y2 - 4/125,
....:   5*z0 + 5*z1 + 7*z3 + 7*z5 + 1/5,
....:   25*z0^2 + 25*z1^2 + 35*z3^2 + 35*z5^2 - 4/5,
....:   5*z0^3 + 5*z1^3 + 7*z3^3 + 7*z5^3 - y0 + 1/125,
....:   5*y0*z0 - z0^2 + 7*y1*z3 + 7*y2*z5 + 1/125,
....:   5*z0*z1^2 + 5*z1*z2^2 + 7*z3*z4^2 + 7*z5*z6^2 - z1^2 + 1/125,
....:   5*z1 + 5*z2 + 7*z4 + 7*z6 + 1/5,
....:   25*z0*z1 + 25*z1*z2 + 35*z3*z4 + 35*z5*z6 + 1/5,
....:   5*z0^2*z1 + 5*z1^2*z2 + 7*z3^2*z4 + 7*z5^2*z6 + 1/125,
....:   5*y0*z1 - z1^2 + 7*y1*z4 + 7*y2*z6 + 1/125,
....:   25*z1^2 + 25*z2^2 + 35*z4^2 + 35*z6^2 - 4/5,
....:   5*z1^3 + 5*z2^3 + 7*z4^3 + 7*z6^3 - z2^2 + 1/125]
sage: Id=R.ideal(A2)
sage: %time G2=Id.groebner_basis()
CPU times: user 2.08 s, sys: 0 ns, total: 2.08 s
Wall time: 2.08 s
sage: C2=[g for g in G2]

The full system:

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6, y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,20)
sage: C=C1+C2+[5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125]        # the last one is the extra one
sage: Id=R.ideal(C)
sage: %time G=Id.groebner_basis()
CPU times: user 2min 29s, sys: 16 ms, total: 2min 29s
Wall time: 2min 29s
sage: G
[1]

Quick (trivial) Groebner basis but too long lift of one

I have two (equivalent) sub-systems of polynomial equations of 10 variables and 12 equations, linked with one extra equations (so a total of 20 variable and 25 equations).

I can very quicky compute the Groebner basis of each sub-system. Then I can put them together, with the extra equation, and then I can quicky get the Groebner basis of the full system, which turns out to be trivial (total computation time: less than 3 minutes). See all the details in Appendix.

A direct computation of the Groebner basis of the full system is too long (I stopped after 1 day). The problem is that I need to compute the lift of 1 of the original full system (i.e. express 1 as a linear combination (with polynomial coefficients) of the original generators, by using the lift command list(R.one().lift(Id))), but it is also too long...

Now I expect that the application of a strategy involving the two sub-systems (as above) should exist to quickly get the lift of 1, but how?

I tried to compute this lift in two times, using the Groebner basis of the sub-systems, but it is also too long...


Appendix

First sub-system (10 variables and 12 equations)

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6>=PolynomialRing(QQ,10)
sage: A1=[u0 + 7/5*u1 + 7/5*u2 - 4/125,
....:   5*v0 + 5*v1 + 7*v3 + 7*v5 + 1/5,
....:   25*v0^2 + 25*v1^2 + 35*v3^2 + 35*v5^2 - 4/5,
....:   5*v0^3 + 5*v1^3 + 7*v3^3 + 7*v5^3 - v0^2 + 1/125,
....:   5*v0*v1^2 + 5*v1*v2^2 + 7*v3*v4^2 + 7*v5*v6^2 + 1/125,
....:   5*u0*v1 - v1^2 + 7*u1*v3 + 7*u2*v5 + 1/125,
....:   5*v1 + 5*v2 + 7*v4 + 7*v6 + 1/5,
....:   25*v0*v1 + 25*v1*v2 + 35*v3*v4 + 35*v5*v6 + 1/5,
....:   5*v0^2*v1 + 5*v1^2*v2 + 7*v3^2*v4 + 7*v5^2*v6 - v1^2 + 1/125,
....:   25*v1^2 + 25*v2^2 + 35*v4^2 + 35*v6^2 - 4/5,
....:   5*v1^3 + 5*v2^3 + 7*v4^3 + 7*v6^3 - u0 + 1/125,
....:   5*u0*v2 - v2^2 + 7*u1*v4 + 7*u2*v6 + 1/125]
sage: Id=R.ideal(A1)
sage: %time G1=Id.groebner_basis()
CPU times: user 1.33 s, sys: 0 ns, total: 1.33 s
Wall time: 1.33 s
sage: C1=[g for g in G1]

Second (equivalent) sub-system:

sage: R.<y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,10)
sage: A2=[y0 + 7/5*y1 + 7/5*y2 - 4/125,
....:   5*z0 + 5*z1 + 7*z3 + 7*z5 + 1/5,
....:   25*z0^2 + 25*z1^2 + 35*z3^2 + 35*z5^2 - 4/5,
....:   5*z0^3 + 5*z1^3 + 7*z3^3 + 7*z5^3 - y0 + 1/125,
....:   5*y0*z0 - z0^2 + 7*y1*z3 + 7*y2*z5 + 1/125,
....:   5*z0*z1^2 + 5*z1*z2^2 + 7*z3*z4^2 + 7*z5*z6^2 - z1^2 + 1/125,
....:   5*z1 + 5*z2 + 7*z4 + 7*z6 + 1/5,
....:   25*z0*z1 + 25*z1*z2 + 35*z3*z4 + 35*z5*z6 + 1/5,
....:   5*z0^2*z1 + 5*z1^2*z2 + 7*z3^2*z4 + 7*z5^2*z6 + 1/125,
....:   5*y0*z1 - z1^2 + 7*y1*z4 + 7*y2*z6 + 1/125,
....:   25*z1^2 + 25*z2^2 + 35*z4^2 + 35*z6^2 - 4/5,
....:   5*z1^3 + 5*z2^3 + 7*z4^3 + 7*z6^3 - z2^2 + 1/125]
sage: Id=R.ideal(A2)
sage: %time G2=Id.groebner_basis()
CPU times: user 2.08 s, sys: 0 ns, total: 2.08 s
Wall time: 2.08 s
sage: C2=[g for g in G2]

The full system:

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6, y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,20)
sage: C=C1+C2+[5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125]   # the last one is the extra one
sage: Id=R.ideal(C)
sage: %time G=Id.groebner_basis()
CPU times: user 2min 29s, sys: 16 ms, total: 2min 29s
Wall time: 2min 29s
sage: G
[1]

Quick (trivial) Groebner basis but too long lift of one

I have two (equivalent) sub-systems of polynomial equations of 10 variables and 12 equations, linked with one extra equations (so a total of 20 variable and 25 equations).

I can very quicky compute the Groebner basis of each sub-system. Then I can put them together, with the extra equation, and then I can quicky get the Groebner basis of the full system, which turns out to be trivial (total computation time: less than 3 minutes). See all the details in Appendix.

A direct computation of the Groebner basis of the full system is too long (I stopped after 1 day). The problem is that I need to compute the lift of 1 of the original full system (i.e. express 1 as a linear combination (with polynomial coefficients) of the original generators, by using the lift command list(R.one().lift(Id))), but it is also too long...

Now I expect that the application of a strategy involving the two sub-systems (as above) should exist to quickly get the lift of 1, but how?

I tried to compute this lift in two times, using the Groebner basis of the sub-systems, but it is also too long...


Appendix

First sub-system (10 variables and 12 equations)

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6>=PolynomialRing(QQ,10)
R.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6>=PolynomialRing(QQ,10)
sage: A1=[u0 + 7/5*u1 + 7/5*u2 - 4/125,
....:   5*v0 + 5*v1 + 7*v3 + 7*v5 + 1/5,
....:   25*v0^2 + 25*v1^2 + 35*v3^2 + 35*v5^2 - 4/5,
....:   5*v0^3 + 5*v1^3 + 7*v3^3 + 7*v5^3 - v0^2 + 1/125,
....:   5*v0*v1^2 + 5*v1*v2^2 + 7*v3*v4^2 + 7*v5*v6^2 + 1/125,
....:   5*u0*v1 - v1^2 + 7*u1*v3 + 7*u2*v5 + 1/125,
....:   5*v1 + 5*v2 + 7*v4 + 7*v6 + 1/5,
....:   25*v0*v1 + 25*v1*v2 + 35*v3*v4 + 35*v5*v6 + 1/5,
....:   5*v0^2*v1 + 5*v1^2*v2 + 7*v3^2*v4 + 7*v5^2*v6 - v1^2 + 1/125,
....:   25*v1^2 + 25*v2^2 + 35*v4^2 + 35*v6^2 - 4/5,
....:   5*v1^3 + 5*v2^3 + 7*v4^3 + 7*v6^3 - u0 + 1/125,
....:   5*u0*v2 - v2^2 + 7*u1*v4 + 7*u2*v6 + 1/125]
sage: Id=R.ideal(A1)
sage: %time G1=Id.groebner_basis()
CPU times: user 1.33 s, sys: 0 ns, total: 1.33 s
Wall time: 1.33 s
sage: C1=[g for g in G1]

Second (equivalent) sub-system:

sage: R.<y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,10)
R.<y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(QQ,10)
sage: A2=[y0 + 7/5*y1 + 7/5*y2 - 4/125,
....:   5*z0 + 5*z1 + 7*z3 + 7*z5 + 1/5,
....:   25*z0^2 + 25*z1^2 + 35*z3^2 + 35*z5^2 - 4/5,
....:   5*z0^3 + 5*z1^3 + 7*z3^3 + 7*z5^3 - y0 + 1/125,
....:   5*y0*z0 - z0^2 + 7*y1*z3 + 7*y2*z5 + 1/125,
....:   5*z0*z1^2 + 5*z1*z2^2 + 7*z3*z4^2 + 7*z5*z6^2 - z1^2 + 1/125,
....:   5*z1 + 5*z2 + 7*z4 + 7*z6 + 1/5,
....:   25*z0*z1 + 25*z1*z2 + 35*z3*z4 + 35*z5*z6 + 1/5,
....:   5*z0^2*z1 + 5*z1^2*z2 + 7*z3^2*z4 + 7*z5^2*z6 + 1/125,
....:   5*y0*z1 - z1^2 + 7*y1*z4 + 7*y2*z6 + 1/125,
....:   25*z1^2 + 25*z2^2 + 35*z4^2 + 35*z6^2 - 4/5,
....:   5*z1^3 + 5*z2^3 + 7*z4^3 + 7*z6^3 - z2^2 + 1/125]
sage: Id=R.ideal(A2)
sage: %time G2=Id.groebner_basis()
CPU times: user 2.08 s, sys: 0 ns, total: 2.08 s
Wall time: 2.08 s
sage: C2=[g for g in G2]

The full system:

sage: R.<u0, u1, u2, v0, v1, v2, v3, v4, v5, v6, y0, y1, y2, z0, z1, z2, z3, z4, z5, z6>=PolynomialRing(QQ,20)
R.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6,y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(QQ,20)
sage: C=C1+C2+[5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125]  # the last one is the extra one
sage: Id=R.ideal(C)
sage: %time G=Id.groebner_basis()
CPU times: user 2min 29s, sys: 16 ms, total: 2min 29s
Wall time: 2min 29s
sage: G
[1]