Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. An Algorithm for the Newton Resultant

An Algorithm for the Newton Resultant

File(s)
93-1394.ps (301.31 KB)
93-1394.pdf (1.02 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6172
Collections
Computer Science Technical Reports
Author
Canny, John
Pedersen, Paul
Abstract

Given 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.

Date Issued
1993-10
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1394
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance