Re: Re: unable to FullSimplify
- To: mathgroup at smc.vnet.net
- Subject: [mg65867] Re: [mg65846] Re: unable to FullSimplify
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 19 Apr 2006 04:54:36 -0400 (EDT)
- References: <200604160545.BAA07958@smc.vnet.net><e1vebv$995$1@smc.vnet.net> <200604181056.GAA14321@smc.vnet.net> <07AC3E37-9566-4802-A247-F9D27147EB96@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
On 18 Apr 2006, at 22:15, Andrzej Kozlowski wrote:
>
> 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
I forgot about this one:
> And don't even try higher powers like:
> FullSimplify[Expand[x + (x + x^2)^16]]
> :)
The same trick as above works here too:
FullSimplify[Expand[x + (x + x^2)^16] /. x -> y - 1] /. y -> x + 1
x*(x^15*(x + 1)^16 + 1)
:-)
In fact, in spite of its higher LeafCount, visually it is in some
ways "simpler" than the original input.
Andrzej Kozlowski
- References:
- unable to FullSimplify
- From: vladimir347@yahoo.com
- Re: unable to FullSimplify
- From: "Vladimir" <vladimir347@yahoo.com>
- unable to FullSimplify