General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



Support Hull: Relating the Cayley-Dixon Resultant Constructions to the Support of a Polynomial System

A. D. Chtcherba, D. Kapur


A geometric concept of the support hull of the support of a polynomial was used by the authors in [CK03] for developing tight upper bounds on the size of the Dixon resultant matrix for unmixed polynomial systems. The relationship between the support hull and the Cayley-Dixon resultant construction is analyzed in this paper. The support hull is shown to play a 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 unmixed polynomial systems, the sizes of the resultant matrices (both dialytic as well as nondialytic) constructed using the Cayley-Dixon formulation is determined by the support hull of its support. Consequently, the degree of the projection operator (which is in general, a nontrivial multiple of the resultant) computed from these resultant matrices 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 sizes of the resultant matrices (both dialytic and nondialytic) based on the Dixon formulation remain 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 a corner-cut polynomial system from 2 dimensions to arbitrary dimension as well as defining almost corner-cut polynomial systems.

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. These algorithms have been implemented, and their effectiveness have been demonstrated on a number of examples.

  issac2004 @