Support hull: relating the cayley-dixon resultant constructions to the support of a polynomial system

ABSTRACT

A geometric concept of the support hull of the support of a polynomial was used earlier by the authors for developing a tight upper bound on the size of the Cayley-Dixon resultant matrix for an unmixed polynomial system. The relationship between the support hull and the Cayley-Dixon resultant construction is analyzed in this paper. The support hull is shown to play an important role in the construction and analysis of resultant matrices based on the Cayley-Dixon formulation, similar to the role played by the associated convex hull (Newton polytope) for analyzing resultant matrices over the toric variety. For an unmixed polynomial system, the sizes of the resultant matrices (both dialytic as well as nondialytic) constructed using the Cayley-Dixon formulation are determined by the support hull of its support. Consequently, degree of the projection operator (which is in general, a nontrivial multiple of the resultant) computed from such a resultant matrix is determined by the support hull.The support hull of a given support is similar to its convex hull except that instead of the Euclidean distance, the support hull is defined using rectilinear distance. The concept of a support-hull interior point is introduced. It is proved that for an unmixed polynomial system, the size of the resultant matrix (both dialytic and nondialytic) based on the Cayley-Dixon formulation remains the same even if a term whose exponent is support-hull interior with respect to the support is generically added to the polynomial system. This key insight turned out to be instrumental in generalizing the concept of an unmixed polynomial system with a corner-cut support from 2 dimensions to arbitrary dimension as well as identifying an unmixed polynomial system with almost corner-cut support in arbitrary dimension.An algorithm for computing the size (and the lattice points) of the support hull of a given support is presented. It is proved that determining whether a given lattice point is not in the support hull, is NP-complete. A heuristic for computing a good variable ordering for constructing Dixon matrices for mixed as well as unmixed polynomial systems is proposed using the support hull and its projections. This is one of the first results on developing heuristics for variable orderings for constructing resultant matrices. A construction for a Sylvester-type resultant matrix based on the support hull of a polynomial system is also given.

REFERENCES

• 1: David Avis , David Bremner , Raimund Seidel, How good are convex hull algorithms?, Computational Geometry: Theory and Applications, v.7 n.5-6, p.265-301, April 1997 [doi>10.1016/S0925-7721(96)00023-5]
• 2: John F. Canny , Ioannis Z. Emiris, A subdivision-based algorithm for the sparse resultant, Journal of the ACM (JACM), v.47 n.3, p.417-451, May 2000 [doi>10.1145/337244.337247]
• 3: Eng-Wee Chionh, Rectangular corner cutting and Dixon A -resultants, Journal of Symbolic Computation, v.31 n.6, p.651-669, June 2001 [doi>10.1006/jsco.2001.0448]
• 4: Arthur D. Chtcherba , Deepak Kapur, A new sylvester-type resultant method based on the dixon-bezout formulation, 2003
• 5: Arthur D. Chtcherba , Deepak Kapur, Conditions for exact resultants using the Dixon formulation, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.62-70, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345583]
• 6: A. D. Chtcherba and D. Kapur. Constructing Sylvester-type Resultant Matrices using the Dixon Formulation. Accepted for publication Journal of Symbolic Computation, 2003.
• 7: Arthur D. Chtcherba , Deepak Kapur, Exact resultants for corner-cut unmixed multivariate polynomial systems using the Dixon formulation, Journal of Symbolic Computation, v.36 n.3-4, p.289-315, September 2003 [doi>10.1016/S0747-7171(03)00084-1]
• 8: Arthur D. Chtcherba , Deepak Kapur, Exact resultants for corner-cut unmixed multivariate polynomial systems using the Dixon formulation, Journal of Symbolic Computation, v.36 n.3-4, p.289-315, September 2003 [doi>10.1016/S0747-7171(03)00084-1]
• 9: A. D. Chtcherba and D. Kapur. On Relationship between the Dixon-based Resultant Construction and the Supports of Polynomial Systems. Technical Report Forthcomming, Computer Science Dept., Univ. of New Mexico, Albuquerque, New Mexico, USA, 2004.
• 10: A. Dixon. The eliminant of three quantics in two independent variables. Proc. London Mathematical Society, 6:468--478, 1908.
• 11: Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
• 12: 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]
• 13: 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]
• 14: 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]
• 15: Igor R. Shafarevich , Miles Reid, Basic algebraic geometry 1 (2nd, revised and expanded ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 16: Ming Zhang , Ron Goldman, Rectangular corner cutting and Sylvester A-resultants, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.301-308, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345659]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory

Keywords:
dialytic method, dixon resultant formulation, resultant, support, support hull, support-hull interior point, sylvester-type matrices, variable ordering