Access Restriction

Author Ku, S. Y. ♦ Adler, R. J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
Language English
Subject Keyword Bezout's determinant ♦ G.c.d algorithm ♦ Euclidean algorithm ♦ Polynomial resultant ♦ Multivariate polynomial equations ♦ Elimination ♦ Reduced p.r.s algorithm ♦ Resultant algorithm ♦ Sylvester's determinant
Abstract Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation depends upon the extent to which extraneous factors are introduced, the extent of propagation of errors caused by truncation of real coeffcients, memory requirements, and computing speed. Preliminary considerations narrow the choice of the best algorithm to Bezout's determinant and Collins' reduced polynomial remainder sequence (p.r.s.) algorithm. Detailed tests performed on sample problems conclusively show that Bezout's determinant is superior in all respects except for univariate polynomials, in which case Collins' reduced p.r.s. algorithm is somewhat faster. In particular Bezout's determinant proves to be strikingly superior in numerical accuracy, displaying excellent stability with regard to round-off errors. Results of tests are reported in detail.
Description Affiliation: Case Western Reserve Univ., Cleveland, OH (Ku, S. Y.; Adler, R. J.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 12
Issue Number 1
Page Count 8
Starting Page 23
Ending Page 30

Open content in new tab

   Open content in new tab
Source: ACM Digital Library