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.
|