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