An Efficient Algorithm for the Sparse Mixed Resultant

John F. Canny, Ioannis Z. Emiris

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.
BibTeX
@inproceedings{canny1993efficient,
  author = {John F. Canny and Ioannis Z. Emiris},
  title = {{An Efficient Algorithm for the Sparse Mixed Resultant}},
  booktitle = {AAECC},
  year = {1993},
  doi = {10.1007/3-540-56686-4\_36},
}

Loading related content...

Figure