Re: Re: another Bug in Reduce ?

*To*: mathgroup at smc.vnet.net*Subject*: [mg60594] Re: [mg60533] Re: another Bug in Reduce ?*From*: Adam Strzebonski <adams at wolfram.com>*Date*: Wed, 21 Sep 2005 03:20:34 -0400 (EDT)*References*: <dgit7h$2ag$1@smc.vnet.net> <200509190845.EAA23572@smc.vnet.net> <ED1C56B6-A552-4CA6-A365-562B710B4271@mimuw.edu.pl> <432F2F3F.1030106@wolfram.com> <2AA13211-4413-42B0-81DD-F32333A5EBB2@mimuw.edu.pl>*Reply-to*: adams at wolfram.com*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote: > > On 20 Sep 2005, at 06:35, Adam Strzebonski wrote: > >>> 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 >> > > By the "rest of the problems" I meant the problems with Reduce > discussed in Maxim's post. They involve things like Im[Sqrt[x]], > Infinities etc, so they do not use CAD, and it seems to me that some > sort of "heuristics" (by whch I mean "special case" based techniques > rather than general algorithms like CAD) have to be used in these > situations. > > Andrzej Kozlowski > The "heuristics" used by Reduce are also supposed to always give the correct answer. By this I mean that we never intentionally allow an answer that has not been rigorously proven. An exception is zero testing of transcendental constant expressions, but when Reduce uses numerical zero testing it gives a warning message. In[1]:= zero=2 Sin[Pi/8]-Sqrt[2 - Sqrt[2]]; In[2]:= Reduce[zero x^3+zero^2 x^2+x-1==0, x] Reduce::ztest: Unable to decide whether numeric quantities Pi Pi 2 {Sqrt[2 - Sqrt[2]] - 2 Sin[--], -2 + <<2>> - 4 Sin[--] } 8 8 are equal to zero. Assuming they are. Out[2]= x == 1 That said, I agree that the heuristics used to solve nonalgebraic problems are probably more bug prone than the general algorithms. This is due to multitude of special case rules that have been produced through solving equations and inequalities by hand, and to the fact that testing interactions between different methods (Reduce works recursively) is more difficult than testing well defined algorithms. Best Regards, Adam Strzebonski Wolfram Research

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