# Singular

 Page 1 of 1 [ 1 post ]
 Print view | E-mail friend Previous topic | Next topic
Author Message
 Post subject: Getting certificates for ideal membershipPosted: 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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 1 post ]

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

 It is currently Wed Jan 23, 2019 9:40 pm