Re: Re: FullSimplify Hang?
- To: mathgroup at smc.vnet.net
- Subject: [mg62219] Re: [mg62213] Re: [mg62184] FullSimplify Hang?
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 16 Nov 2005 02:28:22 -0500 (EST)
- References: <200511140216.VAA23580@smc.vnet.net> <200511150916.EAA22729@smc.vnet.net> <0269D499-FBE8-4BDD-80C3-7F1F468C1F69@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
On 15 Nov 2005, at 19:27, Andrzej Kozlowski wrote:
>
> On 15 Nov 2005, at 18:16, Renan wrote:
>
>> On 11/14/05, Igor Touzov <igor at nc.rr.com> wrote:
>>> I run FullSimplify on expression with LeafCount of 89281. It runs
>>> for 80
>>> hours already , and I have no idea if it ever going to complete.
>>>
>>> Is there any way to estimate its progress % ?
>>
>> I would like also to see this feature in Mathematica.
>> Sometimes, it is rather annoying to not have an "estimated time",
>> esp.
>> considering that many other software give at least a progress bar.
>>
>>> It is possible it just in some king of dead loop?
>>
>> I don't think so; I believe the Mathematica kernel is smart enough to
>> detect this.
>>
>>> It would be nice for Mathematica to have ability to indicate current
>>> progress or possibility to interrupt current simplification and
>>> obtain
>>> intermediate result.
>>
>> []s
>> --
>
>
> I can't even imagine how this could possibly be done. This kind of
> estimation is only possible if the process that is being estimated
> is in some sense uniform. In this case the past can be a rough
> guide to the present. However, FullSimplify or Simplify apply a
> number of entirely unrelated transformation in turn; how could the
> time taken by any of those tried up to a given time be any guide to
> the time that the other ones will take? Even if just only one
> transformation is left, it could be the one that is going to take
> longer than all the ones that have been tried so far put together.
>
> Actually, the issue of "hanging" is spurious one, since
> FullSimplify could easily take longer than your computer will last
> without ever "hanging".
>
> What I would like is something else that should not be impossible.
> At present we can use TimeConstrained to restrict the time taken by
> FullSimplify, but if the simplification fails to be accomplished in
> specified time there is no way, as far as I know, to see the "best
> result obtained so far". One can do that with functions like Nest
> etc, but not with FullSimplify. Since, I think, Simplify must at
> each moment in time store the simplest answer obtained so far, it
> should not be too much to ask that this answer be returned when the
> time specified in TimeConstrained is reached. (If this is possible
> to do now I would love to hear about it!).
>
> Andrzej Kozlowski
>
>
Actually, I have found a way to do this!
Unfortunately my current approach considerably increases the length
of time taken by FullSimplify so much that it is not usable in
practice :-( But it is a start ;-)
I will illustrate the approach on an example. Suppose we would like
to FullSimplify the expression
((1 + Sin[x])*(1 - Cos[x]))/Cos[2*x]
I will first show how to obtain all the forms through into which
FullSimplify simplifies the given expression. (Actually I have posted
this approach a number of times before).
Let's start with an empty list
In[1]:=
ls = {};
Next, we run:
In[2]:=
FullSimplify[((1 + Sin[x])*(1 - Cos[x]))/Cos[2*x], ComplexityFunction ->
((If[FullSimplify[#1 - ((1 + Sin[x])*(1 - Cos[x]))/Cos[2*x]] ==
0, AppendTo[ls, #1]]; LeafCount[#1]) & )]
Out[2]=
(-(Cos[x] - 1))*Sec[2*x]*(Sin[x] + 1)
Let's check how long our list is:
In[3]:=
Length[ls]
Out[3]=
43
However, it includes many repetitions, so we take union and sort it
according to LeafCount:
In[4]:=
ls = Sort[Union[ls], LeafCount[#1] < LeafCount[#2] & ];
In[5]:=
Length[ls]
Out[5]=
13
Let's look at the three best results:
In[6]:=
Take[ls, 3]
Out[6]=
{(-(Cos[x] - 1))*Sec[2*x]*(Sin[x] + 1), (1 - Cos[x])*Sec[2*x]*(Sin[x]
+ 1), (-(1/2))*Sec[2*x]*(2*Cos[x] - 2*Sin[x] + Sin[2*x] - 2)}
No, let's repeat the process using TimeConstrained, to just 0.1 second.
In[13]:=
ls = {};
In[14]:=
TimeConstrained[FullSimplify[((1 + Sin[x])*(1 - Cos[x]))/Cos[2*x],
ComplexityFunction ->
((If[FullSimplify[#1 - ((1 + Sin[x])*(1 - Cos[x]))/Cos[2*x]] ==
0, AppendTo[ls, #1]]; LeafCount[#1]) & )], 0.1]
Out[14]=
$Aborted
Now there are fewer results:
In[15]:=
Length[ls]
Out[15]=
28
and also fewer distinct results:
In[16]:=
ls = Sort[Union[ls], LeafCount[#1] < LeafCount[#2] & ];
In[17]:=
Length[ls]
Out[17]=
9
However, the best three are exactly the same as before.
In[18]:=
Take[ls, 3]
Out[18]=
{(-(Cos[x] - 1))*Sec[2*x]*(Sin[x] + 1), (1 - Cos[x])*Sec[2*x]*(Sin[x]
+ 1), (-(1/2))*Sec[2*x]*(2*Cos[x] - 2*Sin[x] + Sin[2*x] - 2)}
Now some remarks. Firstly, we could use Enter Subsession from the
Kernel/Evaluation menu instead of TimeConstrained, so that we
actually can "interrupt and check for the best result so far".
The big slowdown in performance is the use of FullSImplify in the
code, that is design to return only forms that are equivalent to the
one we are simplifying. Without that we shall obtain also lots of
partial forms, basically anything to which the ComplexityFunction is
applied. Obviously as it stands the code is not practicable since it
is going to be very much slower than applying FullSimplify itself.
However, it should be easy for WRI to produce something working in a
similar way but much more efficient. In fact it may be better to
allow all the partial forms into ls and then select from the list
only those that are equivalent to the original input. They may also
be other improvements that could make this actually practicable.
Andrzej Kozlowski
- References:
- FullSimplify Hang?
- From: "Igor Touzov" <igor@nc.rr.com>
- Re: FullSimplify Hang?
- From: Renan <renan.birck@gmail.com>
- FullSimplify Hang?