Revision history [back]
 | 1 | initial version |
You can calulate a Gröbner basis with respect to a lexicographic ordering to get an equivalent "triangular" system that can be solved back-to-front by successive solving and substitution (introducing parameters whenever there is a choice to be made).
sage: R.<a15, x13_14, a4, a11, a0, x14_15, x11_13, x5_5, x9_12, a5, a12, x3_4, a1, x7_7, x11_14, x12_15, x5_6, x4_4, x9_9, a6, a13, x3_5, a2, x10_10, x7_8, x6_6, x5_7, x12_12, x8_8, a7, x3_6, x6_7, x14_14, a9, x15_15, x4_6, x11_11, x8_9, a8, x10_12, a14, x13_13, a3, a10, x4_7, x12_14, x11_12, x13_15, x10_13> = PolynomialRing(QQ, order='invlex')
polys = [-x3_4*x9_12, -x10_12*x3_4, -x10_13*x3_4, -x11_12*x3_4, -x11_13*x3_4, -x11_14*x3_4, x3_4^2*x7_7, x7_8*x8_9, -x11_12^2*x8_8, -x12_12*x3_4 + x3_4*x4_4, -x12_14*x3_4 + x3_4*x4_6, -x12_15*x3_4 + x3_4*x4_7, -x13_13*x3_4 + x3_4*x5_5, -x13_14*x3_4 + x3_4*x5_6, -x13_15*x3_4 + x3_4*x5_7, -x14_14*x3_4 + x3_4*x6_6, -x14_15*x3_4 + x3_4*x6_7, -x15_15*x3_4*x7_8 + x3_4*x7_8, x3_4*x3_5*x7_7, x3_4*x3_6*x7_7, a0 - 1, a1 - 1, a2 - 1, a3 - 1, a4*x4_4 - 1, a5*x5_5 - 1, a6*x6_6 - 1, a7*x7_7 - 1, a8*x8_8 - 1, a9*x9_9 - 1, a10*x10_10 - 1, a11*x11_11 - 1, a12*x12_12 - 1, a13*x13_13 - 1, a14*x14_14 - 1, a15*x15_15 - 1]
sage: I = R.ideal(polys)
sage: %time G = I.groebner_basis(algorithm='libsingular:std')
CPU times: user 4.45 ms, sys: 91 µs, total: 4.55 ms
Wall time: 4.57 ms
sage: list(G)
[a15*x3_4*x7_8 - x3_4*x7_8, a15*x15_15 - 1, x13_14*x3_4 - x3_4*x5_6, a4*x3_4 - a12*x3_4, a4*x4_4 - 1, a11*x11_11 - 1, a0 - 1, x14_15*x3_4 - x3_4*x6_7, x11_13*x3_4, x5_5*a5 - 1, x5_5*x3_4 - x3_4*x13_13, x9_12*x3_4, a5*x3_4 - x3_4*a13, a12*x12_12 - 1, x3_4^2, x3_4*x11_14, x3_4*x12_15 - x3_4*x4_7, x3_4*x4_4 - x3_4*x12_12, x3_4*a6 - x3_4*a14, x3_4*x3_5, x3_4*x7_8*x15_15 - x3_4*x7_8, x3_4*x6_6 - x3_4*x14_14, x3_4*x5_7 - x3_4*x13_15, x3_4*x3_6, x3_4*x4_6 - x3_4*x12_14, x3_4*x10_12, x3_4*x11_12, x3_4*x10_13, a1 - 1, x7_7*a7 - 1, x9_9*a9 - 1, a6*x6_6 - 1, a13*x13_13 - 1, a2 - 1, x10_10*a10 - 1, x7_8*x8_9, x8_8*a8 - 1, x14_14*a14 - 1, a3 - 1, x11_12^2]
This equivalent system can be passed to solve, which then does the job faster:
sage: %time solve(list(map(SR, G)), list(map(SR, R.gens())))
CPU times: user 3.04 s, sys: 170 ms, total: 3.21 s
Wall time: 2.53 s
Different variable orderings may lead to different speeds (the monomial ordering can be restricted to lex, I just used invlex as a shorthand for a variable ordering that happened to be faster). Another possible intermediate step is to calculate the radical of the ideal, though that is probably slow in general.
| | 2 | No.2 Revision |
You can calulate a Gröbner basis with respect to a lexicographic ordering to get an equivalent "triangular" system that can be solved back-to-front by successive solving and substitution (introducing parameters whenever there is a choice to be made).
sage: R.<a15, x13_14, a4, a11, a0, x14_15, x11_13, x5_5, x9_12, a5, a12, x3_4, a1, x7_7, x11_14, x12_15, x5_6, x4_4, x9_9, a6, a13, x3_5, a2, x10_10, x7_8, x6_6, x5_7, x12_12, x8_8, a7, x3_6, x6_7, x14_14, a9, x15_15, x4_6, x11_11, x8_9, a8, x10_12, a14, x13_13, a3, a10, x4_7, x12_14, x11_12, x13_15, x10_13> = PolynomialRing(QQ, order='invlex')
sage: polys = [-x3_4*x9_12, -x10_12*x3_4, -x10_13*x3_4, -x11_12*x3_4, -x11_13*x3_4, -x11_14*x3_4, x3_4^2*x7_7, x7_8*x8_9, -x11_12^2*x8_8, -x12_12*x3_4 + x3_4*x4_4, -x12_14*x3_4 + x3_4*x4_6, -x12_15*x3_4 + x3_4*x4_7, -x13_13*x3_4 + x3_4*x5_5, -x13_14*x3_4 + x3_4*x5_6, -x13_15*x3_4 + x3_4*x5_7, -x14_14*x3_4 + x3_4*x6_6, -x14_15*x3_4 + x3_4*x6_7, -x15_15*x3_4*x7_8 + x3_4*x7_8, x3_4*x3_5*x7_7, x3_4*x3_6*x7_7, a0 - 1, a1 - 1, a2 - 1, a3 - 1, a4*x4_4 - 1, a5*x5_5 - 1, a6*x6_6 - 1, a7*x7_7 - 1, a8*x8_8 - 1, a9*x9_9 - 1, a10*x10_10 - 1, a11*x11_11 - 1, a12*x12_12 - 1, a13*x13_13 - 1, a14*x14_14 - 1, a15*x15_15 - 1]
sage: I = R.ideal(polys)
sage: %time G = I.groebner_basis(algorithm='libsingular:std')
CPU times: user 4.45 ms, sys: 91 µs, total: 4.55 ms
Wall time: 4.57 ms
sage: list(G)
[a15*x3_4*x7_8 - x3_4*x7_8, a15*x15_15 - 1, x13_14*x3_4 - x3_4*x5_6, a4*x3_4 - a12*x3_4, a4*x4_4 - 1, a11*x11_11 - 1, a0 - 1, x14_15*x3_4 - x3_4*x6_7, x11_13*x3_4, x5_5*a5 - 1, x5_5*x3_4 - x3_4*x13_13, x9_12*x3_4, a5*x3_4 - x3_4*a13, a12*x12_12 - 1, x3_4^2, x3_4*x11_14, x3_4*x12_15 - x3_4*x4_7, x3_4*x4_4 - x3_4*x12_12, x3_4*a6 - x3_4*a14, x3_4*x3_5, x3_4*x7_8*x15_15 - x3_4*x7_8, x3_4*x6_6 - x3_4*x14_14, x3_4*x5_7 - x3_4*x13_15, x3_4*x3_6, x3_4*x4_6 - x3_4*x12_14, x3_4*x10_12, x3_4*x11_12, x3_4*x10_13, a1 - 1, x7_7*a7 - 1, x9_9*a9 - 1, a6*x6_6 - 1, a13*x13_13 - 1, a2 - 1, x10_10*a10 - 1, x7_8*x8_9, x8_8*a8 - 1, x14_14*a14 - 1, a3 - 1, x11_12^2]
This equivalent system can be passed to solve, which then does the job faster:
sage: %time solve(list(map(SR, G)), list(map(SR, R.gens())))
CPU times: user 3.04 s, sys: 170 ms, total: 3.21 s
Wall time: 2.53 s
Different variable orderings may lead to different speeds (the monomial ordering can be restricted to lex, I just used invlex as a shorthand for a variable ordering that happened to be faster). Another possible intermediate step is to calculate the radical of the ideal, though that is probably slow in general.
