Generalized Characteristic Polynomials

John F. Canny

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-440
August 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-440.pdf

We generalize the notion of characteristic polynomial for a system of linear equations to systems of multivariate polynomial equations. The generalization is natural in the sense that it reduces to the usual definition when all the polynomials are linear. Whereas the constant coefficient of the general characteristic polynomial is the resultant of the system. This construction is applied to solve a traditional problem with efficient methods for solving systems of polynomial equations: the presence of infinitely many solutions "at infinity". We give a single-exponential time method for finding all the isolated solution points of a system of polynomials, even in the presence of infinitely many solutions at infinity or elsewhere.


BibTeX citation:

@techreport{Canny:CSD-88-440,
    Author = {Canny, John F.},
    Title = {Generalized Characteristic Polynomials},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1988},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6040.html},
    Number = {UCB/CSD-88-440},
    Abstract = {We generalize the notion of characteristic polynomial for a system of linear equations to systems of multivariate polynomial equations. The generalization is natural in the sense that it reduces to the usual definition when all the polynomials are linear. Whereas the constant coefficient of the general characteristic polynomial is the resultant of the system. This construction is applied to solve a traditional problem with efficient methods for solving systems of polynomial equations: the presence of infinitely many solutions "at infinity". We give a single-exponential time method for finding all the isolated solution points of a system of polynomials, even in the presence of infinitely many solutions at infinity or elsewhere.}
}

EndNote citation:

%0 Report
%A Canny, John F.
%T Generalized Characteristic Polynomials
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-440
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6040.html
%F Canny:CSD-88-440