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 41 to 60 of 186.
Sorted by year (- Sagraloff, Michael: On the complexity of the Descartes method when using approximate arithmetic (2014)
- Schröcker, Hans-Peter; Weber, Matthias J.: Guaranteed collision detection with toleranced motions (2014)
- Shen, Fei; Wu, Wenyuan; Xia, Bican: Real root isolation of polynomial equations based on hybrid computation (2014)
- Xiao, Shuijing; Zeng, Guangxing: Determination of the limits for multivariate rational functions (2014)
- Berberich, Eric; Emeliyanenko, Pavel; Kobel, Alexander; Sagraloff, Michael: Exact symbolic-numeric computation of planar algebraic curves (2013)
- Gao, Xiao-Shan; Li, Wei; Yuan, Chun-Ming: Intersection theory in differential algebraic geometry: generic intersections and the differential Chow form (2013)
- Herrero, María Isabel; Jeronimo, Gabriela; Sabia, Juan: Affine solution sets of sparse polynomial systems (2013)
- Lasserre, Jean-Bernard; Laurent, Monique; Mourrain, Bernard; Rostalski, Philipp; Trébuchet, Philippe: Moment matrices, border bases and real radical computation (2013)
- Poteaux, Adrien; Schost, Éric: On the complexity of computing with zero-dimensional triangular sets (2013)
- Poteaux, Adrien; Schost, Éric: Modular composition modulo triangular sets and applications (2013)
- Sun, Yao; Wang, Dingkang: An efficient algorithm for factoring polynomials over algebraic extension field (2013)
- Ayad, Ali; Fares, Ali; Ayyad, Youssef: An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations (2012)
- Burr, Michael A.; Krahmer, Felix: SqFreeEVAL: An (almost) optimal real-root isolation algorithm (2012)
- Cheng, Jin-San; Gao, Xiao-Shan; Guo, Leilei: Root isolation of zero-dimensional polynomial systems with linear univariate representation (2012)
- Collins, George E.; Krandick, Werner: On the computing time of the continued fractions method (2012)
- Dahan, Xavier; Kadri, Abdulilah; Schost, Éric: Bit-size estimates for triangular sets in positive dimension (2012)
- De Feo, Luca; Schost, Éric: Fast arithmetics in Artin-Schreier towers over finite fields (2012)
- Gaudry, Pierrick; Schost, Éric: Genus 2 point counting over prime fields (2012)
- Janovitz-Freireich, Itnuit; Mourrain, Bernard; Rónyai, Lajos; Szántó, Ágnes: On the computation of matrices of traces and radicals of ideals (2012)
- Laurent, Monique; Rostalski, Philipp: The approach of moments for polynomial equations (2012)