Re: Simplify UnitStep expressions
- To: mathgroup at smc.vnet.net
- Subject: [mg69326] Re: Simplify UnitStep expressions
- From: p-valko at tamu.edu
- Date: Thu, 7 Sep 2006 04:30:15 -0400 (EDT)
- References: <edm1qa$cps$1@smc.vnet.net>
With all due respect I am afraid the phenomenon has little to do with the actual algorithms used in Simplify[] and FullSimplify[], but rather with the way how assumptions are treated in general. To illustrate my statement, I show an example without any Simplify[] or FullSimplify[]: In: Assuming[a > 2, Not[a > 2] ] I would like to get an answer False, but Mathematica gives Out: a <= 2 Pretty surprising result ! ! ! Regards Peter Adam Strzebonski wrote: > Andrzej Kozlowski wrote: > > > > On 5 Sep 2006, at 16:20, Adam Strzebonski wrote: > > > >> Andrzej Kozlowski wrote: > >> > >>> On 1 Sep 2006, at 11:41, L. Dwynn Lafleur wrote: > >>> > >>>> The following is transcribed from a Mathematica 5.2 notebook in > >>>> Windows XP: > >>>> > >>>> In[1]:= Simplify[UnitStep[a-x/b], a-x/b > 0] > >>>> Out[1]= 1 > >>>> > >>>> In[2]:= Simplify[UnitStep[a-Pi/b], a-Pi/b > 0] > >>>> Out[2]= UnitStep[a-Pi/b] > >>>> > >>>> Why does the second output different from the first? I know it has > >>>> something to do with the fact that Pi is internally defined in > >>>> Mathematica > >>>> because a similar result occurs Pi is replaced with E, but what > >>>> logic is > >>>> being followed? > >>>> > >>>> -- > >>>> ====================================== > >>>> L. Dwynn Lafleur > >>>> Professor of Physics > >>>> University of Louisiana at Lafayette > >>>> lafleur at louisiana.edu > >>>> ====================================== > >>>> > >>> Curiously, if you use FullSimplify rather then Simplify you will get: > >>> FullSimplify[UnitStep[a-Pi/b], a-Pi/b > 0] > >>> 1 > >>> The same holds if Pi is replaces by E, or indeed by explicit > >>> functions of E or Pi such as Pi^2, E^Pi etc. In all such cases > >>> FullSimplify works but Simplify does not work. Strange. > >>> Andrzej Kozlowski > >> > >> > >> The cylindrical algebraic decomposition (CAD) algorithm used by Simplify > >> to prove inference requires polynomial inequalities with rational number > >> coefficients. a-x/b > 0 is equivalent to a polynomial inequality > >> -(a*b^2) + b*x < 0 which has rational number coefficients. > >> a-Pi/b > 0 is equivalent to a polynomial inequality -(a*b^2) + b*Pi < 0 > >> which has a numeric coefficient Pi which is not a rational number. > >> > >> Mathematica has two ways of dealing with nonrational numeric > >> coefficients in CAD. One is to replace each nonrational coefficient > >> with a new variable. This method always allows to decide inference > >> (modulo the ability to zero-test the exact numeric constants), but > >> it is potentially very expensive - CAD has a doubly exponential > >> complexity in the number of variables and we add a new variable for > >> each nonrational coefficient. The second method replaces nonrational > >> numeric coefficients with their approximations. This is much less > >> expensive, but in some cases it fails to decide inference. > >> Simplify uses the second method which in this case is insufficient. > >> > >> FullSimplify uses more transformations, and one of the additional > >> transformations succeeds. > >> > >> Best Regards, > >> > >> Adam Strzebonski > >> Wolfram Research > >> > >> > >> > > > > Thanks for the explanation. I feel I should have guessed it, but there > > is one thing that still puzzles me. What exactly makes the rational > > approximation fail for Pi or E, since it seems to work fine for > > algebraic numbers such as Sqrt[2] or 3^(1/3)? It certainly can't be > > anything to do with Pi or E not being algebraic, so presumably it is > > something to do with the way the rational approximation is chosen? This > > sounds very interesting; could you explain the exact reason why the > > rational approximation in this case doe snot work and in what other > > cases will it not work in general? It sounds like the reason might be > > mathematically interesting (?). > > > > Andrzej Kozlowski > > > > For Pi or E the assumption mechanism uses inexact (bignum) > approximations and constructs CAD with inexact sample point > coordinates. If we have an inequality f(X)<0 and we do not > find a cell with a sample point P for which f(P)<0, but we > do find a cell with a sample point P for which f(P) is > a bignum zero (for instance 0``20) then we cannot tell > whether f(X)<0 has any solutions or not. > > For algebraic numbers the assumption mechanism does not use > approximations. It replaces the algebraic numbers with new > variables, because in this case it does not contribute that > much to the complexity. We do not need to compute projections > wrt. the new variables. Instead we make the variables last in > the projection ordering, and in the lifting phase we only lift > the one-point cell which corresponds to the new variables being > equal to the corresponding algebraic numbers. > > Best Regards, > > Adam Strzebonski > Wolfram Research