Efficient Isolation of a Polynomial Real Roots

Fabrice Rouillier 1 Paul Zimmermann 1
1 SPACES - Solving problems through algebraic computation and efficient software
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications, INRIA Lorraine
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.
Document type :
Reports
[Research Report] RR-4113, 2001


https://hal.inria.fr/inria-00072518
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:10:32 AM
Last modification on : Wednesday, June 21, 2006 - 10:43:31 AM

Identifiers

  • HAL Id : inria-00072518, version 1

Collections

Citation

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

Export

Share

Metrics

Consultation de
la notice

186

Téléchargement du document

242