Admissible orders and linear forms

ABSTRACT

Admissible orders on terms (power-products of finitely many indeterminates X1,..., Xn play a fundamental role in the definition and construction of Groebner bases for polynomial ideals (see [Bul). By passage to exponents, these orders may be construed as linear orders on [EQUATION] compatible with addition and with smallest element [EQUATION] = (0,...,0). Any such order extends uniquely to a linear order < on [EQUATION] turning ([EQUATION], +, >) into an ordered group such that all elements of [EQUATION] are non-negative, Conversely, any restriction of such an order to [EQUATION] is an admissible order on [EQUATION]. So from now on an "admissible order" will be a linear group order on [EQUATION] with [EQUATION] >= 0.

REFERENCES

• 1: {Bu} B. Buchberger, Groebner bases: An algorithmic method in polynomial ideal theory, in Recent trends in multidimensional systems theory, Reidel Publ. Comp. 1965.
• 2: {Ga} A. Galligo, Theoreme de division et stabilite en geometrie analytique locale, Ann. Inst. Fourier Univ. Grenoble 29 (1979), 107--184.
• 3: {GJ} M. R. Garey, D. S. Johnson, <b>Computers &amp; Intractability</b>, Freeman, New York, printing 1984.
• 4: Lorenzo Robbiano, Term Orderings on the Polynominal Ring, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.513-517, April 01-03, 1985

INDEX TERMS

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Theory, Verification