Nearly optimal refinement of real roots of a univariate polynomial

DOI10.1016/j.jsc.2015.06.009zbMath1329.65096OpenAlexW1496909474MaRDI QIDQ898253

Elias P. Tsigaridas, Pan, Victor Y.

Publication date: 8 December 2015

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2015.06.009

zbMATH Keywords

polynomialBoolean complexitydouble exponential sieve algorithmfast polynomial divisionprecision of computingreal root refinement

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

Efficient sampling in spectrahedra and volume approximation, Positive root isolation for poly-powers by exclusion and differentiation, Solving rank-constrained semidefinite programs in exact arithmetic, Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation, Root refinement for real polynomials using quadratic interval refinement, Nearly optimal computations with structured matrices, New Practical Advances in Polynomial Root Clustering, Real polynomial root-finding by means of matrix and polynomial iterations, Accelerated approximation of the complex roots and factors of a univariate polynomial

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Simple algorithms for approximating all roots of a polynomial with real roots
• A worst-case bound for topology computation of algebraic curves
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Practical improvement of the divide-and-conquer eigenvalue algorithms
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Numerical methods for roots of polynomials. II
• Bisection acceleration for the symmetric tridiagonal eigenvalue problem
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Accelerated approximation of the complex roots of a univariate polynomial
• Near Optimal Subdivision Algorithms for Real Root Isolation
• Modern Computer Algebra
• Real Polynomial Root-Finding by Means of Matrix and Polynomial Iterations
• Random polynomials and expected complexity of bisection methods for real solving
• On the boolean complexity of real root refinement
• Practical Divide-and-Conquer Algorithms for Polynomial Arithmetic
• Faster Integer Multiplication
• On the Complexity of Reliable Root Approximation
• Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
• Quasi-Laguerre Iteration in Solving Symmetric Tridiagonal Eigenvalue Problems
• On the complexity of solving a bivariate polynomial system
• When Newton meets Descartes
• Efficient real root approximation
• Univariate real root isolation in an extension field
• Quadratic interval refinement for real roots
• On the topology of planar algebraic curves
• Algorithms – ESA 2005
• The quasi-Laguerre iteration
• On Solving Systems of Bivariate Polynomials
• Algorithms in real algebraic geometry