Proc. of

Deepak Kapur and Tushar Saxena

New results relating the sparsity of non-homogeneous polynomial systems and
computation of their projection operator (i.e., a non-trivial multiple
of multivariate resultant) using Dixon's method are developed. It is
proved that the Dixon formulation of resultants, despite being
classical, implicitly exploits the structure of the Newton
polytopes of input polynomials;
the complexity of computing Dixon resultant is not
determined by the total degree of the polynomial system.
Bound on the size of the Dixon matrix of unmixed polynomial
systems is derived in terms of their Newton polytopes. This bound
is used to prove that for a multi-homogeneous system, the size of its
Dixon matrix is of a smaller order than its n-fold mixed volume.
Using dense multivariate polynomial interpolation
techniques, it is shown that for a fixed number of variables,
Dixon matrix of multi-homogeneous polynomial systems can be
constructed using * O *(* M *^3) arithmetic operations,
where * M * is
the n-fold mixed volume of the input system.
The Dixon matrix is found to be smaller than the sparse
and Macaulay resultant matrices by a factor exponential in
the number of variables, and the Dixon formulation yields a
faster algorithm to compute the resultant. This work
links the classical Dixon formulation (developed in 1908) to the
modern line of sparsity analysis based on Newton polytopes.