View Related Documents

Abstract

We propose a compact formula for the mixed resultant of a system of n+1 sparse Laurent polynomials in n variables. Our approach is conceptually simple and geometric, in that it applies a mixed subdivision to the Minkowski Sum of the input Newton polytopes. It constructs a matrix whose determinant is a non-zero multiple of the resultant so that the latter can be defined as the GCD of n + 1 such determinants. For any specialization of the coefficients there are two methods which use one extra perturbation variable and return the resultant. Our algorithm is the first to present a determinantal formula for arbitrary systems; moreover, its complexity for unmixed systems is polynomial in the resultant degree. Further empirical results suggest that this is the most efficient method to date for sparse elimination.
Supported by a David and Lucile Packard Foundation Fellowship and by NSF Presidential Young Investigator Grant IRI-8958577.

Fulltext Preview

Image of the first page of the fulltext document