# Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing the "other" symmetric polynomials.

For instance (I use here the notation $\sigma_n^k$ for the $k$-th symmetric polynomial in $n$ variables), the Vieta formulae allow me to compute a bunch of symmetric polynomials all at once like so:

\begin{align*} &(x+t)(x+u)(x+v)(x+w)\\ &\qquad =x^4+\sigma_4^1(t,u,v,w)x^3+\sigma_4^2(t,u,v,w)x^2+\sigma_4^3(t,u,v,w)x+\sigma_4^4(t,u,v,w) \end{align*}

and, as I have said, $\sigma_4^1$ and $\sigma_4^4$ are trivial to compute on their own without having to resort to Vieta.

But what if I want to compute $\sigma_4^3$ only without having to compute all the other symmetric polynomials? More generally, my application involves a large-ish number of arguments, and I want to be able to compute "isolated" symmetric polynomials without having to compute all of them.

Thus, I'm looking for an algorithm for computing $\sigma_n^k$ given only $k$ and the arguments themselves, without computing the other symmetric polynomials. Are there any, or can I not do better than Vieta?

-
How would you use Vita to calculate the polynomials? Vita mixes them all up.. – Thomas Ahle Dec 14 '14 at 18:43

Let us use the symbols $u_1, u_2, ....$, for the indeterminates $t, u, v, ...$ in the question. The computation will be given in terms of a new set of indeterminates, $x_1, x_2, ....$, whose connection to the original indeterminates is given by:

$x_j = \sum_{i=1}^{n} u_i^j$

We define the derivation operator $\Delta$ acting on the new set of indeterminates as follows:

$\Delta x_j = j x_{j+1}$

$\Delta ab = a \Delta b + b \Delta a$

Then the $i$-th elementary symmetric polynomial is given by:

$\sigma_n^i = \frac{1}{i!}(x_1-\Delta)^{i-1}x_1$

The evaluation is performed in terms of the new indeterminates, after the evaluation, the expressions of the new determinates in terms of the original indeterminates need to be substituted.

-
Apllying $i=2$ gives $\frac12 (x_1x_1 - \Delta x_1)=\frac12 (x_1x_1 - 2 x_2)$, or did I miss something...? – draks ... Dec 23 '12 at 22:53
How fast is this then? After expanding the $(x_1-\triangle)^{i-1}$ don't you still have to do $O(n^2)$ work? – Thomas Ahle Dec 14 '14 at 18:51

You can use Newton-Girard formulae. The elementary symmetric polynomial have representation as determinants: $$p_k(x_1,\ldots,x_n)=\sum_{i=1}^nx_i^k = x_1^k+\cdots+x_n^k \\ e_2(x_1,\ldots,x_n)=\sum_{1 \leq i_1<i_2<...<i_k\leq n}x_{i_1}x_{i_2}\cdots x_{i_k}$$ $$e_n=\frac1{n!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots&& \ddots & \ddots \\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix}$$

-
Do you also have a fast way of computing those determinants? The raw method takes O(n^2.4) operations. I suppose the near symmetry might help? or maybe not? Perhaps it can play into some sampling/approximation algorithm... – Thomas Ahle Dec 14 '14 at 18:37

A simple divide-and-conquer recursion looks like it comes in at $O(nk)$, just like the recurrence given by @BenKuhn. Split the variables into two halves, and inductively compute $\sigma_{n/2}^j$ for $j=0,\ldots,k$ evaluated on both halves. Iterate $r$ times, where $n\approx 2^r k$; the total work required is $2^r$ evaluations of $\{\sigma_k^j\mid 0\le j\le k\}$. But each of these sets can be done in $O(k^2)$ work using Vieta, so the total work is $O(2^r k^2)=O(nk)$.

It's probably worth remarking that you can evaluate $\sigma_n^{n-k}$ by evaluating $\sigma_n^k$ on the reciprocals of the variables. So you're in good shape if $k$ is either very small, or nearly $n$.

-

There's a dynamic programming algorithm that is $O(nk)$ using a recurrence relation. If we define $S_n^k = \sigma_n^k(x_1, \dots, x_n)$, then we have $$S_n^k = S_{n-1}^k + x_n S_{n-1}^{k-1}$$ which allows one to compute $S_n^k$ by filling an $n \times k$ matrix, where (almost) every cell takes constant time to fill.

(The base case is of course $S_n^0 = 1$ for all $n$ and $S_n^k = 0$ for all $n$ and $k \neq 0$.)

-