Next: Splice and template Up: An Efficient Symbolic-Numeric Environment Previous: Interactive output

Optimized computational sequences

The package Optimize.m performs syntactic code optimization on Mathematica expressions [30][29]. The term `optimization' is used in the sense of lowering the overall computational cost and not the best possible. Identical common sub-expressions are matched in linear time (O(n) operations) and the strategy is thus very efficient for large expressions. For example, the x+y in (x+y)*f[x+y] is matched, but not in x+y+f[x+y]. Some heuristics such as extraction of numeric coefficients are also performed (see [29] for a fuller discussion).

The following operations are distinguished.

Additionally the option OptimizeCoefficients can be used to include numerical coefficients in Plus and Times as candidates for optimization (the default setting does not to do this since it is less efficient). Distinguishing the above operations enables more efficient optimization of certain types of expressions, by allowing the user some control over the optimization process. The example below illustrates several additional issues. Options of Optimize may be passed to CAssign and FortranAssign. Efficient factoring of exponents in binary form is also possible. 


In[4]:= <<Optimize`;
In[5]:= expr = Tanh[b^5] Sin[a^2] + Tanh[1/b^3] Cos[a^4]/a^5;
In[6]:= FortranAssign[expr,expr,AssignOptimize->True,
          OptimizePower->Binary]
Out[6]//OutputForm=
        o1=a**2
        o2=o1**2
        o3=b**2
        o4=o6**2
        expr=sin(o1)*tanh(b*o4)+cos(o2)*tanh(1/(b*o3))/(a*o2)
The example also demonstrates the relation between reciprocals and powers (1/x^k and x^k) which share the same set of binary factorisations. If Optimize related messages are generated, or optimization fails for some reason, code translation proceeds using the original (unoptimized) expression.

When expressions are polynomials, special factorisations can yield more efficient evaluation. PolynomialQ[poly,var] is a logical test in Mathematica for verification that the expression poly is a polynomial in the variable var. Horner form is the most efficient form of factorisation, when issues of numerical stability are not considered. The factorisation involves additions and multiplications for a polynomial of degree . The procedure Horner is provided in the package Optimize.m for factoring uni-variate and multi-variate polynomials in Horner form. The following example illustrates that when the coefficients are numeric, the routine is able to determine the variable(s) to be factored. 


In[5]:= Horner[ 3 x^2 + 2 x - 1]
Out[5]= -1 + x (2 + 3 x)
The routine is able to determine the variables (using Variables[poly]) whenever the coefficients are numeric. The default ordering is lexicographic, but the user can over-ride this by specifying the variable list explicitly. Because of the highly recursive nature of the nesting of factors, Horner form yields a fairly severe test for code translation routines. The following example shows the behaviour of Mathematica's output formatter, simulating a nested Horner form using Fold. 


In[6]:= nestpoly = Fold[ (#2 + x #1)&, 0 , Range[20] ]
Out[6]=
20 + x (19 + x (18 + x (17 +
           x (16 + x (15 + x
                  (14 + x (13 +
                       x (12 +
                         x (11 +
                         x (10 +
                         x (9 +
                         x (8 +
                         x (7 +
                         x (6 + x (5 + x (4 + x (3 + x (2 + x)))))))))))
                       )))))))
The output is not space-efficient. Furthermore, CForm and FortranForm exhibit similar behaviour since they utilise the same internal code. In contrast, our implementation is able to deal with such difficult examples, even when sub-expression extraction is requested. 

In[7]:= FortranAssign[nestpoly, nestpoly, AssignMaxSize->200]
Out[7]//OutputForm=
        t1=4.d0+x*(3.d0+x*(2.d0+x))
        t2=x*(6.d0+x*(5.d0+t1*x))
        t3=9.d0+x*(8.d0+(7.d0+t2)*x)
        t4=x*(1.1d1+x*(1.d1+t3*x))
        t5=1.4d1+x*(1.3d1+(1.2d1+t4)*x)
        t6=x*(1.6d1+x*(1.5d1+t5*x))
        t7=1.9d1+x*(1.8d1+(1.7d1+t6)*x)
        nestpoly=2.d1+t7*x
Further examples of the use of the code optimization option are provided in the applications section .

bondaren@thsun1.jinr.ru