Ioannis Z. Emiris

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-840
November 1994

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

Sparse elimination exploits the structure of a set of multivariate polynomials by measuring complexity in terms of Newton polytopes. We examine polynomial systems that generate 0-dimensional ideals: a generic monomial basis for the coordinate ring of such a system is defined from a mixed subdivision. We offer a simple proof of this known fact and relate the computation of a monomial basis to the calculation of Mixed Volume. The proof relies on the construction of sparse resultant matrices and leads to the efficient computation of multiplication maps in the coordinate ring and the calculation of common zeros. It is shown that the size of monomial bases and multiplication maps in the context of sparse elimination theory is a function of the Mixed Volume of the Newton polytopes, whereas classical elimination considers simply total degree. Our algorithm for the sparse resultant and for root-finding has worst-case complexity proportional to the volume of the Minkowski Sum of these polytopes. We derive new bounds on the Minkowski Sum volume as a function of the Mixed Volume and use these results in order to give general upper bounds on the complexity of computing monomial bases, sparse resultants and common zeros.

BibTeX citation:

@techreport{Emiris:CSD-94-840,
    Author = {Emiris, Ioannis Z.},
    Title = {On the Complexity of Sparse Elimination},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5746.html},
    Number = {UCB/CSD-94-840},
    Abstract = {Sparse elimination exploits the structure of a set of multivariate polynomials by measuring complexity in terms of Newton polytopes. We examine polynomial systems that generate 0-dimensional ideals: a generic monomial basis for the coordinate ring of such a system is defined from a mixed subdivision. We offer a simple proof of this known fact and relate the computation of a monomial basis to the calculation of Mixed Volume. The proof relies on the construction of sparse resultant matrices and leads to the efficient computation of multiplication maps in the coordinate ring and the calculation of common zeros. It is shown that the size of monomial bases and multiplication maps in the context of sparse elimination theory is a function of the Mixed Volume of the Newton polytopes, whereas classical elimination considers simply total degree. Our algorithm for the sparse resultant and for root-finding has worst-case complexity proportional to the volume of the Minkowski Sum of these polytopes. We derive new bounds on the Minkowski Sum volume as a function of the Mixed Volume and use these results in order to give general upper bounds on the complexity of computing monomial bases, sparse resultants and common zeros.}
}

EndNote citation:

%0 Report
%A Emiris, Ioannis Z.
%T On the Complexity of Sparse Elimination
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-840
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5746.html
%F Emiris:CSD-94-840