Efficient isolation of polynomial's real roots

Fabrice Rouillier 1, 2 Paul Zimmermann 2
1 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
2 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper revisits an algorithm isolating the real roots of a univariate polynomial using Descartes' rule of signs. It follows work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. Our first contribution is a generic algorithm which enables one to describe all the known algorithms based on Descartes' rule of sign and the bissection strategy in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage and as fast as both Collins and Akritas' algorithm and Krandick variant, independently of the input polynomial. From this new algorithm, we derive an adaptive semi-numerical version, using multi-precision interval arithmetic. We finally show that these critical optimizations have important consequences since our new algorithm still works with huge polynomials, including orthogonal polynomials of degree $1000$ and more, which were out of reach of previous methods.
Type de document :
Article dans une revue
Journal of Computational and Applied Mathematics, Elsevier, 2004, 162 (1), pp.33-50. 〈10.1016/j.cam.2003.08.015〉
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:12:45
Dernière modification le : mercredi 21 mars 2018 - 18:58:14

Lien texte intégral




Fabrice Rouillier, Paul Zimmermann. Efficient isolation of polynomial's real roots. Journal of Computational and Applied Mathematics, Elsevier, 2004, 162 (1), pp.33-50. 〈10.1016/j.cam.2003.08.015〉. 〈inria-00099941〉



Consultations de la notice