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
    How would you use Vita to calculate the polynomials? Vita mixes them all up..2014-12-14
  • 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

  • 0
    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...2014-12-14
  • 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
    Apllying $i=2$ gives $\frac12 (x_1x_1 - \Delta x_1)=\frac12 (x_1x_1 - 2 x_2)$, or did I miss something...?2012-12-23
  • 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$.