Singular
https://www.singular.uni-kl.de/forum/

Getting certificates for ideal membership
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1532		 Page 1 of 1
Author:  jrh [ Tue Sep 26, 2006 9:39 pm ]
Post subject:  Getting certificates for ideal membership
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.
Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/