MathGroup Archive 2005

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

Search the Archive

Re: Re:Re: FullSimplify with Assumptions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg53449] Re: [mg53435] Re:Re: FullSimplify with Assumptions
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Wed, 12 Jan 2005 03:41:21 -0500 (EST)
  • References: <200501110631.BAA00751@smc.vnet.net> <AC2C4308-63DC-11D9-94CC-000A95B4967A@mimuw.edu.pl>
  • Reply-to: adams at wolfram.com
  • Sender: owner-wri-mathgroup at wolfram.com

Alternatively, one can try FullSimplify with all possible
orderings of chosen variables. Of course, this multiplies
the computation time by Factorial[Length[variables]]...
Here is a simple implementation of a variable order
independent FullSimplify.

In[1]:= VOISimplify[vars_, expr_, assum_:True] :=
    Module[{perm, ee, best},
       perm=Permutations[vars];
       ee=(FullSimplify@@({expr, assum}/.Thread[vars->#]))&/@perm;
       best=Sort[Transpose[{LeafCount/@ee, ee, perm}]][[1]];
       best[[2]]/.Thread[best[[3]]->vars]]

In[2]:= VOISimplify[{x, y}, (L - L*y^2)/x^2, {-1 + x^2 + y^2 == 0}]
Out[2]= L

In[3]:= VOISimplify[{x, y}, (L - L*x^2)/y^2, {-1 + x^2 + y^2 == 0}]
Out[3]= L


Best Regards,
Adam Strzebonski
Wolfram Research

Andrzej Kozlowski wrote:
> 
> On 11 Jan 2005, at 07:31, Goyder Dr HGD wrote:
> 
>> Thank you for your comments on my questions. However, this raises more 
>> questions:
>>
>> 1. What is the mission of FullSimplify? I thought the mission was to 
>> minimise the LeafCount of the expression. Are you are saying that this 
>> is not possible if assumptions are included? If this is not possible 
>> then what can FullSimplify hope to do?
> 
> 
> FullSimplify tries to simplify an expression according to a user 
> specified complexity function and using user specified transformation 
> functions. Of course it uses certain defaults, which are selected 
> because they have been judged most suitable for most users. You can 
> inspect all the options of FullSimplify:
> 
> 
> Options[FullSimplify]
> 
> 
> {Assumptions :> $Assumptions, ComplexityFunction ->
>    Automatic, ExcludedForms -> {},
>   TimeConstraint -> Infinity, TransformationFunctions ->
>    Automatic, Trig -> True}
> 
> As you can see the the default ComplexityFunction and 
> TransformationFunctions are not specified (their value is Automatic) but 
> Adam Strzebonski once posted the code of the default ComplexityFunction 
> to this list. Any way, it is not actually LeafCount but is generally 
> close to LeafCount. But of course the default values are not going to be 
> suitable for most users. If they are not suited to your needs you have 
> to define your own ComplexityFunction and your own 
> TransformationFunctions. Moreover, anything that is included in the 
> defaults will affect the vast majority of users who normally use only 
> default values. It would obviously not be a good idea to choose defaults 
> that might be ideal for one or two users and would cause other users 
> programs to run much slower to no useful purpose.
> 
> Andrzej Kozlowski
> 
> 
>>
>> 2. If I change the input of FullSimplify from an expression to an 
>> assertion to be tested, see below, then it seems to be able to use the 
>> assumptions. Is this always going to be true?
>>
>> In[3]:=
>> InputForm[FullSimplify[(L - L*y^2)/x^2, {-1 + x^2 + y^2 == 0}]]
>>
>> Out[3]//InputForm=
>> (L - L*y^2)/x^2
>>
>> In[4]:=
>> InputForm[FullSimplify[(L - L*y^2)/x^2 == L, {-1 + x^2 + y^2 == 0}]]
>>
>> Out[4]//InputForm=
>> True
>>
> 
> In this kind of cases (purely algebraic ones) it will always be true 
> since in this case the answer is independent of the Groebner basis 
> used.  What you are doing in essentially:
> 
> 
> 
> Last[PolynomialReduce[(L-L*y^2)/x^2-L,{-1+x^2+y^2},{x,y}]]
> 
> 
> 0
> 
> 
> Last[PolynomialReduce[(L-L*y^2)/x^2-L,{-1+x^2+y^2},{y,x}]]
> 
> 
> 0
> 
> and the answer independent of the Groebner basis used even though, as I 
> pointed out earlier:
> 
> 
> Last[PolynomialReduce[(L - L*y^2)/x^2, {-1 + x^2 + y^2},
>    {x, y}]]
> 
> L/x^2 - (L*y^2)/x^2
> 
> 
> Last[PolynomialReduce[(L - L*y^2)/x^2, {-1 + x^2 + y^2},
>    {y, x}]]
> 
> L
> 
>> 3. Why is it so impossible to check all lexical orderings? How would 
>> the time increase with the number of variables and the number of 
>> assumptions? Should this be an option, with warnings and time 
>> constraints?
> 
> 
> It is possible but you have to do it yourself. You can append suitable 
> transformation functions to the default transformation functions.
> 
> 
>>
>> 4. The actual source of my problem was a huge trig function. I had 
>> changed the trig functions into polynomials and the assumption above 
>> was the remains of Sin[t]^2 + Cos[t]^2 == 1. FullSimplify did a lot of 
>> good work before falling at the last hurdle.  How else can one proceed?
> 
> 
> The defaults are meant to be helpful to most people. They are not meant 
> to solve all problems and clearly it would not be possible to to do that 
> no matter what defaults where chosen. When they do not work in your 
> particular situation you have to write your own ComplexityFunction and 
> choose your own TransformationFunctions.
> 
> 
>>
>> Thanks
>>
>> Hugh Goyder
>> -----Original Message-----
>> From: Adam Strzebonski [mailto:adams at wolfram.com]
To: mathgroup at smc.vnet.net
>> Subject: [mg53449] [mg53435] Re: [mg53339] FullSimplify with Assumptions
>>
>>
>> Andrzej Kozlowski wrote:
>>
>>> *This message was transferred with a trial version of CommuniGate(tm) 
>>> Pro*
>>> On 7 Jan 2005, at 12:00, Goyder Dr HGD wrote:
>>>
>>>> In the examples below I would expect FullSimplify to give L.
>>>> However, I get results that depend on the symbols I use.
>>>> It would appear that symbols x and y are treated differently.
>>>>
>>>> How can I force FullSimplify to use the LeafCount as the
>>>> ComplexityFunction?
>>>>
>>>>
>>>> In[14]:= r1 = FullSimplify[(L - L*y^2)/x^2, {-1 + x^2 + y^2 == 0}]
>>>>
>>>> Out[14]= (L - L*y^2)/x^2
>>>>
>>>> In[15]:= r2 = FullSimplify[(L - L*x^2)/y^2, {-1 + x^2 + y^2 == 0}]
>>>>
>>>> Out[15]= L
>>>>
>>>> In[16]:= LeafCount[r1]
>>>>
>>>> Out[16]= 12
>>>>
>>>> In[17]:= LeafCount[r2]
>>>>
>>>> Out[17]= 1
>>>>
>>>> In[18]:= $Version
>>>>
>>>> Out[18]= "5.1 for Microsoft Windows (October 25, 2004)"
>>>>
>>>> Thanks for any comment
>>>>
>>>> Hugh Goyder
>>>>
>>> I would speculate that the reason has something to do with FullSimplify
>>> using PolynomialReduce or related functions, whose outcome depends on
>>> the ordering of the variables. Compare for example:
>>>
>>>
>>> Last[PolynomialReduce[(L - L*y^2)/x^2, {-1 + x^2 + y^2},
>>>    {x, y}]]
>>>
>>>
>>> L/x^2 - (L*y^2)/x^2
>>>
>>> with
>>>
>>>
>>> Last[PolynomialReduce[(L - L*y^2)/x^2, {-1 + x^2 + y^2},
>>>    {y, x}]]
>>>
>>> L
>>>
>>> Note also that if you do not include explicitly the variables you 
>>> will get:
>>>
>>>
>>> Last[PolynomialReduce[(L - L*y^2)/x^2, {-1 + x^2 + y^2}]]
>>>
>>>
>>> L/x^2 - (L*y^2)/x^2
>>>
>>>
>>> I suspect this isn't a bug in FullSimplify. To remedy it FullSimplify
>>> would need to use all possible orderings of variables when applying
>>> algebraic functions whose output depends on variable order, and that is
>>> obviously just not a reasonable option in terms of performance. Also,
>>> Simplify and FullSimplify are not really optimized for conditions of the
>>> form  something == something else; I find it a little surprising that it
>>> works as well as it does. One should really deal with such problems by
>>> using polynomial algebra, that is PolynomialReduce etc, with specified
>>> variable ordering.
>>>
>>>
>>> Andrzej Kozlowski
>>> Chiba, Japan
>>> http://www.akikoz.net/~andrzej/
>>> http://www.mimuw.edu.pl/~akoz/
>>>
>>
>> This is exactly the case.
>>
>> When FullSimplify is given equational assumptions it
>> computes a single Groebner basis of the assumptions
>> (with the DegreeReverseLexicographic monomial order
>> and with the variables ordered by Sort).
>> PolynomialReduce with respect to this Groebner basis
>> is then applied as one of the transformation functions
>> used to simplify subexpressions.
>>
>> Best Regards,
>>
>> Adam Strzebonski
>> Wolfram Research
>>
>>
>>
>>
>> -- 
>> This message has been scanned for viruses and
>> dangerous content by the Cranfield MailScanner, and is
>> believed to be clean.
>>
> 


  • Prev by Date: Re: Re:Re: FullSimplify with Assumptions
  • Next by Date: Mathematica Graphics output in an ASP.NET WebApplication
  • Previous by thread: Re: Re:Re: FullSimplify with Assumptions
  • Next by thread: Re: Mathematica and Visual basic