I have a large number of rather complicated functions of a large number of variables. All functions are polynomials. I am wondering how to use Mathematica to simplify these expressions so as to minimize the number of multiplications. Neither Simplify nor FullSimplify seems to do this, at least not with the default rules for simplification.
If you are evaluating the polynomials multiple times, then storing those after applying HornerForm might save execution time.
Here is an example with 10,000 executions:
z = RandomVariate[UniformDistribution[{0, 1}], 10000];
p = HornerForm[(11 x^3 - 4 x^2 + 7 x + 2)/(x^2 - 3 x + 1)]
(* (2 + x (7 + x (-4 + 11 x)))/(1 + (-3 + x) x) *)
AbsoluteTiming[p /. x -> # & /@ z;]
(* {0.0726247, Null} *)
AbsoluteTiming[(11 x^3 - 4 x^2 + 7 x + 2)/(x^2 - 3 x + 1) /. x -> # & /@ z;]
(* {0.119925, Null} *)
That’s about a 40% time savings for this example.
Hard to say without seeing a specific representative example. Maybe ExperimentalOptimizeExpression` will suffice.
Hi Jim, thanks for your suggestion. It’s along the right lines, and I wasn’t aware of this idea. One issue is that the Horner form of a multivariate polynomial depends on the order of the variables, and this introduces severe inefficiencies for the types of expressions I have.
My approach, which is nearly working, is to define a complexity function that counts the number of multiplications and adds it to the number of exponentiations. For technical reasons, the only exponents that can appear in the expressions are 2, so these “look like” multiplications in terms of my goal, which is to minimize the number of multiplications.
One weird thing is that FullSimplify does seem to find the global minimum for my custom complexity function when applied to shorter expressions, but for larger expressions it doesn’t come close. What’s funny is that if I manually improve the expression in terms of the complexity function, FullSimplify applied to the result returns the manual solution. In other words, it seems that the search algorithm in FullSimplify is not working well. Is there any way to improve its performance?
For reference, the expressions are functions of 39 real variables, and the fully expanded polynomial is a sum over about 100 terms.
To progress further I would have to repeat @DanielLichtblau 's suggestion: a specific example would be helpful.
OK, you asked for it…
myexpression=2 (p3 x12 x20 x25 - p3 x13 x20 x25 + p3 x13 x25^2 - p3 x12 x20 x26 +
p3 x13 x20 x26 - p3 x12 x25 x26 - p3 x13 x25 x26 + p3 x12 x26^2 +
x12 x20 x25 x27 - x13 x20 x25 x27 + x13 x25^2 x27 -
x12 x20 x26 x27 + x13 x20 x26 x27 - x12 x25 x26 x27 -
x13 x25 x26 x27 + x12 x26^2 x27 - 2 x12 x14 x25 x33 +
2 x13 x14 x25 x33 + 2 x1 x25^2 x33 - 2 x13 x25^2 x33 +
2 x12 x14 x26 x33 - 2 x13 x14 x26 x33 - 4 x1 x25 x26 x33 +
2 x12 x25 x26 x33 + 2 x13 x25 x26 x33 + 2 x1 x26^2 x33 -
2 x12 x26^2 x33 + x12 x14 x20 x38 - x13 x14 x20 x38 -
x13 x14 x25 x38 - 2 x1 x20 x25 x38 + 2 x13 x20 x25 x38 -
x12 x14 x26 x38 + 2 x13 x14 x26 x38 + 2 x1 x20 x26 x38 -
x12 x20 x26 x38 - x13 x20 x26 x38 + 2 x1 x25 x26 x38 -
x13 x25 x26 x38 - 2 x1 x26^2 x38 + x12 x26^2 x38 -
x12 x14 x20 x39 + x13 x14 x20 x39 + 2 x12 x14 x25 x39 -
x13 x14 x25 x39 + 2 x1 x20 x25 x39 - x12 x20 x25 x39 -
x13 x20 x25 x39 - 2 x1 x25^2 x39 + x13 x25^2 x39 -
x12 x14 x26 x39 - 2 x1 x20 x26 x39 + 2 x12 x20 x26 x39 +
2 x1 x25 x26 x39 - x12 x25 x26 x39 +
p1 (p3 (-x20 + x25) (x25 - x26) - x20 x25 x27 + x25^2 x27 +
x20 x26 x27 - x25 x26 x27 + 2 x14 x25 x33 - 2 x25^2 x33 -
2 x14 x26 x33 + 2 x25 x26 x33 - x14 x20 x38 - x14 x25 x38 +
2 x20 x25 x38 + 2 x14 x26 x38 - x20 x26 x38 - x25 x26 x38 -
p2 (p3 (x20 - 2 x25 + x26) - (2 x25 - x26) (x27 - 2 x33) +
x20 (x27 - 2 x38) + x26 x38 + x14 (-2 x33 + x38)) -
p2 (x14 + x20 - 2 x25) x39 + (x14 - x25) (x20 - x25) x39 +
p2^2 (p3 + x27 - 2 x33 + x39)) - (x25 - x26) (p3 (x25 - x26) +
x26 (-x27 + x38) + x25 (x27 - x39) + x14 (-x38 + x39)) x7 +
p2^2 (2 x1 (x33 - x39) +
x13 (p3 + x27 - 2 x33 + x39) + (-p3 - x27 + x39) x7) +
p2 (-x13 x20 x27 + 2 x13 x25 x27 - x13 x26 x27 + 2 x13 x14 x33 +
4 x1 x25 x33 - 4 x13 x25 x33 - 4 x1 x26 x33 + 2 x13 x26 x33 -
x13 x14 x38 - 2 x1 x20 x38 + 2 x13 x20 x38 + 2 x1 x26 x38 -
x13 x26 x38 - x13 x14 x39 + 2 x1 x20 x39 - x13 x20 x39 -
4 x1 x25 x39 + 2 x13 x25 x39 + 2 x1 x26 x39 +
x12 (x20 (x27 - x39) - 2 x14 (x33 - x39) -
x26 (x27 - 2 x33 + x39)) - (x25 (2 x27 - 2 x39) +
x14 (-x38 + x39) + x26 (-2 x27 + x38 + x39)) x7 +
p3 (x12 (x20 - x26) - x13 (x20 - 2 x25 + x26) -
2 (x25 - x26) x7)));
myt[x_, oper_ : Times] :=
Tr[Map[(Length[#] - 1) &,
Flatten[Extract[x, {Drop[#, -1]}] & /@ Position[x, oper]]]];
myc[x_] := myt[x, Times] + myt[x, Power];
myexpression2 =
FullSimplify[myexpression, ComplexityFunction -> myc,
TimeConstraint -> {Infinity, Infinity}];
myc[myexpression2] (* 386 *)
The number of multiplications can be reduced easily by hand, although it is not so easy to find the global minimum. I’m wondering if it is possible to tweak the search parameters of FullSimplify, since it is performing very well for somewhat shorter expressions…
In this example it seems that the tandem of HornerForm and ExperimentatOptimizeExpression` will do something useful.
Here is the multiplication count for the expression. After applying HornerForm it is about the same.
In[61]:= Total[Cases[myexpression, a_Times :> Length[a], Infinity]]
Out[61]= 521
But…
oex =
Experimental`OptimizeExpression[HornerForm@myexpression,
"OptimizationLevel" -> 2, "OptimizationSymbol" -> C$];
Now it is cut more than in half.
In[65]:= Total[Cases[oex, a_Times :> Length[a], Infinity]]
Out[65]= 238
This might or might not work well for other examples.
Hi Daniel - thanks, this is very helpful. Is there a simple way to convert the expression from OptimizeExpression back to one in terms of the original variables? I’ve followed the instructions from this thread on how to convert to, for example, C code, but the result appears to be incorrect numerically.
The OptimizedEzpression object requires those new variables in order to support CSE (Common Subexpression Elimination). Any conversion would destroy that feature, thu losing any gain made in terms of lessening the number of multiplications and other operations.