Computing Polynomial Resultants: Bezout's Determinant
vs. Collins' Reduced P. Algorithm

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 coefficients, 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.

CACM January, 1969

Ku, S. Y.
Adler, R. J.

resultant algorithm, g.c.d. algorithm, polynomial
resultant, elimination, Bezout's determinant, 
Sylvester's determinant, reduced p.r.s. algorithm, Euclidean
algorithm, multivariate polynomial equations

4.40 5.10 5.15 5.41

CA690103 JB February 20, 1978  12:10 PM

1024	4	1946
1051	4	1946
1098	4	1946
1214	4	1946
1380	4	1946
1388	4	1946
1393	4	1946
1396	4	1946
1396	4	1946
1485	4	1946
1487	4	1946
1549	4	1946
1570	4	1946
1878	4	1946
1931	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1946	4	1946
1957	4	1946
2167	4	1946
2168	4	1946
2723	4	1946
2857	4	1946
2857	4	1946
3112	4	1946
902	5	1946
1093	5	1946
1177	5	1946
1393	5	1946
1387	5	1946
1946	5	1946
1946	5	1946
1946	5	1946
360	5	1946
731	5	1946
878	5	1946