Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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 ...
share|improve this answer
    
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? –  Estes Feb 22 '13 at 13:21
    
Appreciate the sage code, I must try it out. Best wishes –  Estes Feb 22 '13 at 15:25
    
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 ... –  Peter Mueller Feb 22 '13 at 15:47
    
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. –  Estes Feb 26 '13 at 17:30

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.

share|improve this answer
    
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. –  Peter Mueller Feb 26 '13 at 21:11
    
Symbolically, generating the dependence of the polynomial coefficients on a,b,c,d. –  Estes Feb 27 '13 at 12:08
    
Added more details to my answer. –  Peter Mueller Feb 27 '13 at 13:19
    
Very useful Peter. Many thanks for your help with this –  Estes Mar 1 '13 at 9:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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