Re: Re: Locating common subexpressions
- To: mathgroup at smc.vnet.net
- Subject: [mg69859] Re: [mg69471] Re: [mg69429] Locating common subexpressions
- From: "Chris Chiasson" <chris at chiasson.name>
- Date: Tue, 26 Sep 2006 00:59:15 -0400 (EDT)
- References: <200609121052.GAA04126@smc.vnet.net> <200609130802.EAA18395@smc.vnet.net> <acbec1a40609230638t71fcf18fmf697de9eeab5c86a@mail.gmail.com>
Hrm, I really like this setup: In[1]:= a=Table[Random[],{2},{2}] Out[1]= {{0.0874247,0.717542},{0.140678,0.925907}} In[2]:= b=SparseArray[a] Out[2]= SparseArray[<\[InvisibleSpace]4\[InvisibleSpace]>,{2,2}] In[3]:= c=Experimental`OptimizeExpression[b] Out[3]= Experimental`OptimizedExpression[ SparseArray[<\[InvisibleSpace]4\[InvisibleSpace]>,{2,2}]] In[4]:= Normal[c] Out[4]= SparseArray[<\[InvisibleSpace]4\[InvisibleSpace]>,{2,2}] Normal doesn't go all the way down to a plain data type. It only strips one level of "specialization". I think this could be useful for manipulating a complicated symbolic matrix with a lot of zeros, where one might want to have fast evaluation (via Normal@ReplaceAll[matrix,reps]) of the symbolic components, but also want to keep the SparseArray object for a call to LinearSolve. Good job :-] On 9/23/06, Chris Chiasson <chris at chiasson.name> wrote: > I'm curious: > > does OptimizationLevel->2 produce any substantial difference from it's > default value of 1? > > I ask because I wasn't able to detect any difference visually, but I > also wasn't able to do a part by part comparison using MatchQ, > Extract, and Position because OptimizeExpression seems to ignore me if > I decrease $ModuleNumber. > > (usually I use MatchQ[Extract[xpr1,#],Extract[xpr2,#]]&/@Position[xpr1,_] > when the expressions are almost identical to see where they differ, > but the different temporary variable names make this difficult) > > > On 9/13/06, Daniel Lichtblau <danl at wolfram.com> wrote: > > carlos at colorado.edu wrote: > > > The strangest thing about the behvior of Simplify in my > > > previous post can be seen at a glance: > > > > > > R = (3 + 3*a^2 + Sqrt[5 + 6*a + 5*a^2] + a*(4 + Sqrt[5 + 6*a + > > > 5*a^2]))/6 > > > R = Simplify[R,a>=0] > > > (3 + 3*a^2 + Sqrt[5 + 6*a + 5*a^2] + a*(4 + Sqrt[5 + 6*a + 5*a^2]))/6 > > > > > > The subexpression Sqrt[5 + 6*a + 5*a^2] is not located. Ideally > > > Simplify should right away replace that by a temp, say t$, and > > > get to work on > > > > > > (3 + 3*a^2 + t$ + a*(4 + t$))/6 > > > > > > where from the assumptions, t$>0 and real. Of course the leaf count > > > of t$ should influence subsequent transformations. > > > This initial pass is useful in complicated expressions that come, eg, > > > from an equation solver since messy subexpressions like the > > > discriminant may appear in several places. I had some of those > > > with leaf counts in the tens of thousands. > > > > > > Locating common subs is of course an key task of optimizing > > > compilers. Simplification and compilation share some objectives, > > > although compilers have to deal with timing and side effects. In fact > > > I wouldnt mind at all if Simplify would return a compound expression: > > > > > > Block [{t$}, t$=Sqrt[5 + 6*a + 5*a^2]; (3 + 4*a + 3*a^2 + (1 + > > > a)*t$)/6 ] > > > > > > since this is perfect for documentation, or conversion to low-level > > > code. > > > > If you want CSE you can use OptimizeExpression in Experimental` context. > > > > In[8]:= InputForm[Experimental`OptimizeExpression[(3 + 3*a^2 + Sqrt[5 + > > 6*a + 5*a^2] + a*(4 + Sqrt[5 + 6*a + 5*a^2]))/6]] > > > > Out[8]//InputForm= > > Experimental`OptimizedExpression[Block[{$$25, $$27, $$28, $$29, $$30}, > > $$25 = a^2; $$27 = 6*a; $$28 = 5*$$25; $$29 = 5 + $$27 + $$28; > > $$30 = Sqrt[$$29]; (3 + 3*$$25 + $$30 + a*(4 + $$30))/6]] > > > > This sort of thing is not a part of the Simplify "charter", but is very > > much the intent of OptimizeExpression. As you might suspect, this is > > meant for reforming expressions prior to conversion to lower level > > languages such as C or the byte code of Mathematica's Compile virtual > > machine. > > > > > > Daniel Lichtblau > > Wolfram Research > > > > > > > -- > http://chris.chiasson.name/ > -- http://chris.chiasson.name/
- References:
- Locating common subexpressions
- From: carlos@colorado.edu
- Re: Locating common subexpressions
- From: Daniel Lichtblau <danl@wolfram.com>
- Locating common subexpressions