Algorithm to compute complete homogeneous symmetric polynomials

Question

Is there any algorithm to compute complete homogeneous symmetric polynomials efficiently? I was able to find algorithm to compute elementary symmetric polynomials.

Example :- a1 = 2, a2 =3 So for this case n = 2 Now suppose we are given a random positive integer m. Let's say m = 2, then, complete homogeneous symmetric polynomial corresponding to n = 2 and m= 2 is $$F_m(x, y) = x^2 + y^2 + x*y $$ $$F_2(2, 3) = 2^2 + 3^2 + 2*3 = 19$$

Answer 1

Here is a method. Is it the most efficient one, I don't know...

A) Let us begin by the case of 2 variables with the concrete example of

$$P(x,y)=a_0x^6+a_1x^5y+cx^4y^2+\cdots a_5xy^5+a_6y^6.\tag{1}$$

(the generalization will be straightforward).

Let us assume that $y \ne 0$ (otherwise, the computation is immediate).

Two steps :

• factorizing $y^6$, we are left with $y^6 Q(x/y)$, where $Q$ is a sixth degree polynomial in the single variable $t=x/y$, then

• evaluate $Q$ using Horner's scheme for example.

B) For a 3 variables polynomial $\sum_{0 \le i,j,k \le 6}a_{i,j,k}x^{i}y^jz^k$,

• factorize $z^6$ : we get $z^6 Q(x,t)$ where $Q$ is a polynomial with variables $x$ and $t=y/z$.

• then apply the method described just before.

C) For $n$ variables, generalize this process in a "recursive way"...

---

Edit : taking account the remarks done, a big simplification occurs. Let us consider again example (1).

$$P(x,y)=(x/y)^6(1+t+t^2+\cdots +t^6)=(x/y)^6 \dfrac{1-t^7}{1-t}$$

Answer 2

I was surprised that I could not find an algorithm in python to compute the complete symmetric homogeneous polynomials so I wrote one. Here is my code. The computation is done recursively. It would be much more efficient in a compiled language.

def CompPoly(a,n):
    #Returns the complete symmetric homogeneous polynomial of degree n and coeffs a
    if(n>1):
        sum=pow(a[0],n)
        if(size(a)>1):
            for i in range(n):
                sum=sum+pow(a[0],i)*CompPoly(a[1:],n-i)
        return sum
    if(n==1):
        return a.sum()
    return 1