Fast Computation of the Bezout and Dixon Resultant Matrices

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.