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.
>>
>
- References:
- Re:Re: FullSimplify with Assumptions
- From: "Goyder Dr HGD" <h.g.d.goyder@cranfield.ac.uk>
- Re:Re: FullSimplify with Assumptions