Back to Forum | View unanswered posts | View active topics
Topic review - Groebner basis computation efficiency |
Author |
Message |
|
|
Post subject: |
Re: Groebner basis computation efficiency |
|
|
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)
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)
|
|
|
|
Posted: Mon Mar 21, 2022 11:25 am |
|
|
|
|
|
Post subject: |
Re: Groebner basis computation efficiency |
|
|
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);
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/ftp/pub/Math/Singular/misc/modgb.lib provides this: [code] LIB"modgb.lib"; ring r=0,.... ideal I=.... ideal J=modGB("slimgb",I,0); [/code]
|
|
|
|
Posted: Fri Mar 18, 2022 4:01 pm |
|
|
|
|
|
Post subject: |
Groebner basis computation efficiency |
|
|
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;
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;[/code]
|
|
|
|
Posted: Thu Mar 10, 2022 4:34 am |
|
|
|
|
|
It is currently Fri May 13, 2022 10:54 am
|
|