87
Views
4
CrossRef citations to date
0
Altmetric
Section B

Division-free computation of subresultants using Bezout matrices

Pages 2186-2200 | Received 02 Jan 2008, Accepted 22 Aug 2008, Published online: 22 Jun 2009
 

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.

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.