Optimization of a set of polynomials for computation speed

Question

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

-d * d * l * l * d * b * l * l * d + 2 * d * e * J * l * d + 2 * b * e * h * l * QF * e * J * J * d * b * J * J * Q + 2 * B * d * H * J * QF * e * h * h * QD * d * H * h * d + b * b * J * J * O * o-2 * B * d * H * J * O * O + d * d * H * H * O * O-2 * B * B * J * l * p * o + 2 * B * d * H * l * p * o + 2 * b * e * h * J * n * o-2 * d * e * h * h * n * o + 2 * B * d * J * l * t * o-2 * d * d * h * l * t * o * 2 * b * e * J * J * t * o + 2 * d * e * h * J * t * o + b * b * l * l * n * n-2 * b * e * h * l * p * n + e * e * h * h * n * n-2 * b * d * l * l * t * n + 2 * B * F * J * l * t * n + 2 * d * e * h * l * t * n-2 * e * e * h * J * t * n + d * d * l * l * m * m-2 * d * e * J * l * m * m + f * e * J * J * t * t

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

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

Respectfully,

PS: 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 this section for CAS programs, instead saying how we can use them to achieve our goal.

Answer 1

As a first attempt, I will probably try to use a 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 repeating pattern in terms. This is q , which, fortunately, is present in all of them. Let me remove it and it 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 we do the same, this time we get l , and the problem is divided into two subtasks.

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

Repeat recursively until you repeat the repetition and check your steps back, you can recursively restore the simplified version of the expression:

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

As you can see, the solution will not necessarily be optimal, but it is easy to implement and can be quite good. If you need the best, you probably need to learn more combinations and rank them according to the number of copies you save, but the general concept is the same.