For purposes of proof certification, I'm interested in getting hold of the expansion of a polynomial in terms of generators for an ideal containing it. That is, when p is in the ideal generated by <p1,...,pn> I want to get q1,...,qn such that
p = p1 * q1 + ... + pn * qn
I was recently told that I can use the "lift" command in Singular for this. Indeed this works, but I'm hitting efficiency problems when the examples get larger. For example, consider:
ring r = 0,(x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20),dp; setring r; short = 0; poly f0 = (((x15 - x11) * x0) - 1); poly f1 = (((x4 - x8) * x1) - 1); poly f2 = (((x11 - x8) * x2) - 1); poly f3 = (((x12 - x15) * x3) - 1); poly f4 = (((((x14^2) - (x15^3)) - (x17 * x15)) - x19)); poly f5 = (((((x9^2) - (x11^3)) - (x17 * x11)) - x19)); poly f6 = (((((x10^2) - (x8^3)) - (x17 * x8)) - x19)); poly f7 = ((((x15 - x11)^2) * (x4 + (x15 + x11))) - ((x14 - x9)^2)); poly f8 = (((x15 - x11) * (x6 + x14)) - (-((x14 - x9)) * (x4 - x15))); poly f9 = ((((x4 - x8)^2) * (x7 + (x4 + x8))) - ((x6 - x10)^2)); poly f10 = (((x4 - x8) * (x5 + x10)) - (-((x6 - x10)) * (x7 - x8))); poly f11 = ((((x11 - x8)^2) * (x12 + (x11 + x8))) - ((x9 - x10)^2)); poly f12 = (((x11 - x8) * (x13 + x9)) - (-((x9 - x10)) * (x12 - x11))); poly f13 = ((((x12 - x15)^2) * (x18 + (x12 + x15))) - ((x13 - x14)^2)); poly f14 = (((x12 - x15) * (x16 + x14)) - (-((x13 - x14)) * (x18 - x15))); poly f15 = ((((((x16^2) - (x18^3)) - (x17 * x18)) - x19) * x20) - 1); ideal I = f0,f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11,f12,f13,f14,f15;
If I now explicitly force a Groebner basis computation, I instantaneously get:
> groebner(I); _[1]=1
However, if I attempt to get 1 in terms of the generators, it's much slower, perhaps infeasible:
> lift(I,1);
After half an hour, it's still grinding away and swapping constantly. It could just be that the polynomials I want happen to be enormous. However, I don't expect this, since I can get some adequate polynomials that only fill a few pages out of my own Groebner basis code. (This is instrumented to provide such information, but is otherwise much less efficient than Singular's, hence my interest in using Singular.)
Is there some way I can harness Singular's algorithms to get the information I want more efficiently? If it helps, I'm mainly interested in the degenerate case (as in the example above) of showing 1 is in the ideal, i.e. that it is the whole ring.
Thanks,
John Harrison.
|
|