Optimizing a set of polynomials for computation speed

Question

I have a set of polynomial expressions produced by a computer algebra system (CAS). For example, this is one element of this set.

-d*d*l*l*q-b*b*l*l*q+2*d*f*j*l*q+2*b*f*h*l*q-f*f*j*j*q-b*b*j*j*q+2*b*d*h*j*q-f*f*h*h*q-d*d*h*h*q+b*b*j*j*o*o-2*b*d*h*j*o*o+d*d*h*h*o*o-2*b*b*j*l*n*o+2*b*d*h*l*n*o+2*b*f*h*j*n*o-2*d*f*h*h*n*o+2*b*d*j*l*m*o-2*d*d*h*l*m*o-2*b*f*j*j*m*o+2*d*f*h*j*m*o+b*b*l*l*n*n-2*b*f*h*l*n*n+f*f*h*h*n*n-2*b*d*l*l*m*n+2*b*f*j*l*m*n+2*d*f*h*l*m*n-2*f*f*h*j*m*n+d*d*l*l*m*m-2*d*f*j*l*m*m+f*f*j*j*m*m

I need to execute all of them in a C program, as fast as possible. If you look carefully at any of these formulas, it is obvious that we can optimize them for computation speed. For example, in the polynomial pasted above, I can see immediately the terms -d*d*l*l*q, 2*d*f*j*l*q, and -f*f*j*j*q, so that I could replace their sum by -q*square(d*l-f*j). I believe there are a lot of such things that can be done here. I don't believe (but perhaps am I wrong) that any compiler would be able to find this optimization, or perhaps more advanced ones. I tried to ask maxima (a CAS) to do this for me, but nothing came out (since I am a beginner with maxima, I have perhaps missed a magic command). So, my first question is: what tool/algorithm can we use to optimize a polynomial expression for computation speed?

When it comes to optimize a set of polynomial expressions sharing most of their variables, things become more complicated. Indeed, optimizing expression by expression can be suboptimal because common parts could be identified by the compiler before optimizing but not anymore after if this is not performed as a whole. So, my second question is: what tool/algorithms can we use to optimize a set of polynomial expressions for computation speed?

Best regards,

P.S. : this post shares some similarities with "computer algebra soft to minimize the number of operations in a set of polynomials", however the answers given in that one point to CAS programs instead of saying how we can use them to achieve our goal.

Answer 1

As a first attempt I'd probably try the greedy approach.

So using your first example we start with this:

 -1*d*d*l*l*q
 -1*b*b*l*l*q
  2*d*f*j*l*q
  2*b*f*h*l*q
 -1*f*f*j*j*q
 ...

Now try to find the most repeated pattern in the terms. This is q, which luckily is present in all of them. Let's remove it and that leaves us with

 -1*d*d*l*l
 -1*b*b*l*l
  2*d*f*j*l
  2*b*f*h*l
 -1*f*f*j*j
 ...

Now do the same thing again, this time we get l and the problem splits in two subproblems.

 -1*d*d*l
 -1*b*b*l
  2*d*f*j
  2*b*f*h
  ---------
 -1*f*f*j*j
 ...

Repeat recursively until there's no repetition left and tracing your steps back you can recursively reconstruct a simplified version of the expression:

 q*(l*<first subproblem>+<second subproblem>)

As you can already see, the solution won't necessarily be optimal but it's easy to implement and may be good enough. If you need a better one then you probably need to explore more combinations and rank them according to the number of multiplications you save but the general concept is the same.