MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: "layering" 2d plots
  • Next by Date: Re: "layering" 2d plots
  • Previous by thread: Re: Re: another Bug in Reduce ?
  • Next by thread: Dropping Similar Numbers from List