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 1 to 20 of 186.
Sorted by year (- Strzebonski, Adam; Tsigaridas, Elias: Univariate real root isolation in an extension field and applications (2019)
- Ayyildiz Akoglu, Tulay; Hauenstein, Jonathan D.; Szanto, Agnes: Certifying solutions to overdetermined and singular polynomial systems over (\mathbbQ) (2018)
- Becker, Ruben; Sagraloff, Michael; Sharma, Vikram; Yap, Chee: A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (2018)
- Guilloux, Antonin: Volume of representations and birationality of peripheral holonomy (2018)
- Huang, Cheng-Chao; Li, Jing-Cao; Xu, Ming; Li, Zhi-Bin: Positive root isolation for poly-powers by exclusion and differentiation (2018)
- Koseleff, P.-V.; Pecker, D.; Rouillier, F.; Tran, C.: Computing Chebyshev knot diagrams (2018)
- Mora, Teo: An FGLM-like algorithm for computing the radical of a zero-dimensional ideal (2018)
- Naldi, Simone: Solving rank-constrained semidefinite programs in exact arithmetic (2018)
- Naldi, Simone; Plaumann, Daniel: Symbolic computation in hyperbolic programming (2018)
- Safey El Din, Mohab; Schost, Éric: Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization (2018)
- Batra, Prashant; Sharma, Vikram: Near optimal subdivision algorithms for real root isolation (2017)
- Cifuentes, Diego; Parrilo, Pablo A.: Chordal networks of polynomial ideals (2017)
- 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)
- Faugère, Jean-Charles; Mou, Chenqi: Sparse FGLM algorithms (2017)
- Imbach, Rémi; Moroz, Guillaume; Pouget, Marc: A certified numerical algorithm for the topology of resultant and discriminant curves (2017)
- Shang, Baoxin; Zhang, Shugong; Tan, Chang; Xia, Peng: A simplified rational representation for positive-dimensional polynomial systems and SHEPWM equations solving (2017)
- Strzeboński, Adam; Tsigaridas, Elias P.: Univariate real root isolation over a single logarithmic extension of real algebraic numbers (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)