EFFICIENT INCREMENTAL ALGORITHMS FOR THE SPARSE RESULTANT AND THE MIXED VOLUME

We propose a new and efficient algorithm for computing the sparse resu ltant of a system of n + 1 polynomial equations in n unknowns. This al gorithm produces a matrix whose entries are coefficients of the given polynomials and is typically smaller than the matrices obtained by pre vious approaches. The matrix determinant is a non-trivial multiple of the sparse resultant from which the sparse resultant itself can be rec overed. The algorithm is incremental in the sense that successively la rger matrices are constructed until one is found with the above proper ties. For multigraded systems, the new algorithm produces optimal matr ices, i.e. expresses 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 comp uting the mixed volume of n polynomials in n variables. This computati on provides an upper bound on the number of common isolated roots. A p ublicly available implementation of the algorithm is presented and emp irical results are reported which suggest that it is the fastest mixed volume code to date.