New Structure Theorem for Subresultants

We give a new structure theorem for subresultantsprecising their gap structure and derive from it a new algorithm for computing them. If d is a bound on the degrees and τ a bound on the bit size of the minors extracted from Sylvester matrix, our algorithm has O(d2) arithmetic operations and size of intermediate computations 2 τ. The key idea is to precise the relations between the successive Sylvester matrix ofA and B on one hand and of A and XB on the other hand, using the notion of G-remainder that we introduce. We also compare our new algorithm with another algorithm with the same characteristics which appeared inDucos (2000).