Fast Computation of the Bezout and Dixon Resultant Matrices

Author： Chionh E-W. Zhang M. Goldman R.N.

ISSN： 0747-7171

Source： Journal of Symbolic Computation, Vol.33, Iss.1, 2002-01, pp. : 13-29

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon–Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas requireO(n³) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses onlyO(n²) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas requireO(m⁴n⁴) additions and multiplications to calculate all the entries of the Dixon–Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses onlyO(m²n³) additions and multiplications.