Conditions for exact resultants using the Dixon formulation

ABSTRACT

A structural criteria on polynomial systems is developed for which the generalized Dixon formulation of multivariate resultants defined by Kapur, Saxena and Yang (1994) computes the resultant exactly. The concept of a Dixon-exact support (the set of exponent vectors of terms appearing in a polynomial system) is introduced so that the Dixon formulation produces the exact resultant for generic unmixed polynomial systems whose support is Dixon-exact. A geometric operation, called direct-sum, on the supports is defined that preserves the property of supports being Dixon-exact. Generic n-degree systems and multigraded systems are shown to be a special case of generic unmixed polynomial systems whose support is Dixon-exact. Using a scaling techniques discussed by Kapur and Saxena (1997), a wide class of polynomial systems can be identified for which the Dixon formulation produces exact resultants. This analysis can be used to classify terms appearing in the convex hull (also called the Newton polytope) of the support of a polynomial system that can cause extraneous factors in the computation of a projection operation by the generalized Dixon formulation. For the bivariate case, a complete analysis of the terms corresponding to the exponent vectors in the Newton polytope of the support of a polynomial system is given vis a vis their role in producing extraneous factors in a projection operator. A necessary and sufficient condition is developed for a support to be Dixon-exact. Such an analysis is likely to give insights for the general case of elimination of arbitrarily many variables.

REFERENCES

• 1: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 2: B. Buchberger. Groebner bases: An algorithmic method in polynomial ideal theory. In: (ed. N.K. Bose) Multidimensional System Theory, pages 184-232, 1985.
• 3: John F. Canny , Ioannis Z. Emiris, An Efficient Algorithm for the Sparse Mixed Resultant, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.89-104, May 10-14, 1993
• 4: S-C. Chou , X-S. Gao, Methods for mechanical geometry formula deriving, Proceedings of the international symposium on Symbolic and algebraic computation, p.265-270, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96946]
• 5: A. D. Chthcerba and D. Kapur. Extracting sparse resultant matrices from Dixon resultant formultation. Prec. of 7th Rhine Workshop (RCWA '00), pages 167-182, 2000.
• 6: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer-Verlag, New York, first edition, 1998.
• 7: A. Dixon. The eliminant of three quantics in two independent variables. Prec. London Mathematical Society, 6:468-478, 1908.
• 8: M. Elkali and B. Mourrain. Some applications of bezoutians in effective algebraic geometry. Technical Report 3572, INRIA, Sophia-Antipolis, France, Dec. 1998.
• 9: I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, first edition, 1994.
• 10: Deepak Kapur , Tushar Saxena, Comparison of various multivariate resultant formulations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.187-194, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220370]
• 11: Deepak Kapur , Tushar Saxena, Sparsity considerations in Dixon resultants, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.184-191, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237862]
• 12: Deepak Kapur , Tushar Saxena, Extraneous factors in the Dixon resultant formulation, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.141-148, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258768]
• 13: Deepak Kapur , Tushar Saxena , Lu Yang, Algebraic and geometric reasoning using Dixon resultants, Proceedings of the international symposium on Symbolic and algebraic computation, p.99-107, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190372]
• 14: Tushar Saxena, Efficient variable elimination using resultants, State University of New York at Albany, Albany, NY, 1997
• 15: B. Sturmfels. Sparse elimination theory. In D. Eisenbud and e. L. Robbiano, editors, Prec. Cemputat. Algebraic Geom. and Cemmut. Algebra, Cortona,Italy, June 1991. Cambridge Univ. Press.
• 16: B. Sturmfels and A. Zelevinski. Multigraded resultants of sylvester type. Journal of Algebra, 163:115-127, 1994.

INDEX TERMS

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

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

General Terms:
Theory, Verification