Algorithm(s) para calcular un polinomio simétrico elemental

Question

Me he topado con una aplicación en la que tengo que calcular un montón de primaria simétrica polinomios. Es trivial para calcular la suma o el producto de las cantidades, de curso, así que mi preocupación es con la informática, los "otros" simétrica polinomios.

Por ejemplo (yo uso aquí la notación $\sigma_n^k$ $k$- ésimo polinomio simétrico en $n$ variables), las fórmulas de Vieta me permiten calcular un montón de polinomios simétricos todos a la vez, así:

$$\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*}$$

y, como he dicho, $\sigma_4^1$ $\sigma_4^4$ son triviales para calcular por su propia cuenta sin tener que recurrir a la Vieta.

Pero lo que si quiero calcular $\sigma_4^3$ sólo sin tener que calcular todos los otros polinomios simétricos? Más en general, mi aplicación implica un gran ish número de argumentos, y quiero ser capaz de calcular "aislado" simétrica polinomios sin tener que calcular todos ellos.

Por lo tanto, estoy en busca de un algoritmo para el cálculo de $\sigma_n^k$ sólo $k$ y los argumentos, sin cómputo de los otros polinomios simétricos. Hay, o no puedo hacerlo mejor que Vieta?

Answer 1

Hay un algoritmo de programación dinámico que es $O(nk)$ utilizando a una relación de recurrencia. Si definimos $S_n^k = \sigma_n^k(x_1, \dots, x_n)$, entonces tenemos $$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$ matriz, donde (casi) cada célula toma tiempo constante para llenar.

(El caso base es por supuesto $S_n^0 = 1$ % todo $n$y $S_n^k = 0$ % todo $n$y $k \neq 0$.)

Answer 2

Usted puede utilizar Newton-Girard fórmulas. La primaria simétrica polinomio tiene representación como factores determinantes: $$ 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} $$

Answer 3

Vamos a usar los símbolos $u_1, u_2, ....$, para el indeterminates $t, u, v, ...$ en la pregunta. El cálculo será dada en términos de un nuevo conjunto de indeterminates, $x_1, x_2, ....$, cuya conexión a la original indeterminates está dada por:

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

Definimos el operador de derivación $\Delta$ que actúa sobre el nuevo conjunto de indeterminates de la siguiente manera:

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

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

A continuación, el $i$-th primaria simétrica polinomio está dado por:

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

La evaluación se realiza en términos de la nueva indeterminates, después de la evaluación, las expresiones de las nuevas variedades determinadas, en términos de la original indeterminates necesitan ser sustituidos.

Answer 4

Un simple de dividir y conquistar la recursividad se ve como se llega a las $O(nk)$, al igual que la recurrencia dada por @BenKuhn. Dividir las variables en dos mitades, y de manera inductiva calcular $\sigma_{n/2}^j$ $j=0,\ldots,k$ evaluados en ambas mitades. Recorrer $r$ veces $n\approx 2^r k$; el trabajo total requerido es de $2^r$ evaluaciones de $\{\sigma_k^j\mid 0\le j\le k\}$. Pero cada uno de estos conjuntos puede ser hecho en $O(k^2)$ trabajo utilizando Vieta, de modo que el trabajo total es:$O(2^r k^2)=O(nk)$.

Es probablemente vale la pena comentar que se puede evaluar el $\sigma_n^{n-k}$ evaluando $\sigma_n^k$ en los recíprocos de las variables. Así que usted está en buena forma si $k$ es muy pequeño, o casi $n$.