Efficient Incremental Algorithms for the

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 [CE93]. 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 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.