ISOLATE
Efficient isolation of polynomial’s real roots. 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 bisection 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’s 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.
Keywords for this software
References in zbMATH (referenced in 186 articles , 1 standard article )
Showing results 161 to 180 of 186.
Sorted by year (- Chen, XueFeng; Wang, DingKang: The projection of quasi variety and its application on geometric theorem proving and formula deduction (2004)
- Corvez, Solen; Rouillier, Fabrice: Using computer algebra tools to classify serial manipulators (2004)
- Emiris, Ioannis Z.; Tsigaridas, Elias P.: Comparing real algebraic numbers of small degree (2004)
- Grimmer, Markus; Petras, Knut; Revol, Nathalie: Multiple precision interval packages: comparing different approaches (2004)
- Krandick, Werner: Trees and jumps and real roots. (2004)
- Lebrun, Jérôme; Selesnick, Ivan: Gröbner bases and wavelet design (2004)
- Rouillier, Fabrice; Zimmermann, Paul: Efficient isolation of polynomial’s real roots. (2004)
- Safey El Din, Mohab; Schost, Éric: Properness defects and projections and computation of at least one point in each connected component of a real algebraic set (2004)
- Bostan, Alin; Salvy, Bruno; Schost, Éric: Fast algorithms for zero-dimensional polynomial systems using duality (2003)
- Cluzeau, Thomas; Hubert, Evelyne: Resolvent representation for regular differential ideals (2003)
- Safey El Din, Mohab; Schost, Éric: Polar varieties and computation of one point in each connected component of a smooth real algebraic set (2003)
- Schost, Éric: Complexity results for triangular sets (2003)
- Aubry, Philippe; Rouillier, Fabrice; Safey El Din, Mohab: Real solving for positive dimensional systems. (2002)
- Berberich, Eric; Eigenwillig, Arno; Hemmer, Michael; Hert, Susan; Mehlhorn, Kurt; Schömer, Elmar: A computational basis for conic arcs and boolean operations on conic polygons (2002)
- Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C.: On the complexity of isolating real roots and computing with certainty the topological degree (2002)
- Brown, Christopher W.: Improved projection for cylindrical algebraic decomposition (2001)
- Gao, Xiao-Shan; Huang, Lei-Dong; Jiang, Kun: A hybrid method for solving geometric constraint problems (2001)
- Giusti, Marc; Lecerf, Grégoire; Salvy, Bruno: A Gröbner free alternative for polynomial system solving (2001)
- Heintz, Joos; Matera, Guillermo; Waissbein, Ariel: On the time-space complexity of geometric elimination procedures (2001)
- Lazard, D.: On the specification for solvers of polynomial systems (2001)