Re: Re: unable to FullSimplify
- To: mathgroup at smc.vnet.net
- Subject: [mg65864] Re: [mg65846] Re: unable to FullSimplify
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 19 Apr 2006 04:54:23 -0400 (EDT)
- References: <200604160545.BAA07958@smc.vnet.net><e1vebv$995$1@smc.vnet.net> <200604181056.GAA14321@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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)
LeafCount[%]
13
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
- References:
- unable to FullSimplify
- From: vladimir347@yahoo.com
- Re: unable to FullSimplify
- From: "Vladimir" <vladimir347@yahoo.com>
- unable to FullSimplify