Algorithms for symmetrical polynomials

ABSTRACT

A special representation for symmetrical polynomials is introduced. Algorithms for the ring operations and for several versions of Gauss' method to express an arbitrary symmetrical polynomial by the elementary symmetrical functions are given and analyzed. Empirical observations show that the representation which is the most economical in terms of space is not always the most economical in terms of time.

REFERENCES

• 1: B. van der Waerden, Algebra I, Heidelberg
• 2: E. Netto, Vorlesungen über Algebra, Leipzig, 1896, Bd.I
• 3: W.S. Brown, ALTRAN User's Manual, Bell Laboratories, Murray Hill, 1973
• 4: G.E. Collins, a list of SAC-1 reports is given in the KWIC-Index in SIGSAM Bulletin of the ACM, New York, 8, (1974), 17-44
• 5: P. Bratley , J. K. S. McKay, Algorithm 305: symmetric polynomial, Communications of the ACM, v.10 n.7, p.450, July 1967 [doi>10.1145/363427.363465]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Theory