++++++++++++++++++++++ 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. ###################################################################