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 206 articles , 1 standard article )
Showing results 1 to 20 of 206.
Sorted by year (- Abbott, John; Bigatti, Anna Maria; Palezzato, Elisa; Robbiano, Lorenzo: Computing and using minimal polynomials (2020)
- Ceria, Michela; Mora, Teo; Sala, Massimiliano: HELP: a sparse error locator polynomial for BCH codes (2020)
- Chen, Changbo; Wu, Wenyuan; Feng, Yong: Numerical roadmap of smooth bounded real algebraic surface (2020)
- Friedland, Shmuel; Wang, Li: Spectral norm of a symmetric tensor and its computation (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; Poteaux, Adrien; Quadrat, Alban: A symbolic computation approach towards the asymptotic stability analysis of differential systems with commensurate delays (2019)
- 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)