Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post subject: Getting certificates for ideal membership
PostPosted: Tue Sep 26, 2006 9:39 pm 

Joined: Tue Sep 26, 2006 9:33 pm
Posts: 1
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.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 1 post ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Sat Apr 21, 2018 3:36 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group