2
$\begingroup$

Let $f,g$ be polynomials of $\mathbb{k}[x]$ where $\mathbb{k}$ is a field. The resultant of $f,g$, $Res(f,g)$, is an element of $\mathbb{k}$ which by definition equals the determinant of the Sylvester matrix of these polynomials. It can be shown that it equals the product of all the differences between the roots of $f,g$ (some of them may lie in a field extension) times a power product of their leading coefficients.

In wikipedia it says that the resultant can also be computed through a variant of the Euclidean al-gorithm called subresultant pseudoremainder sequences, producing a generalization of the Bezout's identity: $$ a(x)f(x)+b(x)g(x)=Res(f,g)\in\mathbb{k} $$ My question is: what is the "subresultant pseudoremainder sequences" algorithm, how can it be applied and how can we find the polynomials $a(x)$, $b(x)$?

$\endgroup$

1 Answer 1

1
$\begingroup$

I strongly recommend the following book for the subresultant algorithm and related results. In you will find the theory behind the subresultants and a full description of the quadratic time algorithm to compute them and notes on the bit complexity of the algorithm.

Algorithms in Real Algebraic Geometry

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .