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 166 articles , 1 standard article )
Showing results 1 to 20 of 166.
Sorted by year (- Collins, George E.: On the maximum computing time of the bisection method for real root isolation (2017)
- Fan, Xinxin; Otemissov, Adilet; Sica, Francesco; Sidorenko, Andrey: Multiple point compression on elliptic curves (2017)
- Imbach, Rémi; Moroz, Guillaume; Pouget, Marc: A certified numerical algorithm for the topology of resultant and discriminant curves (2017)
- Alcázar, Juan Gerardo; Hermoso, Carlos: Involutions of polynomially parametrized surfaces (2016)
- Bates, Daniel J.; Hauenstein, Jonathan D.; Niemerg, Matthew E.; Sottile, Frank: Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials (2016)
- Bouzidi, Yacine; Lazard, Sylvain; Moroz, Guillaume; Pouget, Marc; Rouillier, Fabrice; Sagraloff, Michael: Solving bivariate systems using rational univariate representations (2016)
- Burr, Michael A.: Continuous amortization and extensions: with applications to bisection-based root isolation (2016)
- Henrion, Didier; Naldi, Simone; El Din, Mohab Safey: Exact algorithms for linear matrix inequalities (2016)
- Hu, Shenglong; Ye, Ke: Multiplicities of tensor eigenvalues (2016)
- Massri, César: Solving a sparse system using linear algebra (2016)
- Mehrabi, Esmaeil; Schost, Éric: A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers (2016)
- Possieri, Corrado; Sassano, Mario: On polynomial feedback Nash equilibria for two-player scalar differential games (2016)
- Sagraloff, Michael; Mehlhorn, Kurt: Computing real roots of real polynomials (2016)
- Wang, Jihua: Bound the number of limit cycles bifurcating from center of polynomial Hamiltonian system via interval analysis (2016)
- Bouzidi, Yacine; Lazard, Sylvain; Pouget, Marc; Rouillier, Fabrice: Separating linear forms and rational univariate representations of bivariate systems (2015)
- Cheng, Jin-San; Jin, Kai: A generic position based method for real root isolation of zero-dimensional polynomial systems (2015)
- Falbel, E.; Koseleff, P.-V.; Rouillier, F.: Representations of fundamental groups of 3-manifolds into $\mathrmPGL(3,\mathbb C)$: exact computations in low complexity (2015)
- Kerber, Michael; Sagraloff, Michael: Root refinement for real polynomials using quadratic interval refinement (2015)
- Lebreton, Romain: Relaxed Hensel lifting of triangular sets (2015)
- Boulier, François; Chen, Changbo; Lemaire, François; Maza, Marc Moreno: Real root isolation of regular chains (2014)