MathGroup Archive 2006

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

Search the Archive

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/


  • Prev by Date: Re: why does not the Mathematica kernel seem to 'multi-task' between computations in different windows?
  • Next by Date: labeling latitudes and longitudes in WorldPlot
  • Previous by thread: Re: Re: Locating common subexpressions
  • Next by thread: Re: Locating common subexpressions