0
$\begingroup$

The Newton-Girard recursions evidently give a fast algorithm for computing the elementary symmetric polynomials $e_d(x_1,\ldots,x_n):=\sum_{1\leq k_1<\cdots <k_d\leq n} x_{k_1}\cdots x_{k_d}$ in terms of power polynomials $p_d(x_1,\ldots,x_n) :=\sum_{k=1}^n x_k^d$. I am looking for an extension to summations over monomials indexed by a matrix, where the index ordering is enforced separately over each dimension.

Let $x:=\{x_{a,b}: a=1,\ldots A; b = 1,\ldots B\}$ be a two-dimensional array of variables. I want an extension of Newton-Girard (or some other fast recursion) for computing $$ E_d(x):=\sum_{1\leq a_1<\cdots< a_d \leq A} \sum_{1\leq b_1 < \cdots< b_d \leq B} x_{a_1,b_1} x_{a_2,b_2} \cdots x_{a_d,b_d} $$

$\endgroup$
0
$\begingroup$

Here is a recursive evaluation, that should be fast. Change of notation: $F_d[A,B]:=E_d(x)$. By recursing over the final term, $$ F_d [A,B] = x_{A,B}\cdot F_{d-1}[A-1,B-1] + \sum_{a_d\leq A-1} x_{a_d,B}\cdot F_{d-1}[a_d -1,B-1]+\\ \sum_{b_d\leq B-1} x_{A,b_d} F_{d-1}[A-1,b_d -1] + F_d [A-1,B-1] $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.