Fast rewriting of symmetric polynomials

摘要

This note presents a fast version of the classical algorithm to represent any symmetric function in a unique way as a polynomial in the elementary symmetric polynomials by using power sums of variables.We analyze the worst case complexity for both algorithms,the original and the fast version,and confirm our results by empirical run-time experiments.Our main result is a fast alfgorithm with a polynomial worst case complexity w.r.t. the total degree of the input polynomial ocmpared to the classical algorithm with its exponential worst case complexity.