MathGroup Archive 2006

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

Search the Archive

Re: Re: unable to FullSimplify

On 18 Apr 2006, at 19:56, Vladimir wrote:

> Andrzej Kozlowski wrote:
>> This seems to me to be an unfortunate consequence of the fact that
>> the outcome of FullSimplify (and Simplify)  depends on the ordering
>> of the variables. This is because a variable order independent
>> Simplify has very much higher complexity and will get stuck on a
>> complicated expressions. Some time ago Adam Strzebonski of WRI sent
>> the following implementation of order independent FullSimplify:
>> 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]]
> Looks rather interesting! Hmm, it's even possible to enhance it  
> further
> to extract variables from a given expression automatically...
> Unfortunately, ordering of the variables isn't the only problem:
> FullSimplify[Expand[x + (x + x^2)^4]]
> x + x^4 + 4*x^5 + 6*x^6 + 4*x^7 + x^8
> whose LeafCount is a whopping 23 instead of expected 9.
> And don't even try higher powers like:
> FullSimplify[Expand[x + (x + x^2)^16]]
> :)
> My confidence in FullSimplify and Mathematica is slowly fading,
> which is rather sad, because my current research heavily depends on
> understanding returned symbolic solutions which can be too hard
> when any simplification opportunities are missed.
> --
> Vladimir

Well, it seems to me that you are expecting too much. Starting with  
an expression like

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.
Moreover, Mathematica will only apply a transformation is it  
immediately leads to an decrease in complexity. Sometimes the only  
way to transform an expression to a simpler form is by first  
transforming it to a more complex one, for example by adding a term  
to one part of the expression and at the same time subtracting it  
from another. Mathematica will never attempt such transformations. I  
think that in general it will only move from one form to another if  
there is a sequence of transformations using the specified  
transformation functions, each of which decreases the complexity.  
That must leave many situations where no such sequence can be found  
yet the expression itself can be simplified.
Basically whenever we deal with situations where there is no  
universal algorithm but only a collection of heuristic or "ad hoc"  
techniques, you should expect this sort of situations to arise. In  
such cases it often happens that by rearranging the input only  
slightly one can make some progress. For example, in your case, the  
first thing I tired was:

FullSimplify[Expand[x + (x + x^2)^4] /. x -> y - 1] /. y -> x + 1

x*(x^3*(x + 1)^4 + 1)



Not quite as good as 9 but better than 23. Note, however, that the  
transformations that where used (substituting y-1 for x) were  
(temporarily) complexity increasing and I think Mathematica never  
uses such transformations.

Andrzej Kozlowski

  • Prev by Date: Re: Re: Problem with limiits
  • Next by Date: Re: Re: unable to FullSimplify
  • Previous by thread: Re: unable to FullSimplify
  • Next by thread: Re: Re: unable to FullSimplify