Efficient Isolation of a Polynomial Real Roots

Fabrice Rouillier 1 Paul Zimmermann 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper gives new results for the isolation of real roots of a univariate polynomial using Descartes' rule of signs, following work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. The first contribution is a generic algorithm which enables one to describe all the existing strategies in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage, while doing no more computations than other algorithms based on Descartes' rule of signs. We show that these critical optimizations have important consequences by proposing a full efficient solution for isolating the real roots of zero-dimensional polynomial systems.
Type de document :
[Research Report] RR-4113, INRIA. 2001
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:10:32
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:11:32



  • HAL Id : inria-00072518, version 1



Fabrice Rouillier, Paul Zimmermann. Efficient Isolation of a Polynomial Real Roots. [Research Report] RR-4113, INRIA. 2001. 〈inria-00072518〉



Consultations de la notice


Téléchargements de fichiers