Show simple item record

dc.contributor.authorCanny, Johnen_US
dc.contributor.authorPedersen, Paulen_US
dc.description.abstractGiven a system of $n+1$ generic Laurent polynomials, for $i \,=\, 1, \ldots, n+1$, $$\eqlabel(\InputSystem) f_i(\x) \quad = \quad \sum_{q\in \A_i} c_{iq} \,x^q; \qquad q \,=\, (q_1,\ldots,q_n); \qquad \x^q \,=\, x_1^{q_1}x_2^{q_2}\cdots x_n^{q_n}; \eqno(\InputSystem) $$ with (finite) support sets $\A_i \subset L$, where $L$ is some affine lattice isomorphic to $\Z^n$; we consider algorithms for the {\it Newton resultant} $R(f_1,f_2, \ldots, f_{n+1})$. This is the unique (up to sign) irreducible polynomial with coefficients in $\Z$ and monomials in the $c_{iq}$ which determines whether or not system~(\InputSystem) has common roots in the {\it algebraic torus} $(\C-\{0\})^n$. The resultant depends only on the {\it Newton polytopes} $N_i \,:=\, conv(\A_i) \subset \R^n$ of the sets $\A_i$. Our terminology emphasizes the dependence on the combinatorics of the Newton polytopes. The algebraic torus is the natural setting for us because we are interested in the properties of systems of polynomials which are invariant under symmetries of the affine lattice $L$, and translation by $q\in L$ corresponds to multiplication by $x^q$ at the level of polynomials. Since $x^q$ may have negative exponents, we restrict to points none of whose coordinates are zero.en_US
dc.format.extent1069711 bytes
dc.format.extent308538 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleAn Algorithm for the Newton Resultanten_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record