Division-free computation of subresultants using Bezout matrices

Abstract

We present an algorithm to compute the subresultant sequence of two polynomials that completely avoids division in the ground domain, generalizing an algorithm given by Abdeljaoued et al. [J. Abdeljaoued, G. Diaz-Toca, and L. Gonzalez-Vega, Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor, Int. J. Comput. Math. 81 (2004), pp. 1223–1238]. We evaluate determinants of slightly manipulated Bezout matrices using the algorithm of Berkowitz. Although the algorithm gives worse complexity bounds than pseudo-division approaches, our experiments show that our approach is superior for input polynomials with moderate degrees if the ground domain contains indeterminates.

Keywords:

• subresultant
• Bezout matrix
• polynomial gcd

AMS Subject Classification :

• I.1.2 [Symbolic and Algebraic Manipulation]: Algorithms—Algebraic algorithms
• F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems—Computations on Polynomials

Acknowledgements

The author thanks Arno Eigenwillig for pointing towards the problem and for valuable discussions about it. Also, the author is grateful to Gema Diaz-Toca, and the anonymous referees for their valuable comments on the earlier versions of this paper.

Notes

The currently best known bound is due to Coppersmith and Winograd 10.

Not of the first row, as stated in 15.

Kaltofen also mentions the Berkowitz method as an alternative.

One does not have to compute all coefficients, because the degree of is known to be at most k.