Group Abstract Group Abstract

Message Boards Message Boards

Simplify expression to minimize number of multiplications

Posted 5 years ago
POSTED BY: Zak Frentz
8 Replies
Posted 5 years ago
POSTED BY: Jim Baldwin

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.

POSTED BY: Daniel Lichtblau
POSTED BY: Daniel Lichtblau
Posted 5 years ago

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.

POSTED BY: Zak Frentz
Posted 5 years ago

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

POSTED BY: Zak Frentz
Posted 5 years ago
POSTED BY: Jim Baldwin
Posted 5 years ago
POSTED BY: Zak Frentz
POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard