MultiPolynomial Resultant Algorithms

Dinesh Manocha and John F. Canny

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-632
May 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-632.pdf

Computational methods for manipulating sets of polynomial equations are becoming of greater importance due to the use of polynomial equations in various applications. In some cases we need to eliminate variables from a given system of polynomial equations to obtain a "symbolically smaller" system, while in others we desire to compute the numerical solutions of non-linear polynomial equations. Recently, the techniques of Grobner bases and polynomial continuation have received much attention as algorithmic methods for these symbolic and numeric applications. When it comes to practice, these methods are slow and not effective for a variety of reasons. In this paper we present efficient techniques for applying multipolynomial resultant algorithms and show their effectiveness for manipulating system of polynomial equations. In particular, we present efficient algorithms for computing the resultant of a system of polynomial equations (whose coefficients may be symbolic variables). The algorithm can also be used for interpolating polynomials from their values and expanding symbolic determinants. Moreover, we use multipolynomial resultants for computing the real or complex solutions of non-linear polynomial equations. It reduces the problem to computing eigenvalues of matrices. We also discuss implementation of these algorithms in the context of certain applications.


BibTeX citation:

@techreport{Manocha:CSD-91-632,
    Author = {Manocha, Dinesh and Canny, John F.},
    Title = {MultiPolynomial Resultant Algorithms},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/5645.html},
    Number = {UCB/CSD-91-632},
    Abstract = {Computational methods for manipulating sets of polynomial equations are becoming of greater importance due to the use of polynomial equations in various applications. In some cases we need to eliminate variables from a given system of polynomial equations to obtain a "symbolically smaller" system, while in others we desire to compute the numerical solutions of non-linear polynomial equations. Recently, the techniques of Grobner bases and polynomial continuation have received much attention as algorithmic methods for these symbolic and numeric applications. When it comes to practice, these methods are slow and not effective for a variety of reasons. In this paper we present efficient techniques for applying multipolynomial resultant algorithms and show their effectiveness for manipulating system of polynomial equations. In particular, we present efficient algorithms for computing the resultant of a system of polynomial equations (whose coefficients may be symbolic variables). The algorithm can also be used for interpolating polynomials from their values and expanding symbolic determinants. Moreover, we use multipolynomial resultants for computing the real or complex solutions of non-linear polynomial equations. It reduces the problem to computing eigenvalues of matrices. We also discuss implementation of these algorithms in the context of certain applications.}
}

EndNote citation:

%0 Report
%A Manocha, Dinesh
%A Canny, John F.
%T MultiPolynomial Resultant Algorithms
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-632
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/5645.html
%F Manocha:CSD-91-632