[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
Prev by Date:
**Re: NonlinearFit-Logistic Function-CalcCenter 3**
Next by Date:
**Re: Re: another Bug in Reduce ?**
Previous by thread:
**Re: Re: another Bug in Reduce ?**
Next by thread:
**Re: Re: another Bug in Reduce ?**
| |