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:
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 Citation10.
Not of the first row, as stated in Citation15.
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.