swMATH ID: 7741
Software Authors: Rouillier, Fabrice; Zimmermann, Paul
Description: 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.
Homepage: http://www.maplesoft.com/support/help/Maple/view.aspx?path=RootFinding/Isolate
Dependencies: Maple
Keywords: univariate polynomial; isolation of real root; Descartes’s rule of signs; algorithm; bisection method; interval-arithmetic filter; numerical examples
Related Software: Kronecker; FGb; Maple; SINGULAR; PHCpack; SYNAPS; Bertini; RAGlib; na20; Macaulay2; MPFI; Magma; QEPCAD; Lgp; CGAL; SqFreeEVAL; SeDuMi; na10; Epsilon; GloptiPoly
Cited in: 240 Documents

Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
Efficient isolation of polynomial’s real roots. Zbl 1040.65041
Rouillier, Fabrice; Zimmermann, Paul
all top 5

Cited by 307 Authors

21 Schost, Éric
19 Rouillier, Fabrice
17 Safey El Din, Mohab
17 Tsigaridas, Elias P.
11 Emiris, Ioannis Z.
11 Sagraloff, Michael
10 Cheng, Jinsan
10 Mourrain, Bernard
8 Gao, Xiaoshan
7 Mehlhorn, Kurt
6 Eigenwillig, Arno
6 Strzeboński, Adam Wojciech
5 Bouzidi, Yacine
5 Lasserre, Jean-Bernard
5 Laurent, Monique
5 Lazard, Sylvain
5 Matera, Guillermo
5 Pouget, Marc
5 Rostalski, Philipp
4 Akritas, Alkiviadis G.
4 Berberich, Eric
4 Faugère, Jean-Charles
4 Jeronimo, Gabriela
4 Krandick, Werner
4 Lazard, Daniel
4 Mora, Teo
4 Naldi, Simone
4 Salvy, Bruno
4 Sottile, Frank
4 Trébuchet, Philippe
4 Wang, Dingkang
4 Wolpert, Nicola
4 Xia, Bican
3 Ayad, Ali
3 Cafure, Antonio
3 Henrion, Didier
3 Kettner, Lutz
3 Koseleff, Pierre-Vincent
3 Moroz, Guillaume
3 Perrucci, Daniel
3 Possieri, Corrado
3 Poteaux, Adrien
3 Sabia, Juan
3 Schmitt, Susanne
3 Schömer, Elmar
3 Ştefănescu, Doru
3 Szántó, Ágnes
3 Vu, Thi Xuan
3 Waissbein, Ariel
3 Wang, Dongming
3 Xiao, ShuiJing
3 Yap, Chee-Keng
3 Zeng, Guangxing
2 Bates, Daniel J.
2 Becker, Ruben
2 Belabas, Karim
2 Bostan, Alin
2 Burr, Michael A.
2 Ceria, Michela
2 Chen, Changbo
2 Chen, Xiaodiao
2 Cluzeau, Thomas
2 Collins, George E.
2 Dahan, Xavier
2 Diochnos, Dimitrios I.
2 Elkadi, Mohamed
2 Emeliyanenko, Pavel
2 Feng, Yong
2 Galligo, André
2 Hauenstein, Jonathan D.
2 Helmer, Martin
2 Hemmer, Michael
2 Hert, Susan
2 Huang, Chengchao
2 Hubert, Evelyne
2 Janovitz-Freireich, Itnuit
2 Jin, Kai
2 Kerber, Michael
2 Labahn, George
2 Lebrun, Jerome
2 Lecerf, Grégoire
2 Li, Jia
2 Li, Zhibin
2 Ma, XiaoDong
2 Niu, Wei
2 Pecker, Daniel
2 Peñaranda, Luis Mariano
2 Petitjean, Sylvain
2 Quadrat, Alban
2 Revol, Nathalie
2 Rónyai, Lajos
2 Shang, Baoxin
2 Sharma, Vikram
2 Sun, Yao
2 Teillaud, Monique
2 Vigklas, Panagiotis S.
2 Wu, Wenyuan
2 Xu, Ming
2 Yakoubsohn, Jean-Claude
2 Yuan, Chunming
...and 207 more Authors
all top 5

Cited in 58 Serials

60 Journal of Symbolic Computation
11 Applicable Algebra in Engineering, Communication and Computing
9 Theoretical Computer Science
9 Journal of Complexity
9 Mathematics in Computer Science
8 Journal of Computational and Applied Mathematics
7 Computer Aided Geometric Design
6 Journal of Systems Science and Complexity
3 Mathematics of Computation
3 Discrete & Computational Geometry
3 Computational Geometry
3 Foundations of Computational Mathematics
3 Science China. Mathematics
2 Computers & Mathematics with Applications
2 Applied Mathematics and Computation
2 Automatica
2 Journal of Global Optimization
2 Numerical Algorithms
2 SIAM Journal on Optimization
2 Experimental Mathematics
2 Journal of Mathematical Sciences (New York)
2 Journal of Algebra and its Applications
2 Serdica Journal of Computing
2 SIAM Journal on Applied Algebra and Geometry
1 International Journal of Control
1 Bulletin of Mathematical Biology
1 Chaos, Solitons and Fractals
1 Computing
1 Geometriae Dedicata
1 Michigan Mathematical Journal
1 Programming and Computer Software
1 Transactions of the American Mathematical Society
1 Algorithmica
1 Journal of Automated Reasoning
1 CAD. Computer-Aided Design
1 Multidimensional Systems and Signal Processing
1 Mathematical Structures in Computer Science
1 Designs, Codes and Cryptography
1 Aequationes Mathematicae
1 Expositiones Mathematicae
1 Mathematical Programming. Series A. Series B
1 Computational Complexity
1 Journal de Théorie des Nombres de Bordeaux
1 Finite Fields and their Applications
1 Reliable Computing
1 Mechanism and Machine Theory
1 Computational Geosciences
1 Journal of Universal Computer Science
1 Nonlinear Analysis. Modelling and Control
1 Journal of Intelligent and Fuzzy Systems
1 Communications in Mathematical Sciences
1 Mathématiques & Applications (Berlin)
1 Algorithms and Computation in Mathematics
1 International Mathematical Forum
1 Journal of Nonlinear Science and Applications
1 Science China. Information Sciences
1 Imperial College Press Optimization Series
1 Mathematics and Visualization
all top 5

Cited in 38 Fields

114 Computer science (68-XX)
94 Numerical analysis (65-XX)
76 Commutative algebra (13-XX)
63 Algebraic geometry (14-XX)
45 Field theory and polynomials (12-XX)
22 Real functions (26-XX)
18 Number theory (11-XX)
11 Operations research, mathematical programming (90-XX)
8 Functions of a complex variable (30-XX)
7 Information and communication theory, circuits (94-XX)
6 Systems theory; control (93-XX)
5 Linear and multilinear algebra; matrix theory (15-XX)
5 Manifolds and cell complexes (57-XX)
4 Combinatorics (05-XX)
4 Special functions (33-XX)
4 Biology and other natural sciences (92-XX)
3 General and overarching topics; collections (00-XX)
3 Associative rings and algebras (16-XX)
3 Several complex variables and analytic spaces (32-XX)
3 Ordinary differential equations (34-XX)
3 Mechanics of particles and systems (70-XX)
3 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
2 Calculus of variations and optimal control; optimization (49-XX)
2 Differential geometry (53-XX)
1 History and biography (01-XX)
1 Mathematical logic and foundations (03-XX)
1 General algebraic systems (08-XX)
1 Group theory and generalizations (20-XX)
1 Topological groups, Lie groups (22-XX)
1 Dynamical systems and ergodic theory (37-XX)
1 Difference and functional equations (39-XX)
1 Operator theory (47-XX)
1 Convex and discrete geometry (52-XX)
1 Algebraic topology (55-XX)
1 Fluid mechanics (76-XX)
1 Optics, electromagnetic theory (78-XX)
1 Quantum theory (81-XX)
1 Geophysics (86-XX)

Citations by Year