Rational simplification modulo a polynomial ideal

ABSTRACT

We present two algorithms for simplifying rational expressions modulo an ideal of the polynomial ring k[x₁, . . . , x_n]. The first method generates the set of equivalent expressions as amodule over k[x₁, . . . , x_n] and computes a reduced Gröbner basis. From this we obtain a canonical form for the expression up to our choice of monomial order for the ideal. The second method constructs equivalent expressions by solving systems of linear equations over k, and conducts a global search for an expression with minimal total degree. Depending on the ideal, the algorithms may or may not cancel all common divisors. We also provide some timings comparing the efficiency of the algorithms in Maple.

REFERENCES

• 1: W. Adams, P. Loustaunau. An Introduction to Gröbner Bases. American Mathematical Society, 1996.
• 2: T. Becker and V. Weispfenning. Gröbner Bases. Springer-Verlag, 1993.
• 3: Massimo Caboara , Carlo Traverso, Efficient algorithms for ideal operations (extended abstract), Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.147-152, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281597]
• 4: D. Cox, J. Little, D. O'Shea. Ideals, Varieties, and Algorithms. Second Edition. Springer-Verlag, 1996.
• 5: D. Cox, J. Little, D. O'Shea. Using Algebraic Geometry. Second Edition. Springer-Verlag, 2005.
• 6: R. Fröberg. An Introduction to Gröbner Bases. Wiley, 1997.
• 7: Jaime Gutierrez , Tomas Recio, Advances on the simplification of sine-cosine equations, Journal of Symbolic Computation, v.26 n.1, p.31-70, July 1998 [doi>10.1006/jsco.1998.0200]
• 8: Mark van Hoeij, Rational parametrizations of algebraic curves using a canonical divisor, Journal of Symbolic Computation, v.23 n.2-3, p.209-227, Feb./March 1997 [doi>10.1006/jsco.1996.0084]
• 9: Jamie Mulholland , Michael Monagan, Algorithms for trigonometric polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.245-252, July 2001, London, Ontario, Canada [doi>10.1145/384101.384135]
• 10: R. Pearce. Rational Expression Simplification with Polynomial Side Relations. M.Sc. Thesis, Simon Fraser University, 2005.
• 11: Josef Schicho, Rational parametrization of real algebraic surfaces, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.302-308, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281655]
• 12: Quoc-Nam Tran, Efficient Groebner walk conversion for implicitization of geometric objects, Computer Aided Geometric Design, v.21 n.9, p.837-857, November 2004 [doi>10.1016/j.cagd.2004.07.001]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
Groebner Bases, field of fractions, quotient ring, rational expression, side relations, simplification