# Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume

### Ioannis Z. Emiris and John F. Canny

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-94-839

July 1994

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-839.pdf

We propose an efficient method for computing the Sparse Resultant of a system of
*n* + 1 polynomial equations in
*n* unknowns. The first efficient algorithm was proposed by Canny and Emiris. The new algorithm produces a smaller matrix whose determinant is a nontrivial multiple of the Sparse Resultant and from which the latter is easily recovered. It is incremental in the sense that successively larger matrices are constructed until one is found with the above properties. For certain classes of systems, the new algorithm attains optimality by expressing the Sparse Resultant as a single determinant. An implementation of the algorithm is described and experimental results are presented. In addition, we propose an efficient algorithm for computing the Mixed Volume of
*n* polynomials in
*n* variables, which provides an upper bound on the number of common roots. This algorithm has also been implemented and empirical results are reported which suggest that this is the fastest algorithm to date.

Keywords: Sparse Resultant, Mixed Volume, Newton Polytope, Asymptotic Complexity, Experimental Results

BibTeX citation:

@techreport{Emiris:CSD-94-839, Author = {Emiris, Ioannis Z. and Canny, John F.}, Title = {Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume}, Institution = {EECS Department, University of California, Berkeley}, Year = {1994}, Month = {Jul}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5492.html}, Number = {UCB/CSD-94-839}, Abstract = {We propose an efficient method for computing the Sparse Resultant of a system of <i>n</i> + 1 polynomial equations in <i>n</i> unknowns. The first efficient algorithm was proposed by Canny and Emiris. The new algorithm produces a smaller matrix whose determinant is a nontrivial multiple of the Sparse Resultant and from which the latter is easily recovered. It is incremental in the sense that successively larger matrices are constructed until one is found with the above properties. For certain classes of systems, the new algorithm attains optimality by expressing the Sparse Resultant as a single determinant. An implementation of the algorithm is described and experimental results are presented. In addition, we propose an efficient algorithm for computing the Mixed Volume of <i>n</i> polynomials in <i>n</i> variables, which provides an upper bound on the number of common roots. This algorithm has also been implemented and empirical results are reported which suggest that this is the fastest algorithm to date. <p>Keywords: Sparse Resultant, Mixed Volume, Newton Polytope, Asymptotic Complexity, Experimental Results} }

EndNote citation:

%0 Report %A Emiris, Ioannis Z. %A Canny, John F. %T Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume %I EECS Department, University of California, Berkeley %D 1994 %@ UCB/CSD-94-839 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5492.html %F Emiris:CSD-94-839