1
$\begingroup$

Getting nowhere with maple using its triangularize and groebner decompositions for even moderate size systems with any symbolic factors. Any suggestions on how better to approach this would be appreciated. To put a shape on this query I append a sample problem case below, u,v,w,x,y,z are variables, a,b,c,d constants.

6-cvu+cu+cv-2uv+8xy+8wy+8xz+8wz+8yz+8wx-8yzuv+16zyxw-c

-6x+2xu-6w+2wv-6y+2yuv-8yxw-6z+2zu+2zv+2zuv-8zxw-8zyw+8zywv-8zyx+8zyxu+2yu+2yv

4-4xyu-4wyv-4wzv-4xzu-4yzu-4yzv-uvd+ud+vd+4xy+4wy+4xz+4wz+4yz+4wx-2v-2u+4yzuv-d

-2w+2wv-2x+2xu-2y+2yu+2yv-2yuv-2z+2zu+2zv-2zuv

1+u+v+uv-a+ua+va-uva

4+4xyu+4wyv+4wzv+4xzu+4yzu+4yzv-uvb+ub+vb+4xy+4wy+4xz+4wz+4yz+4wx+2v+2u+4yzuv-b

$\endgroup$

2 Answers 2

4
$\begingroup$

Added more details: From specializing $a,b,c,d$ to random integers it seems that your system is $0$-dimensional, and $z$ is the root of a degree $16$ polynomial $f_{a,b,c,d}(z)$. You might compute these degree $16$ polynomials for many integer tuples $a,b,c,d$, and try to guess/interpolate the dependencies of the coefficients of $f_{a,b,c,d}(z)$ on $a,b,c,d$. Once you know $f_{a,b,c,d}(z)$, the rest of the computation should be cheap.

If one fixes all but one of the parameters $a,b,c,d$, and lets the remaining one run through some possibilities, one can guess the degrees of the dependencies of the coefficients of $f_{a,b,c,d}$ in $a,b,c,d$, and then solve the corresponding interpolation problem. For instance, the coefficient of $z^{14}$ seems to be $-3a/4+d-13/4$. The highest degree dependency seems to occur for the coefficient of $z^4$, of degrees $5,3,3,4$ in $a,b,c,d$, respectively. So in order to compute this coefficient, one has to compute $6\cdot 4\cdot 4\cdot 5=480$ examples, and solve the corresponding linear system of equations in $480$ unknowns. Don't know if that is possible, but I would expect it can be done.

The Sage code for the computation of $f_{a,b,c,d}$ is:

while True:
    a,b,c,d=(floor(20*random()-10) for i in range(4))
    R.<u,v,w,x,y,z>=PolynomialRing(QQ,6,order='lex')
    l=[6-c*v*u+ ... SNIP!!! ... +4*y*z*u*v-b]
    i=ideal(l)
    g=i.groebner_basis()
    zz=g[5]
    print (a,b,c,d),zz/zz.coefficient({z:16})

produces

(9, 4, 9, 5) z^16 - 5*z^14 + 47/4*z^12 - 833/64*z^10 + 2263/256*z^8 + 3973/1024*z^6 - 27697/4096*z^4 + 5775/4096*z^2 + 625/4096
(-7, 7, 5, -1) z^16 + z^14 + 13/8*z^12 - 23/8*z^10 + 3011/256*z^8 - 1193/128*z^6 + 16581/2048*z^4 + 2303/4096*z^2 + 2401/65536
(2, -7, 3, 1) z^16 - 15/4*z^14 + 29/4*z^12 - 305/32*z^10 + 75/8*z^8 - 1703/256*z^6 + 453/128*z^4 - 1233/1024*z^2 + 81/256
(-2, -5, -10, 2) z^16 + 1/4*z^14 - 17/8*z^12 - 41/32*z^10 + 457/256*z^8 + 1133/1024*z^6 - 605/1024*z^4 - 21/64*z^2 + 1/16
(-10, -3, -9, 4) z^16 + 33/4*z^14 + 219/8*z^12 + 1023/64*z^10 + 4017/256*z^8 - 6919/1024*z^6 - 1301/1024*z^4 - 138985/16384*z^2 + 130321/65536
(-4, 5, -4, 7) z^16 + 27/4*z^14 + 61/4*z^12 + 79/64*z^10 - 1293/64*z^8 + 4333/1024*z^6 + 24929/2048*z^4 - 40071/4096*z^2 + 130321/65536
(-7, -6, -9, 0) z^16 + 2*z^14 + z^12 - 23/4*z^10 + 643/128*z^8 - 331/128*z^6 + 171/256*z^4 - 243/256*z^2 + 6561/65536
... snip ...
$\endgroup$
4
  • $\begingroup$ Thanks Peter. I spent quite some time trying to do just this for the posted example using Maple, without success I should add. I had hoped to get the computation automated in order to inspect a number of similar cases. I fear it may not be possible, even in this relatively simple case. Many thanks for your input. As a matter of curiosity, how did you derive the polynomials for z? $\endgroup$
    – Estes
    Feb 22, 2013 at 13:21
  • $\begingroup$ Appreciate the sage code, I must try it out. Best wishes $\endgroup$
    – Estes
    Feb 22, 2013 at 15:25
  • $\begingroup$ Fixed the code from above, the markdown is a nightmare! The html construct <pre> distorted the third line. Now it's fine, the senseless colors are not my fault ... $\endgroup$ Feb 22, 2013 at 15:47
  • $\begingroup$ No solution found I'm afraid. Trial and error as a method ended up being overly complex given this is a single special case of a general class. $\endgroup$
    – Estes
    Feb 26, 2013 at 17:30
0
$\begingroup$

I believe this is not currently a tractable problem for any math package out there when symbolic constants are involved. It will be interesting to see how long this remains true.

$\endgroup$
4
  • $\begingroup$ Are you interested in this system of equations as a test case, or do you actually want to solve it symbolically? In the latter case, I have two further suggestions: (1) Your system has some several symmetries which can be taken advantage of in order to reduce the degrees. (2) You might tell where the system comes from, maybe someone has alternative ideas on how to manage the problem. $\endgroup$ Feb 26, 2013 at 21:11
  • $\begingroup$ Symbolically, generating the dependence of the polynomial coefficients on a,b,c,d. $\endgroup$
    – Estes
    Feb 27, 2013 at 12:08
  • $\begingroup$ Added more details to my answer. $\endgroup$ Feb 27, 2013 at 13:19
  • $\begingroup$ Very useful Peter. Many thanks for your help with this $\endgroup$
    – Estes
    Mar 1, 2013 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.