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 202 articles , 1 standard article )
Showing results 1 to 20 of 202.
Sorted by year (- Abbott, John; Bigatti, Anna Maria; Palezzato, Elisa; Robbiano, Lorenzo: Computing and using minimal polynomials (2020)
- Chen, Changbo; Wu, Wenyuan; Feng, Yong: Numerical roadmap of smooth bounded real algebraic surface (2020)
- Guo, Feng; Phạm, Ti’ên-Son: On types of degenerate critical points of real polynomial functions (2020)
- Henrion, Didier; Naldi, Simone; Safey El Din, Mohab: Real root finding for low rank linear matrices (2020)
- Huang, Cheng-Chao; Xu, Ming; Li, Zhi-Bin: A conflict-driven solving procedure for poly-power constraints (2020)
- Hyun, Seung Gyu; Neiger, Vincent; Rahkooy, Hamid; Schost, Éric: Block-Krylov techniques in the context of sparse-FGLM algorithms (2020)
- Jin, Kai; Cheng, Jinsan: On the topology and isotopic meshing of plane algebraic curves (2020)
- Menini, Laura; Possieri, Corrado; Tornambè, Antonio: A symbolic algorithm to compute immersions of polynomial systems into linear ones up to an output injection (2020)
- Bouzidi, Yacine; Quadrat, Alban; Rouillier, Fabrice: Certified non-conservative tests for the structural stability of discrete multidimensional systems (2019)
- Chalub, Fabio A. C. C.; Souza, Max O.: From fixation probabilities to (d)-player games: an inverse problem in evolutionary dynamics (2019)
- Dai, Liyun; Fan, Zhe; Xia, Bican; Zhang, Hanwen: Logcf: an efficient tool for real root isolation (2019)
- Erhel, Jocelyne; Migot, Tangi: Characterizations of solutions in geochemistry: existence, uniqueness, and precipitation diagram (2019)
- Strzebonski, Adam; Tsigaridas, Elias: Univariate real root isolation in an extension field and applications (2019)
- Xiao, Shuijing; Zeng, Guangxing: Solving the equality-constrained minimization problem of polynomial functions (2019)
- Yu, Zhiheng; Liu, Liu: Complexity in iteration of polynomials (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)