Groebner basis calculation [Archive]

Torquemada

Apr19-04, 01:11 PM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>I have an ideal generated by 75 binomials in 110 variables for which\nI\'d like to find a Groebner basis. I have no idea whether or not this\nis a tractable problem. I\'ve left it running in Singular for 2 days on\na 2.4GHz Pentium with no result so far (though it hasn\'t run out of\nmemory yet). However my problem is a special case with only binomial\ngenerators so I\'m wondering if there is some special purpose code out\nthere that can solve this problem. I tried just implementing\nBuchberger\'s algorithm with some code specialised for binomials but\nthat seems far too slow too. Or is this problem just too difficult on\ntodays PCs? Maybe it would take years or centuries? Is there something\nfaster than Singular out there that can handle 110 variables? What is\nthe state of the art in Groebner basis computations?\n\nI is the ideal, defined over the field Q, is given by all binomials of\nthe form\n\nc_i * A_j - B_i,j\n\nWhere j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in\nthe binary expansion of j.\n\nFor example c_0A_3-B_0,3 appears in I because 3=2^0+2^1 but\nc_4A_13-B_4,13 doesn\'t as 13=2^0+2^2+2^3 which doesn\'t contain 2^4.\n\nI\'d like to eliminate the c_i so I\'d like to use something like the\n5th elimination order though just plain lexicographic would do as long\nas the c_i are greater than the other monomials.\n\nI hope I haven\'t made too many errors in the above. This isn\'t really\nmy field.\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>I have an ideal generated by 75 binomials in 110 variables for which
I'd like to find a Groebner basis. I have no idea whether or not this
is a tractable problem. I've left it running in Singular for 2 days on
a 2.4GHz Pentium with no result so far (though it hasn't run out of
memory yet). However my problem is a special case with only binomial
generators so I'm wondering if there is some special purpose code out
there that can solve this problem. I tried just implementing
Buchberger's algorithm with some code specialised for binomials but
that seems far too slow too. Or is this problem just too difficult on
todays PCs? Maybe it would take years or centuries? Is there something
faster than Singular out there that can handle 110 variables? What is
the state of the art in Groebner basis computations?

I is the ideal, defined over the field Q, is given by all binomials of
the form

c_i * A_j - B_i,j

Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in
the binary expansion of j.

For example c_{0A_3}-B_0,3 appears in I because 3=2^0+2^1 but
c_{4A_13}-B_4,13 doesn't as 13=2^0+2^2+2^3 which doesn't contain 2^4.

I'd like to eliminate the c_i so I'd like to use something like the
5th elimination order though just plain lexicographic would do as long
as the c_i are greater than the other monomials.

I hope I haven't made too many errors in the above. This isn't really
my field.

Mitch Harris

Apr21-04, 03:22 PM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>Torquemada wrote:\n> I have an ideal generated by 75 binomials in 110 variables for which\n> I\'d like to find a Groebner basis. I have no idea whether or not this\n> is a tractable problem.\n\nSimplifying such a system is indeed intractable -in gereral-.\nThe associated problem of deciding if a polynomial is a member of an\nideal is EXPSPACE-complete problem (google for Mayr). This means it most\nlikely has a lower case GB computation that is exponential time (or worse,\nand the best algorithms so far take doubly exponential times in the number\nof variables.\n\n> I\'ve left it running in Singular for 2 days on\n> a 2.4GHz Pentium with no result so far (though it hasn\'t run out of\n> memory yet). However my problem is a special case with only binomial\n> generators so I\'m wondering if there is some special purpose code out\n> there that can solve this problem.\n\n"Special cases" is a different matter altogether. If your system is\nconveniently structured, you may be able to do a lot of elimination\ntheoretically (use symmetry, systematic elimination, induction)\n\n> I tried just implementing\n> Buchberger\'s algorithm with some code specialised for binomials but\n> that seems far too slow too. Or is this problem just too difficult on\n> todays PCs? Maybe it would take years or centuries? Is there something\n> faster than Singular out there that can handle 110 variables? What is\n> the state of the art in Groebner basis computations?\n\nGB computation in general reduces to GB computation with binomials (that\nis, binomial GB computation is just as hard as the unrestricted case).\n\n> I is the ideal, defined over the field Q, is given by all binomials of\n> the form\n>\n> c_i * A_j - B_i,j\n>\n> Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in\n> the binary expansion of j.\n>\n> For example c_0A_3-B_0,3 appears in I because 3=2^0+2^1 but\n> c_4A_13-B_4,13 doesn\'t as 13=2^0+2^2+2^3 which doesn\'t contain 2^4.\n>\n> I\'d like to eliminate the c_i so I\'d like to use something like the\n> 5th elimination order though just plain lexicographic would do as long\n> as the c_i are greater than the other monomials.\n\nBecause of the digit thing, there is a lot of structure here,\nso there might be hope.\n\nCan you do a much much smaller system by program and by hand\n(to check the program)? like j in {1,2,3}, i in {0,1}?\n\n--\nMitch Harris\n(remove q to reply)\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>Torquemada wrote:
> I have an ideal generated by 75 binomials in 110 variables for which
> I'd like to find a Groebner basis. I have no idea whether or not this
> is a tractable problem.

Simplifying such a system is indeed intractable -in gereral-.
The associated problem of deciding if a polynomial is a member of an
ideal is EXPSPACE-complete problem (google for Mayr). This means it most
likely has a lower case GB computation that is exponential time (or worse,
and the best algorithms so far take doubly exponential times in the number
of variables.

> I've left it running in Singular for 2 days on
> a 2.4GHz Pentium with no result so far (though it hasn't run out of
> memory yet). However my problem is a special case with only binomial
> generators so I'm wondering if there is some special purpose code out
> there that can solve this problem.

"Special cases" is a different matter altogether. If your system is
conveniently structured, you may be able to do a lot of elimination
theoretically (use symmetry, systematic elimination, induction)

> I tried just implementing
> Buchberger's algorithm with some code specialised for binomials but
> that seems far too slow too. Or is this problem just too difficult on
> todays PCs? Maybe it would take years or centuries? Is there something
> faster than Singular out there that can handle 110 variables? What is
> the state of the art in Groebner basis computations?

GB computation in general reduces to GB computation with binomials (that
is, binomial GB computation is just as hard as the unrestricted case).

> I is the ideal, defined over the field Q, is given by all binomials of
> the form
>
> c_i * A_j - B_i,j
>
> Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in
> the binary expansion of j.
>
> For example c_{0A_3}-B_0,3 appears in I because 3=2^0+2^1 but
> c_{4A_13}-B_4,13 doesn't as 13=2^0+2^2+2^3 which doesn't contain 2^4.
>
> I'd like to eliminate the c_i so I'd like to use something like the
> 5th elimination order though just plain lexicographic would do as long
> as the c_i are greater than the other monomials.

Because of the digit thing, there is a lot of structure here,
so there might be hope.

Can you do a much much smaller system by program and by hand
(to check the program)? like j in {1,2,3}, i in {0,1}?

--
Mitch Harris
(remove q to reply)

Daniel Lichtblau

Apr21-04, 03:25 PM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>google01@sigfpe.com (Torquemada) wrote in message news:<571e4e03.0404171706.21816012@posting.google. com>...\n> I have an ideal generated by 75 binomials in 110 variables for which\n> I\'d like to find a Groebner basis. I have no idea whether or not this\n> is a tractable problem. I\'ve left it running in Singular for 2 days on\n> a 2.4GHz Pentium with no result so far (though it hasn\'t run out of\n> memory yet). However my problem is a special case with only binomial\n> generators so I\'m wondering if there is some special purpose code out\n> there that can solve this problem. I tried just implementing\n> Buchberger\'s algorithm with some code specialised for binomials but\n> that seems far too slow too. Or is this problem just too difficult on\n> todays PCs? Maybe it would take years or centuries? Is there something\n> faster than Singular out there that can handle 110 variables? What is\n> the state of the art in Groebner basis computations?\n>\n> I is the ideal, defined over the field Q, is given by all binomials of\n> the form\n>\n> c_i * A_j - B_i,j\n>\n> Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in\n> the binary expansion of j.\n>\n> For example c_0A_3-B_0,3 appears in I because 3=2^0+2^1 but\n> c_4A_13-B_4,13 doesn\'t as 13=2^0+2^2+2^3 which doesn\'t contain 2^4.\n>\n> I\'d like to eliminate the c_i so I\'d like to use something like the\n> 5th elimination order though just plain lexicographic would do as long\n> as the c_i are greater than the other monomials.\n>\n> I hope I haven\'t made too many errors in the above. This isn\'t really\n> my field.\n\nI\'ll make a few remarks. First, you might get a better response if you\npost this sort of question to sci.math.symbolic (since Groebner basis\ncomputation methods are among the interests of people who lurk on that\ngroup). I\'m cross-posting thereto.\n\nSecond, your ideal has a couple of nice qualities (by the way, I get\n80 generators, not 75, assuming I interpreted the criterion\ncorrectly). For one, it is toric. For another, the generators already\ncomprise a Groebner basis with respect to term orders wherein the \'b\'\nvariables are weighted more heavily than all others (that is, term\norders that are elimination orders for those variables). This gives\nrise to two possible approaches.\n\n(1) Use a method that is dedicated to handling toric ideals.\n\n(2) Use a Groebner basis conversion method such as the Groebner walk.\n\nI do not know offhand whether either or both of these are available in\nSingular but I suspect this is not hard to learn from the\ndocumentation.\n\nTo get some idea of difficulty I tried this out in Mathematica. I set\nthe range of \'j\' to be a parameter so as to test smaller related\nproblems.\n\nisInBinaryExpansion[i_,j_] := Reverse[IntegerDigits[j,2,5]][[i+1]] ===\n1\n\ntoricProblem[n_, a_:a, b_:b, c_:c] := Module[\n{avars,bvars,cvars, allACproducts, usedACproducts, polys},\ncvars = Array[c, n, 0];\navars = Array[a, 2^n-1];\nallACproducts = Flatten[Outer[Times, cvars, avars]];\nusedACproducts = Cases[allACproducts, a[j_]*c[i_] /;\nisInBinaryExpansion[i,j]];\npolys = Map[#-(#/.a[j_]*c[i_]->b[i,j])&, usedACproducts];\nbvars = Cases[Variables[polys], b[__]];\nGroebnerBasis[polys, Join[avars,bvars], cvars,\nMonomialOrder->EliminationOrder, Sort->True]\n]\n\nNot surprisingly it is easy for n = 3.\n\nIn[5]:= Timing[gb3 = toricProblem[3];]\nOut[5]= {0.03 Second, Null}\n\nIn[7]:= gb3 // InputForm\nOut[7]//InputForm=\n{a[7]*b[1, 3] - a[3]*b[1, 7], a[7]*b[0, 3] - a[3]*b[0, 7],\na[7]*b[2, 5] - a[5]*b[2, 7], a[7]*b[0, 5] - a[5]*b[0, 7],\n-(a[5]*b[0, 3]) + a[3]*b[0, 5], a[7]*b[2, 6] - a[6]*b[2, 7],\n-(a[6]*b[2, 5]) + a[5]*b[2, 6], a[7]*b[1, 6] - a[6]*b[1, 7],\n-(a[6]*b[1, 3]) + a[3]*b[1, 6], a[7]*b[0, 1] - a[1]*b[0, 7],\na[5]*b[0, 1] - a[1]*b[0, 5], a[3]*b[0, 1] - a[1]*b[0, 3],\na[7]*b[1, 2] - a[2]*b[1, 7], a[6]*b[1, 2] - a[2]*b[1, 6],\na[3]*b[1, 2] - a[2]*b[1, 3], a[7]*b[2, 4] - a[4]*b[2, 7],\na[6]*b[2, 4] - a[4]*b[2, 6], a[5]*b[2, 4] - a[4]*b[2, 5],\n-(b[1, 7]*b[2, 6]) + b[1, 6]*b[2, 7], -(b[0, 7]*b[2, 5]) + b[0,\n5]*b[2, 7],\n-(b[0, 7]*b[1, 3]) + b[0, 3]*b[1, 7], -(a[7]*b[1, 3]*b[2, 6]) +\na[3]*b[1, 6]*b[2, 7], -(a[7]*b[0, 3]*b[2, 5]) + a[3]*b[0, 5]*b[2,\n7],\n-(a[3]*b[1, 6]*b[2, 5]) + a[5]*b[1, 3]*b[2, 6],\n-(b[0, 3]*b[1, 7]*b[2, 5]) + b[0, 5]*b[1, 3]*b[2, 7],\n-(b[0, 3]*b[1, 6]*b[2, 5]) + b[0, 5]*b[1, 3]*b[2, 6]}\n\n\nFor n = 4 the computation is far more substantial, but still not too\nhard.\n\nIn[9]:= Timing[gb4 = toricProblem[4];]\nOut[9]= {18.57 Second, Null}\n\nThe result is fairly large but again, not out of bounds by any means.\n\nIn[10]:= Length[gb4]\nOut[10]= 321\n\nIn[11]:= LeafCount[gb4]\nOut[11]= 5983\n\nNow n = 5 is another matter entirely. I ran out of memory on one\nattempt (after several minutes). I am now trying it again on a bigaram\nmachine. No telling what will happen. Groebner basis computations can\nbe funny that way.\n\n\nDaniel Lichtblau\nWolfram Research\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>google01@sigfpe.com (Torquemada) wrote in message news:<571e4e03.0404171706.21816012@posting.google.com>...
> I have an ideal generated by 75 binomials in 110 variables for which
> I'd like to find a Groebner basis. I have no idea whether or not this
> is a tractable problem. I've left it running in Singular for 2 days on
> a 2.4GHz Pentium with no result so far (though it hasn't run out of
> memory yet). However my problem is a special case with only binomial
> generators so I'm wondering if there is some special purpose code out
> there that can solve this problem. I tried just implementing
> Buchberger's algorithm with some code specialised for binomials but
> that seems far too slow too. Or is this problem just too difficult on
> todays PCs? Maybe it would take years or centuries? Is there something
> faster than Singular out there that can handle 110 variables? What is
> the state of the art in Groebner basis computations?
>
> I is the ideal, defined over the field Q, is given by all binomials of
> the form
>
> c_i * A_j - B_i,j
>
> Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in
> the binary expansion of j.
>
> For example c_{0A_3}-B_0,3 appears in I because 3=2^0+2^1 but
> c_{4A_13}-B_4,13 doesn't as 13=2^0+2^2+2^3 which doesn't contain 2^4.
>
> I'd like to eliminate the c_i so I'd like to use something like the
> 5th elimination order though just plain lexicographic would do as long
> as the c_i are greater than the other monomials.
>
> I hope I haven't made too many errors in the above. This isn't really
> my field.

I'll make a few remarks. First, you might get a better response if you
post this sort of question to sci.math.symbolic (since Groebner basis
computation methods are among the interests of people who lurk on that
group). I'm cross-posting thereto.

Second, your ideal has a couple of nice qualities (by the way, I get
80 generators, not 75, assuming I interpreted the criterion
correctly). For one, it is toric. For another, the generators already
comprise a Groebner basis with respect to term orders wherein the 'b'
variables are weighted more heavily than all others (that is, term
orders that are elimination orders for those variables). This gives
rise to two possible approaches.

(1) Use a method that is dedicated to handling toric ideals.

(2) Use a Groebner basis conversion method such as the Groebner walk.

I do not know offhand whether either or both of these are available in
Singular but I suspect this is not hard to learn from the
documentation.

To get some idea of difficulty I tried this out in Mathematica. I set
the range of 'j' to be a parameter so as to test smaller related
problems.

isInBinaryExpansion[i_,j_] :=[/itex] Reverse[IntegerDigits[j,2,5]][[i+1]] ===
1

toricProblem[n_, a_:a, b_:b, c_:c] := Module[
{avars,bvars,cvars, allACproducts, usedACproducts, polys},
cvars = Array[c, n, 0];
avars = Array[a, 2^n-1];
allACproducts = Flatten[Outer[Times, cvars, avars]];
usedACproducts = Cases[allACproducts, a[j_]*c[i_] /;
isInBinaryExpansion[i,j]];
polys = Map[#-(#/.a[j_]*c[i_]->b[i,j])&, usedACproducts];
bvars = Cases[Variables[polys], b[__]];
GroebnerBasis[polys, Join[avars,bvars], cvars,
MonomialOrder->EliminationOrder, Sort->True]
]

Not surprisingly it is easy for n = 3.

In[5]:= Timing[gb3 = toricProblem[3];]
Out[5]= {0.03 Second, Null}

In[7]:= gb3 // InputForm
Out[7]//InputForm=
{a[7]*b[1, 3] - a[3]*b[1, 7], a[7]*b[0, 3] - a[3]*b[0, 7],a[7]*b[2, 5] - a[5]*b[2, 7], a[7]*b[0, 5] - a[5]*b[0, 7],-(a[5]*b[0, 3]) + a[3]*b[0, 5], a[7]*b[2, 6] - a[6]*b[2, 7],-(a[6]*b[2, 5]) + a[5]*b[2, 6], a[7]*b[1, 6] - a[6]*b[1, 7],-(a[6]*b[1, 3]) + a[3]*b[1, 6], a[7]*b[0, 1] - a[1]*b[0, 7],a[5]*b[0, 1] - a[1]*b[0, 5], a[3]*b[0, 1] - a[1]*b[0, 3],a[7]*b[1, 2] - a[2]*b[1, 7], a[6]*b[1, 2] - a[2]*b[1, 6],a[3]*b[1, 2] - a[2]*b[1, 3], a[7]*b[2, 4] - a[4]*b[2, 7],a[6]*b[2, 4] - a[4]*b[2, 6], a[5]*b[2, 4] - a[4]*b[2, 5],-(b[1, 7]*b[2, 6]) + b[1, 6]*b[2, 7], -(b[0, 7]*b[2, 5]) + b[0,5]*b[2, 7],-(b[0, 7]*b[1, 3]) + b[0, 3]*b[1, 7], -(a[7]*b[1, 3]*b[2, 6]) +a[3]*b[1, 6]*b[2, 7], -(a[7]*b[0, 3]*b[2, 5]) + a[3]*b[0, 5]*b[2,
7],
[itex]-(a[3]*b[1, 6]*b[2, 5]) + a[5]*b[1, 3]*b[2, 6],-(b[0, 3]*b[1, 7]*b[2, 5]) + b[0, 5]*b[1, 3]*b[2, 7],-(b[0, 3]*b[1, 6]*b[2, 5]) + b[0, 5]*b[1, 3]*b[2, 6]}

For n = 4 the computation is far more substantial, but still not too
hard.

In[9]:= Timing[gb4 = toricProblem[4];]
Out[9]= {18.57 Second, Null}

The result is fairly large but again, not out of bounds by any means.

In[10]:= Length[gb4]
Out[10]= 321

In[11]:= LeafCount[gb4]
Out[11]= 5983

Now n = 5 is another matter entirely. I ran out of memory on one
attempt (after several minutes). I am now trying it again on a bigaram
machine. No telling what will happen. Groebner basis computations can
be funny that way.

Daniel Lichtblau
Wolfram Research

Mitch Harris

Apr22-04, 02:31 PM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>Torquemada <google01@sigfpe.com> wrote:\n>I have an ideal generated by 75 binomials in 110 variables for which\n>I\'d like to find a Groebner basis. I have no idea whether or not this\n>is a tractable problem.\n\nSimplifying such a system is indeed intractable -in gereral-.\nThe associated problem of deciding if a polynomial is a member of an\nideal is EXPSPACE-complete problem (google for Mayr). This means it most\nlikely has a lower case GB computation that is exponential time (or worse,\nand the best algorithms so far take doubly exponential times in the number\nof variables.\n\n\n>I\'ve left it running in Singular for 2 days on\n>a 2.4GHz Pentium with no result so far (though it hasn\'t run out of\n>memory yet). However my problem is a special case with only binomial\n>generators so I\'m wondering if there is some special purpose code out\n>there that can solve this problem.\n\n"Special cases" is a different matter altogether. If your system is\nconveniently structured, you may be able to do a lot of elimination\ntheoretically (use symmetry, systematic elimination, induction)\n\n>I tried just implementing\n>Buchberger\'s algorithm with some code specialised for binomials but\n>that seems far too slow too. Or is this problem just too difficult on\n>todays PCs? Maybe it would take years or centuries? Is there something\n>faster than Singular out there that can handle 110 variables? What is\n>the state of the art in Groebner basis computations?\n\nGB computation in general reduces to GB computation with binomials (that\nis binomoial GB computation is just as hard as the unrestricted case).\n\n>I is the ideal, defined over the field Q, is given by all binomials of\n>the form\n>\n>c_i * A_j - B_i,j\n>\n>Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in\n>the binary expansion of j.\n>\n>For example c_0A_3-B_0,3 appears in I because 3=2^0+2^1 but\n>c_4A_13-B_4,13 doesn\'t as 13=2^0+2^2+2^3 which doesn\'t contain 2^4.\n>\n>I\'d like to eliminate the c_i so I\'d like to use something like the\n>5th elimination order though just plain lexicographic would do as long\n>as the c_i are greater than the other monomials.\n\nCan you do a much much smaller system by program and by hand\n(to check the program)? like j in {1,2,3}, i in {0,1}?\n\n--\nMitch (remove q to respond)\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>Torquemada <google01@sigfpe.com> wrote:
>I have an ideal generated by 75 binomials in 110 variables for which
>I'd like to find a Groebner basis. I have no idea whether or not this
>is a tractable problem.

Simplifying such a system is indeed intractable -in gereral-.
The associated problem of deciding if a polynomial is a member of an
ideal is EXPSPACE-complete problem (google for Mayr). This means it most
likely has a lower case GB computation that is exponential time (or worse,
and the best algorithms so far take doubly exponential times in the number
of variables.

>I've left it running in Singular for 2 days on
>a 2.4GHz Pentium with no result so far (though it hasn't run out of
>memory yet). However my problem is a special case with only binomial
>generators so I'm wondering if there is some special purpose code out
>there that can solve this problem.

"Special cases" is a different matter altogether. If your system is
conveniently structured, you may be able to do a lot of elimination
theoretically (use symmetry, systematic elimination, induction)

>I tried just implementing
>Buchberger's algorithm with some code specialised for binomials but
>that seems far too slow too. Or is this problem just too difficult on
>todays PCs? Maybe it would take years or centuries? Is there something
>faster than Singular out there that can handle 110 variables? What is
>the state of the art in Groebner basis computations?

GB computation in general reduces to GB computation with binomials (that
is binomoial GB computation is just as hard as the unrestricted case).

>I is the ideal, defined over the field Q, is given by all binomials of
>the form
>
>c_i * A_j - B_i,j
>
>Where j is in {1,2,...,31}, i is in {0,1,2,3,4}, and 2^i appears in
>the binary expansion of j.
>
>For example c_{0A_3}-B_0,3 appears in I because 3=2^0+2^1 but
>c_{4A_13}-B_4,13 doesn't as 13=2^0+2^2+2^3 which doesn't contain 2^4.
>
>I'd like to eliminate the c_i so I'd like to use something like the
>5th elimination order though just plain lexicographic would do as long
>as the c_i are greater than the other monomials.

Can you do a much much smaller system by program and by hand
(to check the program)? like j in {1,2,3}, i in {0,1}?

--
Mitch (remove q to respond)