MathGroup Archive 2006

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

Search the Archive

Re: Re: unable to FullSimplify


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 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.



  • Prev by Date: Re: Where do I put my own add-on packages?
  • Next by Date: Re: Re: unable to FullSimplify
  • Previous by thread: Re: unable to FullSimplify
  • Next by thread: Re: Re: unable to FullSimplify