Ioannis Z. Emiris and John F. Canny

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-94-839

, 1994

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

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

---

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},
    Year= {1994},
    Month= {Jul},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5492.html
%F Emiris:CSD-94-839