Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor

Abstract

The main purpose of this article is to present algorithms to parameterize the degree of the greatest common divisor of two polynomials with parametric coefficients: these algorithms are based on the fact that the principal minors of the Bezout matrices provide the principal subresultant sequence. When coefficients depend on parameters, these algorithms show a better behaviour than the classical ones.

E-mail: [email protected]

E-mail: [email protected]

Keywords:

• Bezout matrices
• Subresultant
• Polynomial gcd

Acknowledgement

Partially supported by Ministerio de Educacion y Ciencia grant BFM 2002-04402-C02-0 and the European Union funded project RAAG (HPRN–CT–2001–00271).

Notes

E-mail: [email protected]

E-mail: [email protected]

E-mail: [email protected]

The current estimation of α is due to Winograd and Coppersmith, 1987, with α < 2.376.

Both sequential algorithms versions are O(n ⁴). However, the sequential complexity algorithm for Chistov is asymptotically (2/3)n ⁴ while the one for the Samuleson–Berkowitz algorithm is (1/2)n ⁴ [see Ref. 1].

This gives a simple proof of the famous algebraic identity known as the Cayley–Hamilton theorem.