Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.