Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Re: FullSimplify Hang?
  • Next by Date: Re: FixedPoint
  • Previous by thread: Re: Re: FullSimplify Hang?
  • Next by thread: Re: FullSimplify Hang?