Groebner basis computation efficiency

Guest · Thu Mar 10, 2022 4:34 am

Hi. I have the following ideal, which turns out to be the maximal ideal generated by all the variables. Magma can compute a Groebner basis in a few seconds, while in Singular, "std(I)" seems to take forever. Is there a trick that one can use to speed up the computation, or is Magma using voodoo magic? Thanks!

Code:

ring R = 0,(x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28),dp;
ideal I = -x6*x9+x5*x10-x8*x11+x7*x12,-2*x1*x10-x2*x11-x2*x12+x3*x12,x3*x9+2*x0*x10+x4*x10-2*x6,-x3*x10-x8*x10+x0*x11+x0*x12+x6*x12-x3-x7-x8,-x1*x9+x2*x10-x0*x12+x2+x4+x8,-x7*x9-x1*x10+x5*x11-x3,x7*x10-x4*x11-x6*x11-x10,-x7*x9+x5*x11-x2*x12+2*x1+x9,x4*x9+x6*x9-x5*x10+x2-x12,x2*x10+x2-x3+x11,-x6*x13+x5*x14-x8*x15+x7*x16,-2*x1*x14-x2*x15-x2*x16+x3*x16+2*x6,x3*x13+2*x0*x14+x4*x14,-x3*x14-x8*x14+x0*x15+x0*x16+x6*x16+x4,-x1*x13+x2*x14-x0*x16+x5,-x7*x13-x1*x14+x5*x15-x2+x6,x7*x14-x4*x15-x6*x15-x3-x14,-x7*x13+x5*x15-x2*x16-2*x0-x4+x13,x4*x13+x6*x13-x5*x14-x16,x2*x14+x15,-x6*x17+x5*x18-x8*x19+x7*x20,-2*x1*x18-x2*x19-x2*x20+x3*x20+x3+x7+x8,x3*x17+2*x0*x18+x4*x18-x4,-x3*x18-x8*x18+x0*x19+x0*x20+x6*x20,-x1*x17+x2*x18-x0*x20-x0-x6,-x7*x17-x1*x18+x5*x19+x1,x7*x18-x4*x19-x6*x19-x18,-x7*x17+x5*x19-x2*x20+x3+x8+x17,x4*x17+x6*x17-x5*x18-x0-x20,x2*x18-x0-x6+x19,-x6*x21+x5*x22-x8*x23+x7*x24,-2*x1*x22-x2*x23-x2*x24+x3*x24-x2-x4-x8,x3*x21+2*x0*x22+x4*x22-x5,-x3*x22-x8*x22+x0*x23+x0*x24+x6*x24+x0+x6,-x1*x21+x2*x22-x0*x24,-x7*x21-x1*x22+x5*x23+x0,x7*x22-x4*x23-x6*x23+x1-x22,-x7*x21+x5*x23-x2*x24-x2+x21,x4*x21+x6*x21-x5*x22-x24,x2*x22+x0+x23,-x6*x25+x5*x26-x8*x27+x7*x28,-2*x1*x26-x2*x27-x2*x28+x3*x28+x3,x3*x25+2*x0*x26+x4*x26+x2-x6,-x3*x26-x8*x26+x0*x27+x0*x28+x6*x28-x1,-x1*x25+x2*x26-x0*x28-x0,-x7*x25-x1*x26+x5*x27,x7*x26-x4*x27-x6*x27+x7-x26,-x7*x25+x5*x27-x2*x28+x1+x25,x4*x25+x6*x25-x5*x26-x5-x28,x2*x26+x27;

Re: Groebner basis computation efficiency

hannes · Fri Mar 18, 2022 4:01 pm

Groebner bases algorithms use ops lot of heuristics: heuristics are often good strategies,
but fails sometime horribly.
To solve your example one may choose the following approach:
- compute a GB in characteristic p1_, ...p_n with slimgb
- lift the results via chinese reamider theorem
- check the result to be a GB and to contain all initial generators
https://www.singular.uni-kl.de/ft ... /modgb.lib
provides this:

Code:

LIB"modgb.lib";
ring r=0,....
ideal I=....
ideal J=modGB("slimgb",I,0);

Re: Groebner basis computation efficiency

Guest · Mon Mar 21, 2022 11:25 am

Thank you, that's very helpful! Indeed over finite fields the computation is a lot faster.

I have another question. For my example say, I can guess before hand that my ideal is the maximal ideal, is there an easy way to test this?

More precisely, I guess that at the last step of the modular method, one only needs to test one inclusion, since the other one is automatic by the GB computation. But what about an arbitrary set of generators? (x0,...,x28 in my example)