Re: Re: unable to FullSimplify

*To*: mathgroup at smc.vnet.net*Subject*: [mg65977] Re: [mg65945] Re: unable to FullSimplify*From*: Adam Strzebonski <adams at wolfram.com>*Date*: Tue, 25 Apr 2006 05:19:08 -0400 (EDT)*References*: <200604160545.BAA07958@smc.vnet.net> <200604181056.GAA14321@smc.vnet.net> <e24uhn$5s7$1@smc.vnet.net> <200604200914.FAA05331@smc.vnet.net> <e29qvc$m59$1@smc.vnet.net> <200604241001.GAA08924@smc.vnet.net> <81DDADBF-5461-4A2E-9F3C-6297C85B0C30@mimuw.edu.pl>*Reply-to*: adams at wolfram.com*Sender*: owner-wri-mathgroup at wolfram.com

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 >

**References**:**unable to FullSimplify***From:*vladimir347@yahoo.com

**Re: unable to FullSimplify***From:*"Vladimir" <vladimir347@yahoo.com>

**Re: unable to FullSimplify***From:*"Vladimir" <vladimir347@yahoo.com>

**Re: unable to FullSimplify***From:*"Vladimir" <vladimir347@yahoo.com>

**Re: Where do I put my own add-on packages?**

**Printing Lists to file without {}**

**Re: Re: unable to FullSimplify**

**Re: unable to FullSimplify**