MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: problem solving polynomial equations


Andrzej Kozlowski wrote:
> On 15 Oct 2005, at 11:22, wtplasar at ehu.es wrote:
> 
> 
>>Hi,
>>
>>
>>I have  two equations. The first one is
>> [...]
> 
> Basically what happens is this. Solve can't find the general solution  
> to parametric equations of this kind. (It is not the fault of Solve;  
> there is really no way to do it).  So what it does is returns  
> basically any solutions it can find, by using certain "heuristic"  
> methods. One method is simply to set some variables to 0 and see if  
> the equations can be solved for the remaining ones. This is what  
> seems to happen here:
> 
> 
> Solve[{eqy == 0, eqz == 0}, {y, z}] /. Sign[s]^2 -> 1
> 
> 
> {{y -> (1/4)*((-r)*Sign[s] - Sqrt[r^2 - 8*b]), z -> 0},
>    {y -> (1/4)*(r*Sign[s] - Sqrt[r^2 - 8*b]), z -> 0},
>    {y -> (1/4)*(Sqrt[r^2 - 8*b] - r*Sign[s]), z -> 0},
>    {y -> (1/4)*(r*Sign[s] + Sqrt[r^2 - 8*b]), z -> 0},
>    {y -> 0}}
> 
> These are the kind of solutions you could find yourself by hand!
> 
> Now for the other case.
> 
> Solve[{Numerator[eqy] == 0, Numerator[eqz] == 0}, {y, z}] /. Sign[s] 
> ^2 -> 1
> 
> This is pure speculation, but I would guess Solve has for some reason  
> started to apply some algorithm that might give additional solutions.  
> Unfortunately there is no reason to believe that the computation will  
> finish in reasonable time. This could in fact be one of the cases  
> where "better is worse", meaning that the fact that the equations are  
> "better" (so Mathematica makes a serious attempt to find solutions)  
> cases no solutions to be returned. To see this phenomenon in an  
> extreme form on a trivial example, compare these two equations:
> 
> 
> 
> Solve[x (Exp[Sin[x]-Cos[x]])\[Equal]0,x]
> 
> Inverse functions are
>      being used
>        by Solve, so some solutions may not be \
> found; use Reduce for complete solution information.
> 
> {{x->0}}
> 
> Solve can do nothing with this except find the trivial solution so it  
> quickly returns the trivial solution. Now consider the following  
> equation that  I made up at random:
> 
> Solve[(x^32 - x^31)^(1/12) + (x^7 - x^11/3)^(1/5) + 17x + 5 == 0, x]
> 
> This is "better" than the other one, since Mathematica, in principle  
> knows algorithms for solving equations of this type. But it is  
> "worse" since the computation is unlikely to finish (I did not wait  
> long  but even if this ever finishes one can produce a more  
> complicated example that will not).
> 
> So, I think what happened in your case is that your second set of  
> equations is sufficiently "better" than the first to make it actually  
> "worse".
> 
> Well, of course, this is only speculation. Daniel Lichtblau can  
> almost certainly  tell if it is true, if he chooses to.
> 
> Andrzej Kozlowski
> 

The general principle that a more "transcendental" system might be 
solved faster than an "algebraic" one is correct. Moreover various 
tweaks in Solve over the years have had the effect of changing from one 
category to the other e.g. in handling of trigonometric systems.

For the system in question (replicated below) everything is algebraic, 
so this particular aspect of the issue is not involved. But then one can 
have seemingly similar systems with different levels of algebraic 
complexity, and that is what happens in these examples.

eqy = (y*(3*b^2 + 12*b*y^2 + 12*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
    3*r*y*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) + b^2*(1 + 3*z^4) +
       z^2*(8*b*y^2 + 4*y^4 + b^2*(3 + z^4))*Sign[k]]*Sign[s] +
    z^2*Sign[k]*(6*b^2 + 16*b*y^2 + 8*y^4 +
      r*y*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) + b^2*(1 + 3*z^4) +
         z^2*(8*b*y^2 + 4*y^4 + b^2*(3 + z^4))*Sign[k]]*Sign[s])))/
  (3*(3*b^2 + 8*b*y^2 + 4*y^4 + 3*b^2*z^4 +
     2*b*(3*b + 4*y^2)*z^2*Sign[k] +
    2*r*y*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) + b^2*(1 + 3*z^4) +
       z^2*(8*b*y^2 + 4*y^4 + b^2*(3 + z^4))*Sign[k]]*Sign[s]));

eqz = (y*z*(4*b*y + 8*y^3 + 4*b*y*z^4 +
    r*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) + b^2*(1 + 3*z^4) +
       z^2*(8*b*y^2 + 4*y^4 + b^2*(3 + z^4))*Sign[k]]*Sign[s] +
    z^2*Sign[k]*(8*b*y + 8*y^3 + r*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) +
         b^2*(1 + 3*z^4) + z^2*(8*b*y^2 + 4*y^4 +
       b^2*(3 + z^4))*Sign[k]]*
       Sign[s])))/(3*(3*b^2 + 8*b*y^2 + 4*y^4 + 3*b^2*z^4 +
    2*b*(3*b + 4*y^2)*z^2*Sign[k] +
    2*r*y*Sqrt[4*y^4 + 4*b*y^2*(1 + z^4) + b^2*(1 + 3*z^4) +
       z^2*(8*b*y^2 + 4*y^4 + b^2*(3 + z^4))*Sign[k]]*Sign[s]));

Just to be safe we'll force expressions into form numerator/denominator 
(I think they are that way already, but no reason not to be certain).

{eqy2,eqz2} = Together[{eqy,eqz}];

We've seen that we can do

ss1 = Solve[{eqy2,eqz2}==0, {y, z}]

but not

eenum = Numerator[{eqy2,eqz2}];
ssnum = Solve[eenum==0, {y,z}]

Why not? I checked in a debugger and found that the following 
intermediate systems were spawned. I'll set these up with assignments so 
  it can be seen as a "standalone" system.

e1 = 4*b*y + 8*y^3 + 4*b*y*z^4 + 8*b*y*z^2*Sign[k] + 8*y^3*z^2*Sign[k] +
    r*Sqrt[b^2 + 4*b*y^2 + 4*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
       3*b^2*z^2*Sign[k] + 8*b*y^2*z^2*Sign[k] + 4*y^4*z^2*Sign[k] +
       b^2*z^6*Sign[k]]*Sign[s] + r*z^2*Sign[k]*
     Sqrt[b^2 + 4*b*y^2 + 4*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
       3*b^2*z^2*Sign[k] + 8*b*y^2*z^2*Sign[k] + 4*y^4*z^2*Sign[k] +
       b^2*z^6*Sign[k]]*Sign[s] == 0 &&
  3*b^2 + 12*b*y^2 + 12*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
     6*b^2*z^2*Sign[k] +
    16*b*y^2*z^2*Sign[k] + 8*y^4*z^2*Sign[k] +
    3*r*y*Sqrt[b^2 + 4*b*y^2 + 4*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
       3*b^2*z^2*Sign[k] + 8*b*y^2*z^2*Sign[k] + 4*y^4*z^2*Sign[k] +
       b^2*z^6*Sign[k]]*Sign[s] + r*y*z^2*Sign[k]*
     Sqrt[b^2 + 4*b*y^2 + 4*y^4 + 3*b^2*z^4 + 4*b*y^2*z^4 +
       3*b^2*z^2*Sign[k] + 8*b*y^2*z^2*Sign[k] + 4*y^4*z^2*Sign[k] +
       b^2*z^6*Sign[k]]*Sign[s] == 0;

e2 = 3*b^2 + 8*b*y^2 + 4*y^4 + 3*b^2*z^4 + 6*b^2*z^2*Sign[k] +
    8*b*y^2*z^2*Sign[k] + 2*r*y*Sqrt[b^2 + 4*b*y^2 + 4*y^4 + 3*b^2*z^4 +
       4*b*y^2*z^4 + 3*b^2*z^2*Sign[k] + 8*b*y^2*z^2*Sign[k] +
       4*y^4*z^2*Sign[k] + b^2*z^6*Sign[k]]*Sign[s] != 0;

Note that these are both algebraic (though not polynomial) in the 
variables {y,z}. The first above, e1, is a subsystem spawned from the 
numerators only. When we include denominators we also have the 
unequation given as e2. The system that does not hang is in essence the 
first one below.

In[40]:= Timing[ss2 = Solve[e1 && e2, {y,z}]]

Out[40]= {0.043993 Second, {}}

We see that there is not solution; presumably the denominator unequation 
conflicts with one of the numerator-induced equations.

Without the denominator unequation it turns out that Solve must work 
much harder:

In[42]:= Timing[ss1 = Solve[e1, {y,z}]]

(Has not finished after several minutes.)

Conclusion: Algebraic complexity bogs down the seemingly simpler 
numerator-only system, but not the original system.


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Bug with Limit, Series and ProductLog ?
  • Next by Date: Re: Language vs. Library why it matters / Turing
  • Previous by thread: Re: problem solving polynomial equations
  • Next by thread: Re: Solving Diophantine Equations