WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2006

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

Search the Archive

Re: Re: unable to FullSimplify

Andrzej Kozlowski wrote:
> *This message was transferred with a trial version of CommuniGate(tm) Pro*
> 
> On 24 Apr 2006, at 19:01, Vladimir wrote:
> 
>> Andrzej Kozlowski wrote:
>>
>>>> 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?
>>
>>
>> Some option to FullSimplify would be enough for this to be used only
>> when needed. Anyway, it was just one quick and arbitrary example
>> to show that FullSimplify can be improved without too much effort
>>
>>
>>> In fact it even seems hard to see how you would avoid numerous
>>> unnecessary attempts at simplifying the same expression...
>>
>>
>> That's quite normal it seems. For example, to simplify just a+b,
>> ComplexityFunction is called 28 times(!) Here's a proof:
>>
>> reveal[expr_] := (Print[expr]; LeafCount[expr])
>> FullSimplify[a + b, ComplexityFunction -> reveal]
>>
>>
>>> 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.
>>
>>
>> Are you sure? This subdivide reduces its argument on each
>> invocation so I don't see how infinite loop can be possible.
>> I couldn't find any examples with such a problem.
>>
>>
>>> Note however also the folowing interesting feature:
>>>
>>> u = Expand[x + (x + x^2)^4];
>>>
>>> FullSimplify[f[u] == f[x + (x + x^2)^4]]
>>>
>>> True
>>
>>
>> Well, since f[a]==f[a] evaluates to True, Mathematica simplifies
>> the above equation because it is able to prove equality of f's
>> arguments.
>>
>> -- 
>> Vladimir
>>
> 
> As far as I can tell your last statement is vacuous; it essentially  
> says : it happens because it happens. The true reason is actually  quite 
> complicated, as was explained in Adam Strzebonski's post. I am  amazed 
> you missed or ignored his reply to this thread since he posted  it to 
> the list and also sent to you personally. Also, you can trust  him in 
> this matter much more than me or anyone else, since not only  is he the 
> programmer of FullSimplify, but also a very good  mathematician and an 
> expert in exactly the kind of mathematics that  FullSimlify relies on. 
> Since he also did not choose to contradict my  other points I think they 
> are basically correct, except perhaps the  one about the possibility of 
> an infinite loop. (I thought that your  transformation together with 
> some other transformation used by  FullSimplify might result in an 
> infinite loop, but I have not been  able to  find any obvious example).

FullSimplify uses a caching-based mechanism for preventing infinite
loops coming from recursive calls to FullSimplify with the same input.

In[1]:= f[x_] := FullSimplify[x,
    TransformationFunctions -> {Automatic, f}]

In[2]:= FullSimplify[Expand[(x + x^2)^4],
    TransformationFunctions -> {Automatic, f}]

          4        4
Out[2]= x  (1 + x)

> 
> Of course some things are not a matter of mathematics or programming  
> but simply design decisions. One of these is that FullSimplify has  
> Automatic as the only built in value for the option  
> TransformationFunctions with other values being left to the user. It  
> might be that one could add one or two collections of particularly  
> useful but high time complexity transformations for some specific  
> purposes. I am sure however that not doing so was a carefully  
> considered decision.

Usefulness of a particular transformation heavily depends on
the expression being simplified. In my opinion TransformationFunctions
option is most useful for adding very specific transformations that
are based on user's knowledge of the problem at hand.

For instance, the function subdivide proposed by Vladimir is useful
for simplifying Expand[x + (x + x^2)^4]. But it works only if removing
the first element of a sum makes the expression easier to simplify.
If we change the problem slightly, so that the "extra term" does not
come first in the standard ordering of Plus, the transformation does
not help.

In[1]:= subdivide[a_ + b_] := FullSimplify[a] + FullSimplify[b];

In[2]:= FullSimplify[Expand[x^9 + (x + x^2)^4],
            TransformationFunctions -> {Automatic, subdivide}]

          4    5                         2
Out[2]= x  + x  (4 + x (6 + x (4 + x + x )))

Now, we can choose many transformations that would simplify this
expression, and their complexity depends on how much we know about
the structure of the input. If we know that removing the last term
will give us a power of a sum we can use a relatively inexpensive
but quite specialized trnsformation.

In[3]:= subdivide1[a_Plus] := FactorSquareFree[Drop[a, -1]]+a[[-1]]

In[4]:= FullSimplify[Expand[x^9 + (x + x^2)^4],
            TransformationFunctions -> {Automatic, subdivide1}]

          9    4        4
Out[4]= x  + x  (1 + x)

A less specialized but much more expensive option is to use
FullSimplify recursively on all subsets of sums.

In[5]:= subdivide2[a_Plus] :=
    Sort[{LeafCount[#], #}&/@
       (FullSimplify[Plus@@#] + FullSimplify[Plus@@Complement[List@@a, 
#]]&/@
        Subsets[List@@a])][[1, 2]]

In[6]:= FullSimplify[Expand[x^9 + (x + x^2)^4],
            TransformationFunctions -> {Automatic, subdivide2}]

          9    4        4
Out[6]= x  + x  (1 + x)

But this has a really huge complexity, and it still doesn't help
if we again slightly change the problem so that the extra term
combines with one of the terms coming from the expansion of
(x + x^2)^4.

In[7]:= FullSimplify[Expand[x^4 + (x + x^2)^4],
            TransformationFunctions -> {Automatic, subdivide2}]

          4
Out[7]= x  (2 + x (2 + x) (2 + x (2 + x)))

Of course one could easily write a transformation simplifying the last
expression, given the knowledge that it is a power of a binomial plus
one term...

Best Regards,

Adam Strzebonski
Wolfram Research

> Finally, I must say I am not a little shocked that anyone can believe  
> that FullSimplify could be improved so easily, but as I do not get  paid 
> to argue about this, I will leave it at that ...
> 
> Andrzej Kozlowski
>
  • Prev by Date: Re: Where do I put my own add-on packages?
  • Next by Date: Printing Lists to file without {}
  • Previous by thread: Re: Re: unable to FullSimplify
  • Next by thread: Re: unable to FullSimplify