Group Abstract Group Abstract

Message Boards Message Boards

Simplify expression to minimize number of multiplications

Posted 5 years ago

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.

POSTED BY: Zak Frentz
8 Replies

Hard to say without seeing a specific representative example. Maybe ExperimentalOptimizeExpression` will suffice.

POSTED BY: Daniel Lichtblau
Posted 5 years ago
POSTED BY: Jim Baldwin
Posted 5 years ago
POSTED BY: Zak Frentz
Posted 5 years ago

To progress further I would have to repeat @DanielLichtblau 's suggestion: a specific example would be helpful.

POSTED BY: Jim Baldwin
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 BY: Daniel Lichtblau
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