title: Efficient (dense) multivariate polynomial multiplication
body: <p>Suppose we have two polynomials, in man variables, but they need not both contain the same variables. But, for the variables a polynomial does contain, it contains all monomials (up to a degree).</p>
  <h3>Example up to degree 2</h3>
  <blockquote>
  <p>Polynomial A: 1+x+y+x^2+xy+y^2</p>
  <p>Polynomial B: 1+e+f+e^2+ef+f^2</p>
  </blockquote>
  <p>Both A and B are of degree 2, and they are both dense, meaning they contain all monomials of their respected variables.</p>
  <p>Note that in the above, the sets of variables A_s=(x,y) and B_s=(e,f) had an empty intersection, but that need not be the case.</p>
  <p>Does anybody know of an efficient algorithm for computing their product? As both polynomials are dense, there must be an algorithm that takes advantage of this fact.</p>
  <p>I have an algorithm, that is efficient, if the above sets of variables A_s == B_s, are equal. The trivial solution of simply expanding the sets, giving zero coeficients, ex.</p>
  <blockquote>
  <p>A: 1+x+y+0e+0f+...</p>
  </blockquote>
  <p>is not a valid one, as one would constantly need to construct new arrays (polynomial representations).</p>