# minimizing multiplications in computing a polynomial expression

I am looking for an algorithm which presents a given polynomial in many variables (given as a sum of monomials) in a form with the smallest number of multiplications of variables. For example $x_1^2x_3+x_1x_2+x_1x_3x_4 \to x_1(x_2+x_3(x_1+x_4)).$

Of course, one could consider some "dumb" approach testing all possibilities, but I am curious if there is a faster one. I need to do it for over 100,000 of polynomials in over 40 variables each.

-
How big do the degrees get? – Qiaochu Yuan Aug 4 '12 at 4:07
degrees of polynomials are around 20 – Adam S Sikora Aug 4 '12 at 17:39

Let $x_1, x_2, \ldots, x_n$ be called "characters".

Re-construct the polynomial as a series of "atoms" separated by addition/subtraction operations.

For each character, count the number of atoms in which it appears. Group the atoms in which each character appears, and factor out the character. Repeat recursively.

If $n$ is your number of characters, and $m$ is the maximal degree, this algorithm should be $\mathcal{O}(n^2m)$. In practice, you should get better than that as long as your polynomials aren't very complicated.

I don't know if this is optimal. But it is an algorithm.

Edit:

Actually, upon further reflection, I believe this could be implemented very similarly to a depth-first search algorithm, in which case you could consider $x_1^m$ to be $m$ characters, and perhaps consider each character a node, possibly meaning that the total order would be $\mathcal{O}(mn)$. However, it is currently far too late for me to better analyze this approach; it would be greatly appreciated if these musings could be verified.

-
Thanks Ed. I presume your "atom" means a monomial. As you mentioned the problem is that it is not clear if your approach gives the least number of multiplications. – Adam S Sikora Aug 4 '12 at 17:23