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 221 articles , 1 standard article )
Showing results 1 to 20 of 221.
Sorted by year (- Calafiore, Giuseppe C.; Novara, Carlo; Possieri, Corrado: Control analysis and design via randomised coordinate polynomial minimisation (2022)
- Dahan, Xavier: Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one (2022)
- Duff, Timothy; Hein, Nickolas; Sottile, Frank: Certification for polynomial systems via square subsystems (2022)
- Le, Huu Phuoc; Safey El Din, Mohab: Solving parametric systems of polynomial equations over the reals through Hermite matrices (2022)
- Deraux, Martin; Parker, John R.; Paupert, Julien: New nonarithmetic complex hyperbolic lattices. II (2021)
- 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)
- Labahn, George; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan: Homotopy techniques for solving sparse column support determinantal polynomial systems (2021)
- Melczer, Stephen; Salvy, Bruno: Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems (2021)
- Pan, Jian; Shang, Baoxin; Li, Zhe; Zhang, Shugong: Computing PUR of zero-dimensional ideals of breadth at most one (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)
- Xiao, Fanghui; Lu, Dong; Ma, Xiaodong; Wang, Dingkang: An improvement of the rational representation for high-dimensional systems (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)