We give a new structure theorem for subresultants precising their
gap structure and derive from
it a new algorithm for computing them.
If d is a bound on the degrees and t a bound on the bitsize
of the
minors extracted from Sylvester matrix,
our algorithm has O(d2) arithmetic
operations and size of intermediate computations 2 t.
The key idea is to precise the relations between
the successive Sylvester matrix of A and B in one hand
and of A and XB on the other hand, using the notion
of G-remainder we introduce.
We also compare our new algorithm
with another algorithm with the same characteristics given by L. Ducos.
This document was translated from LATEX by
HEVEA.