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.
To view entire paper click here