MathGroup Archive 2000

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

Search the Archive

Re: InequalitySolve with algebraic numbers and Simplify

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23018] Re: [mg22987] InequalitySolve with algebraic numbers and Simplify
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Tue, 11 Apr 2000 23:18:35 -0400 (EDT)
  • Organization: Wolfram Reasearch, Inc
  • References: <8crsqo$2b8@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote:
> 
> on 00.4.9 2:45 PM, Gianluca Gorni at gorni at dimi.uniud.it wrote:
> 
> >
> > Hello!
> >
> > I had a system of *linear* inequalities in two variables x,y,
> > with simple algebraic numbers as coefficients,
> > to solve with InequalitySolve[], and I naively assumed
> > that the solution would be a set of likewise *linear*
> > inequalities. So I was surprised at results like this:
> >
> > Needs["Algebra`InequalitySolve`"]
> >
> > InequalitySolve[{y <= x*Sqrt[2], y <= x}, {x, y}]
> >
> > x <= 0 && y <= -(Sqrt[2]*Sqrt[x^2]) || x > 0 && y <= x
> >
> > Strictly speaking the result is correct, but it does not look
> > good, because of that Sqrt[x^2]. I tried with
> > Experimental`CylindricalAlgebraicDecomposition,
> > but it gives exactly the same answer.

CylindricalAlgebraicDecomposition algorithm works with polynomials
with rational number coefficients. Algebraic numbers are replaced
with new variables, so that the system in your example becomes
y <= a*x && y <= x && a^2 == 0 (and we remember that a is Sqrt[2]),
so it is no longer linear. InequalitySolve does not automatically
simplify its output. 

Here is a (somewhat more general than the one given by Andrzej 
Kozlowski) function which simplifies output of InequalitySolve 
without changing the structure of inequalities.

In[1]:= CADSimplify[a_, assum_] :=
Switch[Head[a],
   And,
   CADSimplify[First[a], assum] && CADSimplify[Rest[a], First[a] &&
assum],
   Or,
   CADSimplify[#, assum]&/@a,
   Inequality|Less|LessEqual|Greater|GreaterEqual|Equal|Unequal,
   Simplify[#, assum]&/@a,
  
_,                                                                              
   a]
 
In[2]:= CADSimplify[a_] := CADSimplify[a, True]
 
In[3]:= x <= 0 && y <= -(Sqrt[2]*Sqrt[x^2]) || x > 0 && y <= x //
CADSimplify
 
Out[3]= x <= 0 && y <= Sqrt[2] x || x > 0 && y <= x  
                           
> >
> > Trying to reduce the results to a more manageable form, I
> > met some somewhat disappointing behaviour of Simplify[]
> > with assumptions (of Mathematica version 4):
> >
> > In:   Simplify[Sqrt[x^2], x == 1 + Sqrt[2]]
> >
> > Out:  Sqrt[x^2]
> >
> > It seems that Mathematica doesn't notice that 1+Sqrt[2] is real and
> > positive! 


Simplify does not attempt to extract variable domain information
from equation assumptions. It would require finding all solutions,
which in general is too time consuming. Possibly FullSimplify
should do it... I am not convinced that Simplify should be 
optimized for assumptions of the form x==constant. I would 
expect that in most cases what one really wants is 
Simplify[expr/.x->constant] 
rather than 
Simplify[expr, x==constant].


> > So let's teach Mathematica that it is real, at least:
> >
> > In:  Simplify[Sqrt[x^2], {Element[x, Reals], x == 1 + Sqrt[2]}]
> >
> > Out: x
> >
> > Somehow I would have expected the answer to be 1+Sqrt[2], what
> > about you? Even if x has a smaller LeafCount than 1+Sqrt[2].

Simplify's objective is to minimize the ComplexityFunction...
Simplify[expr/.x->constant] would give the expected answer.

> >
> > Best regards,
> >
> > Gianluca Gorni
> 
> It seems to me that you have come across some unpleasant quirks in
> Mathematica if not exactly bugs. As for the first one, I don't now exactly
> the cause of it but in general it seems that Mathematica generally has
> problems with expressions like Sqrt[x^2] in logical expressions. For
> example, compare the following behaviour:
> 
> In[1]:=
> And[x < 3, x < 2] // Simplify
> Out[1]=
> x < 2
> 
> In[2]:=
> And[x < 4, x > 5] // Simplify
> Out[2]=
> False
> 
> In[3]:=
> And[x > 3, x^2 < 9] // Simplify
> Out[3]=
> False
> 
> In[4]:=
> And[x > 3, Sqrt[x^2] < 3] // Simplify
> Out[4]=
>                2
> x > 3 && Sqrt[x ] < 3
> 
> That last one should have been false, of course. On the other Simplify with
> assumptions behaves correctly in such cases:
> 
> In[5]:=
> Simplify[x > 3, Sqrt[x^2] < 3]
> 
> Out[5]=
> False
> 

The problem is that there is an underlying assumption in 
Mathematica that all variables represent complex quantities. 
This means that Simplify is not allowed to simplify inequalities 
using the cylindrical algebraic decomposition (CAD) algorithm, 
unless all variables that appear in the inequalities are assumed 
to be real. For instance, one may argue that I is a legitimate 
complex solution of x^2 < 0, while we have

In[5]:= Experimental`CylindricalAlgebraicDecomposition[x^2<0, x]
Out[5]= False    
                                                               
On the other hand, all variables which appear in inequality 
_assumptions_ are automatically assumed to be real, so the 
difference between In[4] and In[5] above is that in In[4] x is 
not assumed to be real, so CAD cannot be used, while in In[5] 
x is assumed to be real, so CAD can be used.

The CAD algorithm is not the only method Simplify may use to
simplify inequalities. It also uses a few heuristics doing
some simple transformations of inequalities. This is how In[1],
In[2], and In[3] above get simplified to False. 

The heuristics use inequality transformations which give equivalent 
formulas in the language of ordered fields. They do not necessarily
give expressions equivalent to the original ones under replacement
of variables with arbitrary complex constants. For instance we have

In[1]:= Simplify[x - y < 0] 
Out[1]= x <
y                                                                   

even though replacing {x -> a + b I, y -> c + b I}, with a<c, 
in x - y < 0 gives True, while in x < y the same replacement
gives an invalid comparison of two complex numbers.
It is somewhat of an inconsistency, but I think it is useful
to have these transformations anyway...



> This makes me feel that it should not be impossible to fix the first problem
> you pointed out. For example one might define a function:
> 
> mysimplify[expr_] :=
>   expr /. And[LessEqual[x_, 0], y_] /; Not[FreeQ[y, x]] :>
>       And[LessEqual[x, 0], Simplify[y, LessEqual[x, 0]]]
> 
> Now,
> 
> In[7]:=
> Experimental`CylindricalAlgebraicDecomposition[{y <= x*Sqrt[2], y <= x},
> {x,y}]
> 
> Out[7]=
>                               2
> x <= 0 && y <= -Sqrt[2] Sqrt[x ] || x > 0 && y <= x
> 
> We can improve this by applying mysimplify
> 
> In[8]:=
> mysimplify[%]
> 
> Out[8]=
> x <= 0 && y <= Sqrt[2] x || x > 0 && y <= x
> 
> gives the kind of answer one would expect. Of course one would need
> something a lot more sophisticated to deal with all the cases in which this
> sort of problem may arise.
> 
> The second one has indeed something to do with the ComplexityFunction.
> Mathematica does indeed give;
> 
> In[9]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}]
> 
> Out[9]=
>       2
> Sqrt[x ]
> 
> Suppose however, we define a complexity function f by:
> 
> cf[expr_] := Count[expr, _?(Not[NumericQ[#]] &), {0, Infinity}]
> 
> Now we notice something curious:
> 
> In[11]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
> 
> Out[11]=
> Sqrt[3 + 2 Sqrt[2]]
> 
> That's a bit weird. If we try FullSimplify (Simplify does not work here!) we
> indeed get:
> 
> In[12]:=
> FullSimplify[%]
> 
> Out[12]=
> 1 + Sqrt[2]
> 
> Why did we not get this answer the first time? Both 1+Sqrt[2] and Sqrt[3 + 2
> Sqrt[2]] have the same value of cf, namely 0, but of course the firs tone
> has much smaller LeafCount. It seems that Simplify never considered the
> simpler answer. 

Simplify uses equation assumptions to PolynomialReduce expressions
w.r.t. a DegRevLex GroebnerBasis of the ideal generated by the
equations. (Of course, this is not the best way of using assumptions
x==constant, but as I mentioned above, Simplify is not optimized
for this special form of assumptions.) We have

In[1]:= PolynomialReduce[Sqrt[x^2], {x-(1 + Sqrt[2])}, {x}][[2]]
 
              2
Out[1]= Sqrt[x ]

no complexity improvement here, so Simplify attempts to simplify
subexpressions
 
In[2]:= PolynomialReduce[x^2, {x-(1 + Sqrt[2])}, {x}][[2]]
 
Out[2]= 3 + 2 Sqrt[2]

This improves the value of cf, so Simplify replaces x^2
with 3 + 2 Sqrt[2], and gets Sqrt[3 + 2 Sqrt[2]] as a new 
form of the whole expression. Now the only way to simplify
this is to use RootReduce, but RootReduce is used only by 
FullSimplify.
                                                           
> This happens even if we modify cf so as to make
> cf[1+Sqrt[2]]  explicitly smaller than cf[Sqrt[3 + 2 Sqrt[2]]:
> 
> In[16]:=
> Clear[cf]
> 
> In[17]:=
> cf[expr_] :=
>   10*Count[expr, _?(Not[NumericQ[#]] &), {0, Infinity}] + LeafCount[expr]
> 
> In[18]:=
> cf[1 + Sqrt[2]]
> 
> Out[18]=
> 7
> 
> In[19]:=
> cf[Sqrt[3 + 2*Sqrt[2]]]
> 
> Out[19]=
> 13
> 
> However:
> 
> In[20]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
> 
> Out[20]=
> Sqrt[3 + 2 Sqrt[2]]
> 
> Fortunately
> 
> In[21]:=
> FullSimplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
> 
> Out[21]=
> 1 + Sqrt[2]
> 
> Note also that with the previous complexity function cf, which is zero on
> both 1+Sqrt[2] and Sqrt[3 + 2 Sqrt[2]]) even FullSimplify chooses the latter
> answer!. All of it does seem weirs and in need of improvement.

The given ComplexityFunction cf is the only criterion FullSimplify 
has for deciding which expression is simpler. It has no reason to 
choose 1+Sqrt[2] instead of Sqrt[3 + 2 Sqrt[2]], unless
cf[1+Sqrt[2]] < cf[Sqrt[3 + 2 Sqrt[2]]].

Best Regards,

Adam Strzebonski
Wolfram Research

> 
> --
> Andrzej Kozlowski
> Toyama International University
> Toyama, Japan


  • Prev by Date: Re: Re: selfdefined operators
  • Next by Date: Needs[] and <<
  • Previous by thread: Re: InequalitySolve with algebraic numbers and Simplify
  • Next by thread: Programming Help. PLEASE (2)