16
$\begingroup$

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?

  • 0
    See also http://cs.stackexchange.com/q/23683/755.2016-10-12

5 Answers 5

8

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_k(x_1,\ldots,x_n)=\sum_{1 \leq i_1 $ e_k=\frac1{k!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots&& \ddots & \ddots \\ p_{k-1} & p_{k-2} & \cdots & p_1 & k-1 \\ p_k & p_{k-1} & \cdots & p_2 & p_1 \end{vmatrix} $

  • 1
    @Thomas, a lower Hessenberg matrix like the one in this answer can be decomposed in $O(n^2)$ operations; the determinant is then easily obtained from the triangular factor. Have a look at "Hyman's method", for instance.2016-03-13
5

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$.)

4

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.

  • 0
    How fast is this then? After expanding the $(x_1-\triangle)^{i-1}$ don't you still have to do $O(n^2)$ work?2014-12-14
4

You can compute $\sigma^k_n(x_1,\dots,x_n)$ in $O(n \log^2 k)$ time, using FFT-based polynomial multiplication. The details are explained here and are apparently due to Ben-Or:

https://cstheory.stackexchange.com/a/33506/5038

This is asymptotically faster than any of the other methods proposed in any of the other answers.

Moreover, you can compute all of the values $\sigma^1_n(x_1,\dots,x_n), \sigma^2_n(x_1,\dots,x_n), \dots, \sigma^n_n(x_1,\dots,x_n)$ in just $O(n \log^2 k)$ time, using the same methods.

  • 0
    [A related question.](http://math.stackexchange.com/questions/134212)2017-04-07
2

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$.