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