Re: Re: unable to FullSimplify
- To: mathgroup at smc.vnet.net
- Subject: [mg65893] Re: [mg65872] Re: unable to FullSimplify
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Fri, 21 Apr 2006 01:33:33 -0400 (EDT)
- References: <200604160545.BAA07958@smc.vnet.net> <200604181056.GAA14321@smc.vnet.net> <e24uhn$5s7$1@smc.vnet.net> <200604200914.FAA05331@smc.vnet.net> <7565F0C4-1EBF-4877-8B5D-7ED62DD7011E@mimuw.edu.pl> <083FD578-CB30-4EDE-8875-C2B18B97ED49@mimuw.edu.pl>
- Reply-to: adams at wolfram.com
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej Kozlowski wrote:
> On 20 Apr 2006, at 20:31, Andrzej Kozlowski wrote:
>
>>
>> On 20 Apr 2006, at 18:14, Vladimir wrote:
>>
>>> Andrzej Kozlowski wrote:
>>>
>>>> Well, it seems to me that you are expecting too much.
>>>
>>>
>>> Well, yes, considering the internal simplification and
>>> related code is supposedly thousands of pages long.
>>>
>>>> x + x^4 + 4*x^5 + 6*x^6 + 4*x^7 + x^8
>>>>
>>>> there are just too many different groupings and rearrangements that
>>>> would have to be tried to get to a simpler form.
>>>
>>>
>>> According to documentation, "FullSimplify effectively has to try
>>> combining every part of an expression with every other".
>>
>>
>> Yes, you are right. I wrote that without giving it much thought; my
>> only really significant point was the one about the need to use only
>> complexity decreasing transformations and this still stands.
>>
>>>
>>>> Sometimes the only
>>>> way to transform an expression to a simpler form is by first
>>>> transforming it to a more complex one
>>>
>>>
>>> I'm sure FullSimplify can be improved without the need
>>> for such complexification steps. For example:
>>>
>>> In[]:= subdivide[a_ + b_] := FullSimplify[a] + FullSimplify[b];
>>> FullSimplify[Expand[x + (x + x^2)^4],
>>> TransformationFunctions -> {Automatic, subdivide}]
>>>
>>> Out[]= x + x^4*(1 + x)^4
>>>
>>
>> Well, yes, it works nicely here but the question is, if you make this
>> a default transformation transformation for FullSimplify how will it
>> effect complexity? If you have a sum of n terms you will have to
>> break it up into all possible pairs, then apply FullSimplify to each,
>> and then keep doing this recursively. In fact it even seems hard to
>> see how you would avoid numerous unnecessary attempts at simplifying
>> the same expression... Obviously complexity is a very important
>> consideration i choosing default functions for FullSimplify.
>> Functions like subdivide should be added by users when they see the
>> need for it.
>>
>> Andrzej Kozlowski
>>
>
> Some more thoughts: if your subdivide were really a default
> transformation in FullSimplify it may well lead to an infinite loop,
> since it would be calling on itself. Of course one could avoid this
> problem, but even without recursive calls to itself, subdivide would
> greatly increase the complexity of FullSimplify, which probably would
> become unusable in many istuations where it works fine now. And even
> once you have done that, there woudl stil be cases where a
> simlification exist but there is no route that leads to it by
> complexity reducing transformations (I have posted such examples at
> least two times to this list already). Note however also the folowing
> interesting feature:
>
> u = Expand[x + (x + x^2)^4];
>
>
> FullSimplify[f[u] == f[x + (x + x^2)^4]]
>
> True
>
> Note that even thogugh FullSimplify does not reduce u to x + (x + x^2)
> ^4, it is actually able to determin that f[u] is equal to f[x + (x +
> x^2)^4], for an arbitrary f. To tell the truth, I do not know how it
> does it, perhaps when used in this form it will actually expand the
> argument to f (expanding is generally a form of "complexification")? I
> hope to hear an answer to this, which is the real reason why I am
> writing about this topic again. ;-)
In addition to the simplest form found so far, FullSimplify keeps
a "standard" form of every expression. We do not have a canonical
form for arbitrary Mathematica expressions, but certainly for
rational functions the "standard" form is canonical.
Unfortunately, the standard form is often much larger than
the simplest form, so for instance the ability to cancel
the first two terms in
f[Expr] - f[ExprInAnotherForm] + OtherExpressions
may depend on whether the complexity increase from putting
OtherExpressions in the standard form offsets the complexity
decrease from cancelling the first two terms.
Best Regards,
Adam Strzebonski
Wolfram Research
>
> In fact, it is in general better to use the approach:
>
>
> FullSimplify[f[u] - f[x + (x + x^2)^4]]==0
>
> True
>
> I have posted in the past examples where the former method fails while
> the latter succeeds.
> The ability to show that two expressions are equal is, in my opinion,
> the principal function of FullSimplify, which performs it very well.
> Adding high complexity transformations would not likely improve in this
> respect but may well harm it by making it slower.
>
>
- References:
- unable to FullSimplify
- From: vladimir347@yahoo.com
- Re: unable to FullSimplify
- From: "Vladimir" <vladimir347@yahoo.com>
- Re: unable to FullSimplify
- From: "Vladimir" <vladimir347@yahoo.com>
- unable to FullSimplify