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 213 articles , 1 standard article )
Showing results 1 to 20 of 213.
Sorted by year (- Emiris, Ioannis Z.; Mantzaflaris, Angelos; Tsigaridas, Elias P.: Multilinear polynomial systems: root isolation and bit complexity (2021)
- Hauenstein, Jon D.; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan: Solving determinantal systems using homotopy techniques (2021)
- Melczer, Stephen; Salvy, Bruno: Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems (2021)
- Vieira, R. S.: How to count the number of zeros that a polynomial has on the unit circle? (2021)
- Wang, Dongming; Xu, Juan: A symbolic-numerical algorithm for isolating real roots of certain radical expressions (2021)
- Abbott, John; Bigatti, Anna Maria; Palezzato, Elisa; Robbiano, Lorenzo: Computing and using minimal polynomials (2020)
- Bouzidi, Yacine; Rouillier, Fabrice: Symbolic methods for solving algebraic systems of equations and applications for testing the structural stability (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)
- M.-Alizadeh, Benyamin; Hashemi, Amir: Deterministic normal position transformation and its applications (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)