Generalized normal forms and polynomial system solving

ABSTRACT

This paper describes a new method for computing the normal form of a polynomial modulo a zero-dimensional ideal I. We give a detailed description of the algorithm, a proof of its correctness, and finally experimentations on classical benchmark polynomial systems. The method that we propose can be thought as an extension of both the Gröbner basis method and the Macaulay construction. We have weaken the monomial ordering requirement for bases computations, which allows us to construct new type of representations for the quotient algebra. This approach yields more freedom in the linear algebra steps involved, which allows us to take into account numerical criteria while performing the symbolic steps. This is a new feature for a symbolic algorithm, which has a huge impact on the practical efficiency.

REFERENCES

• 1: W. Auzinger and H. J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Proc. Intern. Conf. on Numerical Math., volume 86 of Int. Series of Numerical Math, pages 12--30. Birkhäuser Verlag, 1988.
• 2: L. Busé, M. Elkadi, and B. Mourrain. Using projection operators in computer aided geometric design. In Topics in Algebraic Geometry and Geometric Modeling, pages 321--342. Contemporary Mathematics, 2003.
• 3: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258767]
• 4: D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer Verlag, New York, 1992.
• 5: D. Eisenbud. Commutative Algebra with a view toward Algebraic Geometry, volume 150 of Graduate Texts in Math. Berlin, Springer-Verlag, 1994.
• 6: Ioannis Z. Emiris , Bernard Mourrain, Matrices in elimination theory, Journal of Symbolic Computation, v.28 n.1-2, p.3-44, July/Aug. 1999 [doi>10.1006/jsco.1998.0266]
• 7: J.C. Faugère. A new efficient algorithm for computing Gröbner Basis (F4). J. of Pure and Applied Algebra, 139:61--88, 1999.
• 8: J. C. Faugère , P. Gianni , D. Lazard , T. Mora, Efficient computation of zero-dimensional Gro¨bner bases by change of ordering, Journal of Symbolic Computation, v.16 n.4, p.329-344, Oct. 1993 [doi>10.1006/jsco.1993.1051]
• 9: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 10: Eduardo Cattani , David A. Cox , Guillaume Chèze , Alicia Dickenstein , Mohamed Elkadi , Ioannis Z. Emiris , André Galligo , Achim Kehrein , Martin Kreuzer , Bernard Mourrain, Solving Polynomial Equations: Foundations, Algorithms, and Applications (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 11: D. Lazard. Stewart platforms and Gröbner bases. In ARK'92, Proceedings of Advance in Robot Kinematik, Ferrare, Italia, September 1992.
• 12: F. S. Macaulay. The Algebraic Theory of Modular Systems. Cambridge Univ. Press, 1916.
• 13: H.M. Möller and T. Sauer. H-bases for polynomial interpolation and system solving. multivariate polynomial interpolation. Advances Comput. Math., 12(4):335--362, 2000.
• 14: B. Mourrain, The 40 “generic” positions of a parallel robot, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.173-182, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164120]
• 15: B. Mourrain, Computing the isolated roots by matrix methods, Journal of Symbolic Computation, v.26 n.6, p.715-738, Dec. 1998 [doi>10.1006/jsco.1998.0236]
• 16: Bernard Mourrain, A New Criterion for Normal Form Algorithms, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.430-443, November 15-19, 1999
• 17: Bernard Mourrain , Philippe Trebuchet, Solving projective complete intersection faster, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.234-241, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345642]
• 18: B. Mourrain and Ph. Trébuchet. Algebraic methods for numerical solving. In Proc. of the 3rd International Workshop on Symbolic and Numeric Algorithms for Scientific Computing'01 (Timisoara, Romania), pages 42--57, 2002.
• 19: B. Mourrain and Ph. Trébuchet. Generalised normal forms and polynomial system solving. Technical Report 5471, INRIA Sophia-Antipolis, 2005.
• 20: F. Rouillier. Solving zero-dimensional polynomial systems throuhg Rational Univariate Representation. App. Alg. in Eng. Com. Comp., 9(5):433--461, 1999.
• 21: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms

Keywords:
multivariate polynomial, normal form, quotient algebra, root-finding, symbolic-numeric computation