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>