Arthur D. Chtcherba and Deepak Kapur
Presented at International Symposium on Symbolic and Algebraic Computation (ISSAC-2000), St. Andrews, Scotland, August 6-9, 2000
A new method for constructing sparse resultant matrices for a multivariate polynomial system is presented. Unlike other sparse resultant matrix construction algorithms discussed in the literature, the proposed method does not explicitly use the support of the polynomial system (i.e., the set of exponent vectors corresponding to the power-products appearing in the polynomials). Instead, the construction implicitly exploits the sparse structure of the polynomial system since it is is based on the classical constructions by Cayley and Dixon for setting up resultant matrices. The complexity of the proposed algorithm is given, and compared with the incremental algorithm developed by Emiris and Canny (1995) as well as the lifting and subdivision based algorithm developed by Canny and Emiris (1996) for constructing sparse resultant matrices. The algorithm has been implemented, and also empirically compared with the incremental and subdivision algorithms, on a suite of examples from diverse application domains.