New structure theorems for subresultants

Henri Lombardi 1 Marie-Françoise Roy Mohab Safey El Din 2, 3
2 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
3 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 $\tau$ a bound on the bitsize of the minors extracted from Sylvester matrix, our algorithm has $O(d^2)$ arithmetic operations and size of intermediate computations $2\tau$. 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.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2000, 29 (4-5), pp.663-690. 〈10.1006/jsco.1999.0322〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00099274
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:18
Dernière modification le : vendredi 31 août 2018 - 09:25:57

Lien texte intégral

Identifiants

Collections

Citation

Henri Lombardi, Marie-Françoise Roy, Mohab Safey El Din. New structure theorems for subresultants. Journal of Symbolic Computation, Elsevier, 2000, 29 (4-5), pp.663-690. 〈10.1006/jsco.1999.0322〉. 〈inria-00099274〉

Partager

Métriques

Consultations de la notice

289