++++++++++++++++++++++
Optimizing expressions
++++++++++++++++++++++
There is sometimes a need to improve, or otherwise optimize,
the way in which some expressions are evaluated.
Consider for example an expression like Erf[x]+Erf[x]^2
and the way it is evaluated for a given x. The Erf function
will be evaluated *twice* (Share[] not-with-standing), which
is quite unnecessary in this case. If however we had written
the expression as Block[{e=Erf[x]}, e+e^2], then Erf would
be evaluated just once and that is a slightly more optimized
evaluation.
The package Optimize.m implements a command called Optimize to
automate the above type of expression optimization.
What Optimize does is replace an expression with a HoldBlock
object, which is a device for creating a Block of code that
will be held unevaluated. The idea is that HoldBlock will
ultimately be used inside a function or a Compile definition
etc, where the Hold can be released and the optimized code
inserted.
Here are two simple examples which illustrate a use of Optimize:
f[x_Real] := Optimize[Sin[x] + Cos[Sin[x]]];
and
g = Compile[x, Optimize[Sin[x] + Cos[Sin[x]]]];
In each case Optimize evaluates itself (an Evaluate is not
required, because Optimize insists on that anyway) and optimizes
the expression Sin[x] + Cos[Sin[x]] so as to avoid the unnecessary
double evaluation of Sin[x]. Thus when you call f[2.2] or g[2.2],
the Sin[2.2] will be evaluated just *once* and not twice.
Note that only basic *syntactic* optimization is performed -- in
other words only if two or more sub-expressions have *literally*
the same syntactic form will any optimization take place.
No mathematical knowledge is used in this procedure.
There are only three routines defined in Optimize.m, and here's
what they do:
Optimize[expr] optimizes an expression and returns a HoldBlock object.
An example usage is: Optimize[Sin[x] + Cos[Sin[x]]]
and it returns an object that can be used when defining a function,
for example: f[x_Real] := Optimize[Sin[x] + Cos[Sin[x]]];
or it can be used as an argument inside Compile or Function as in:
g = Compile[x, Optimize[Sin[x] + Cos[Sin[x]]]];.
An optimized object can also be evaluated directly using
Normal or ReleaseHold as in:
Normal[Optimize[Sin[x] + Cos[Sin[x]]] /. x->2.2].
HoldBlock[vars, body] represents an optimized expression.
The commands SetDelayed, Compile, Function, Normal and ReleaseHold
all know about HoldBlock and will convert it to Block as necessary.
Cost[expr] estimates the cost of evaluating an expression by simply
counting the number of basic elementary operations that are used.
An example usage is: Cost[Sin[x] + Cos[Sin[x]]] which returns
Cos + Plus + 2*Sin. Cost also works with optimized objects, so
if you apply (Cost[#] - Cost[Optimize[#]])& to an expression,
you will see the operations that might be saved.
And here are some simple input examples for you to try:
Needs["Optimize`"];
expr = Nest[(#+Sin[#])&, x, 10];
f1[x_Real] := Optimize[expr];
f2 = Compile[x, Optimize[expr]];
Plot[expr//Evaluate, {x, 0, 0.01}];//Timing (* 2.3 Seconds *)
Plot[f1[x], {x, 0, 0.01}];//Timing (* 0.6 Seconds *)
Plot[f2[x], {x, 0, 0.01}];//Timing (* 0.1 Seconds *)
?f1
expr = Expand[(Sin[x*y] + ArcTan[x] + Log[x] + Cosh[x^-y]^5)^10];
oexpr = Optimize[expr];
(expr /. {x->1.1, y->0.5})//Timing (* 1.0 Seconds *)
Normal[oexpr /. {x->1.1, y->0.5}]//Timing (* 0.3 Seconds *)
{Cost[expr], Cost[oexpr]}
Optimize[z /. Solve[z^4 - 12*z^3 - 16*z^2 + 4*z + c == 0, z]]
expr = Sum[(Sin[x] + Cos[Sin[x]])^n, {n,1,10}];
{Cost[expr], Cost[Optimize[expr]]}
There is one slight caveat with using Optimize. It doesn't understand
about expressions that contain anything with a HoldAll (or HoldFirst
or HoldRest) attribute. Tweak the source code yourself if you
desparately need to optimize such objects.
Terry Robb
October 1993.
###################################################################
Dr Terry Robb Email: tdr@vaxc.cc.monash.edu.au
Department of Mathematics Phone: +61 (3) 565-5666
Monash University Fax : +61 (3) 565-4403
Clayton 3168, Melbourne, AUSTRALIA.
###################################################################