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

Re: Re: another Bug in Reduce ?

• To: mathgroup at smc.vnet.net
• Subject: [mg60565] Re: [mg60533] Re: another Bug in Reduce ?
• From: Adam Strzebonski <adams at wolfram.com>
• Date: Tue, 20 Sep 2005 05:19:47 -0400 (EDT)
• References: <dgit7h$2ag$1@smc.vnet.net> <200509190845.EAA23572@smc.vnet.net> <ED1C56B6-A552-4CA6-A365-562B710B4271@mimuw.edu.pl>
• Reply-to: adams at wolfram.com
• Sender: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote:
> 
> On 19 Sep 2005, at 17:45, Maxim wrote:
> 
>> On Sun, 18 Sep 2005 05:16:33 +0000 (UTC), Peter Pein  <petsie at dordos.net>
>> wrote:
>>
>>
>>> Dear group,
>>>
>>> in message <dba4l5$elr$1 at smc.vnet.net> (07/16 2005), Mukhtar Bekkali
>>> described a problem which involved Root[.] in dependance of a  
>>> parameter.
>>>
>>> This revealed another difference in the Reduce algorithms of versions
>>> 5.1 and 5.2.
>>>
>>> Please have a look at
>>> http://people.freenet.de/Peter_Berlin/Mathe/ReduceBug/ReduceBug.nb or
>>> http://people.freenet.de/Peter_Berlin/Mathe/ReduceBug/ReduceBug.html.
>>>
>>> In this case, version 5.1 did the better Job (and faster too).
>>>
>>> Peter
>>>
>>> P.S. the strange looking test for the root being real became  necessary,
>>> because Im[#]==0& did not work. (?)
>>>
>>>
>>
>> It seems that Reduce has problems with multiple roots:
>>
>> In[1]:= $Version
>>
>> Out[1]= "5.2 for Microsoft Windows (June 20, 2005)"
>>
>> In[2]:= Reduce[Root[#^3 + p*# - p - 1&, 2] ==
>>            Root[#^3 + p*# - p - 1&, 3], Reals] (* /. p -> -3 *)
>>
>> Out[2]= False
>>
>> In[3]:= Reduce[Root[#^3 + p*# - p - 1&, 3] > 0] (* /. p -> -3 *)
>>
>> Out[3]= p < -3 || -3 < p < -3/4
> 
> 
> 
> 
> The problem here seems to be with CylindricalDecomposition. This  gives 
> the right answer:
> 
> 
> CylindricalDecomposition[y^3 + p*y - p - 1 == 0, {p, y}]
> 
> 
> (p < -3 && (y == (-(1/2))*Sqrt[-4*p - 3] - 1/2 ||
>     y == 1 || y == (1/2)*Sqrt[-4*p - 3] - 1/2)) ||
>   (p == -3 && (y == -2 || y == 1)) ||
>   (-3 < p < -(3/4) && (y == (-(1/2))*Sqrt[-4*p - 3] -
>       1/2 || y == (1/2)*Sqrt[-4*p - 3] - 1/2 ||
>     y == 1)) || (p == -(3/4) && (y == -(1/2) ||
>     y == 1)) || (p > -(3/4) && y == 1)
> 
> we see that the cylindrical has cylinders for   p<-3, -3<p<(-3/4) and  
> single points for p=-3, p=-3/4. These correspond to multiple roots.  
> However, when we look at the way in which these solutions appear in  the 
> cylindrical decomposition we see  (p == -3 && (y == -2 || y ==  1))  
> whereas the actual solution is (p == -3 && (y == -2 || y == 1 ||  y== 
> 1)) and similarly (y == -(1/2) || y == 1)) while the solution is  (y == 
> -(1/2) || y == 1) || y== -(1/2)). 

CylindricalDecomposition does not show multiplicities. I don't think
the notion of solution multiplicity is even well defined for a general
system of equations and inequalities...

> So maybe this explains what  we see here:
> 
> 
> CylindricalDecomposition[Root[#1^3 + p*#1 - p - 1 & , 3] - Root[#1^3  + 
> p*#1 - p - 1 & , 2] == q, {p, q}]
> 
> (p < -3 && q == (1/2)*Sqrt[-4*p - 3] - 3/2) || (-3 < p < -(3/4) && q  == 
> 3/2 - (1/2)*Sqrt[-4*p - 3])
> 
> Note that the case p=-3 does not appear. This seems to be due to the  
> fact that in the above solution there appear only two roots for the  
> case p=-3 and there is not third one. Now look at the next output:
> 
> 
> CylindricalDecomposition[Root[#1^3 + p*#1 - p - 1 & , 1] - Root[#1^3  + 
> p*#1 - p - 1 & , 2] == q, {p, q}]
> 
> 
> (p <= -3 && q == (-(1/2))*Sqrt[-4*p - 3] - 3/2) || (-3 < p < -(3/4)  && 
> q == -Sqrt[-4*p - 3]) || (p == -(3/4) && q == -(3/2))
> 
> 
> Now the case p== -3/4 does appear but look at the value of q. It is  
> -3/2 which is the difference -1/2 -1. But this is not the difference  
> between the first and the third root! So it looks like we are seeing  
> the cause of the bug: it comes form the fact that  
> CylindricalDecomposition forgets about double roots as in the above  
> example.

It was a bug in the CAD code handling Root objects with parameters.
Thank you for isolating it. I have fixed it in the development version.

A piece of code which required input preprocessed with Factor was
being called without the preprocessing. In effect, if the defining
polynomial of a Root object with parameters given in the input was
not staying exactly the same after applying Factor to it, CAD could
get root multiplicities wrong. In your example the polynomial has
two factors

In[2]:= #1^3 + p*#1 - p - 1//Factor

                                   2
Out[2]= (-1 + #1) (1 + p + #1 + #1 )

In the original example Mathematica 5.2 (but not Mathematica 5.1)
Root function collects coefficients in the defining polynomial
wrt. powers of #1

In[1]:= Root[-160 + 783*x + 54*x^2 - 1059*#1 - 540*x*#1 + 504*#1^2 + 
80*#1^3 &, 3][[1, 1]]//InputForm

Out[1]//InputForm=
-160 + 783*x + 54*x^2 + (-1059 - 540*x)*#1 + 504*#1^2 + 80*#1^3

which uncovers the bug in CAD, because Factor gives a completely
expanded form

In[2]:= Factor[%]//InputForm

Out[2]//InputForm=
-160 + 783*x + 54*x^2 - 1059*#1 - 540*x*#1 + 504*#1^2 + 80*#1^3

> 
> As for the rest of the problems they seem to me very difficult to  deal 
> with. Essentially the algorithms used by Reduce,  
> CylindricalAlgebraicDecomposition and Quantifier ELimination are  purely 
> algebraic; they work for polynomial expressions. It seems to  me that 
> all other types of expressions have to be deal with by  heuristic 
> methods and probably can never be made fully reliable  (which is not to 
> say they can't be made better).
> 

Cylindrical algebraic decomposition can handle real algebraic functions
(Root objects and radical expressions) in full generality. It should
always give the correct answer (provided there are no bugs...).

Best Regards,

Adam Strzebonski
Wolfram Research

• References:
  • Re: another Bug in Reduce ?
    • From: Maxim <ab_def@prontomail.com>