Symbolic solution polynomial equation systems with symmetry

ABSTRACT

Systems of polynomial equations often have symmetry. The Buchberger algorithm which may be used for the solution ignores this symmetry. It is restricted to moderate problems unless factorizing polynomials are found leading to several smaller systems. Therefore two methods are presented which use the symmetry to find factorizing polynomials, decompose the ideal and thus decrease the complexity of the system a lot. In a first approach projections determine factorizing polynomials as input for the solution process, if the group contains reflections with respect to a hyperplane. Two different ways are described for the symmetric group Sm and the dihedral group Dm. While for Sm subsystems are ignored if they have the same zeros modulo G as another subsystem, for the dihedral group Dm polynomials with more than two factors are generated with the help of the theory of linear representations and restrictions are used as well. These decomposition algorithms are independent of the finally used solution technique. We used the REDUCE package Groebner to solve examples from CAPRASSE, DEMARET and NOONBURG which illustrate the efficiency of our REDUCE program. A short introduction to the theory of linear representations is given. In a second approach problems of another class are transformed such that more factors are found during the computation; these transformations are based on the theory of linear representations. Examples illustrate these approaches. The range of solvable problems is enlarged significantly.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

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

General Terms:
Algorithms