Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:10:32 AM
Last modification on : Friday, February 4, 2022 - 3:21:55 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:11:32 PM


  • 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⟩



Record views


Files downloads