Ask Your Question
1

multivariate polynomial root-finding

asked 2013-07-08 14:10:36 +0100

bcriger gravatar image

updated 2013-07-08 16:36:18 +0100

calc314 gravatar image

I have a series of large, high-degree, bivariate polynomials in two variables, p and q. For example, one of these polynomials is:

$p^7 (25/4 q^6 - 75 q^5 + 525/2 q^4 - 400 q^3 + 300 q^2 - 120 q + 20) + p^6 (-175/8 q^6 + 525/2 q^5 - 3675/4 q^4 + 1400 q^3 - 1050 q^2 + 420 q - 70) + p^5 (255/8 q^6 - 765/2 q^5 + 2655/2 q^4 - 1980 q^3 + 1425 q^2 - 540 q + 84) + p^4 (-25 q^6 + 300 q^5 - 8175/8 q^4 + 1450 q^3 - 1875/2 q^2 + 300 q - 35) + p^3 (45/4 q^6 - 135 q^5 + 1785/4 q^4 - 580 q^3 + 300 q^2 - 60 q) + p^2 (-45/16 q^6 + 135/4 q^5 - 855/8 q^4 + 120 q^3 - 75/2 q^2) + p (5/16 q^6 - 15/4 q^5 + 45/4 q^4 - 10 q^3) + 1$

I would like to find all values of $q$ for which this polynomial is equal to $1-p$. The following code block illustrates my problem:

sage: fid7tof
5/4*(5*q^6 - 60*q^5 + 210*q^4 - 320*q^3 + 240*q^2 - 96*q + 16)*p^7 - 35/8*(5*q^6 - 60*q^5 + 210*q^4 - 320*q^3 + 240*q^2 - 96*q + 16)*p^6 + 3/8*(85*q^6 - 1020*q^5 + 3540*q^4 - 5280*q^3 + 3800*q^2 - 1440*q + 224)*p^5 - 5/8*(40*q^6 - 480*q^5 + 1635*q^4 - 2320*q^3 + 1500*q^2 - 480*q + 56)*p^4 + 5/4*(9*q^6 - 108*q^5 + 357*q^4 - 464*q^3 + 240*q^2 - 48*q)*p^3 - 15/16*(3*q^6 - 36*q^5 + 114*q^4 - 128*q^3 + 40*q^2)*p^2 + 5/16*(q^6 - 12*q^5 + 36*q^4 - 32*q^3)*p + 1
sage: solve([fid7tof == 1-p], q)
[0 == 5*(10*p^4 - 20*p^3 + 16*p^2 - 6*p + 1)*q^6 - 60*(10*p^4 - 20*p^3 + 16*p^2 - 6*p + 1)*q^5 + 30*(70*p^4 - 140*p^3 + 109*p^2 - 39*p + 6)*q^4 - 160*(20*p^4 - 40*p^3 + 29*p^2 - 9*p + 1)*q^3 + 160*p^4 + 600*(4*p^4 - 8*p^3 + 5*p^2 - p)*q^2 - 320*p^3 - 960*(p^4 - 2*p^3 + p^2)*q + 112*p^2 + 48*p + 16]

All Sage returns is another multivariate polynomial, which doubtless has many solutions $\bar{q}(p)$. Is there something I can do to get these solutions?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2013-07-08 15:38:50 +0100

vdelecroix gravatar image

updated 2013-07-08 15:40:17 +0100

Hi,

You should avoid using the symbolic ring for computations with polynomials (it is slow and most of the time the answer is wrong). Here is a way to solve your question. You want to solve the following system

$25/4q^6-75q^5+525/2q^4-400q^3+300q^2-120q+20 = 0$ $175/8q^6-525/2q^5+3675/4q^4-1400q^3+1050q^2-420q+70 = 0$

...

$(5/16q^6-15/4q^5+45/4q^4-10q^3) = -1$

You can enter each of these polynomials into Sage:

sage: R.<q> = PolynomialRing(QQ,'q')
sage: P7 = (5*q^6 - 60*q^5 + 210*q^4 - 320*q^3 + 240*q^2 - 96*q + 16)
sage: P5 = (85*q^6 - 1020*q^5 + 3540*q^4 - 5280*q^3 + 3800*q^2 - 1440*q + 224)
...
sage: P1 = (q^6 - 12*q^5 + 36*q^4 - 32*q^3)

Now, if there is a common solution there is a common irreducible factor to P7, P6, P5, P4, P3, P2 and P1-1. But as you can check there is no, even between P7 and P5:

sage: P7.factor()
(5) * (q^6 - 12*q^5 + 42*q^4 - 64*q^3 + 48*q^2 - 96/5*q + 16/5)
sage: P5.factor()
(85) * (q^6 - 12*q^5 + 708/17*q^4 - 1056/17*q^3 + 760/17*q^2 - 288/17*q + 224/85)

So, there is no q for this polynomial.

V.

edit flag offensive delete link more

Comments

I'm afraid that's mathematically incorrect. Treating the polynomial I provided as a system of polynomials eliminates solutions. They don't all have to be zero in order for the problem to be solved.

bcriger gravatar imagebcriger ( 2013-07-08 16:53:42 +0100 )edit

What ? If you want to solve $f7(q) p^7 + f6(q) p^6 + ... + f1(q) p + f0(q)$ to be zero (independently of p) then it must be that all of $f0$, $f1$, ..., $f7$ are zero. What do I miss ?

vdelecroix gravatar imagevdelecroix ( 2013-07-08 17:48:11 +0100 )edit

you mean that you want to solve q in terms of p ?

vdelecroix gravatar imagevdelecroix ( 2013-07-08 17:49:10 +0100 )edit

Yes, there are multiple solutions $\bar{q}(p)$. I've found a workaround that involves numerical root-finding for high-degree polynomials, let me know if you want to see it.

bcriger gravatar imagebcriger ( 2013-07-08 19:06:47 +0100 )edit

Vincent's answer is correct for the usual meaning of "equal polynomials". Presumably the OP has a non-standard definition of "equal" in mind, like evaluate to the same value at certain points.

Volker Braun gravatar imageVolker Braun ( 2013-07-09 00:39:30 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-07-08 14:10:36 +0100

Seen: 1,543 times

Last updated: Jul 08 '13