Nearly optimal refinement of real roots of a univariate polynomial

DOI10.1016/J.JSC.2015.06.009zbMATH Open1329.65096OpenAlexW1496909474MaRDI QIDQ898253FDOQ898253

Authors: Elias P. Tsigaridas, Victor Y. Pan 

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

Recommendations

• An improved algorithm for real root isolation of univariate polynomials
• Optimal bounds for the roots of polynomials
• Root refinement for real polynomials using quadratic interval refinement
• Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Simple and nearly optimal polynomial root-finding by means of root radii approximation
• Real radicals and finite convergence of polynomial optimization problems
• A new method for real root isolation of univariate polynomials
• A near-optimal algorithm for computing real roots of sparse polynomials
• Real roots of univariate polynomials and straight line programs

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A worst-case bound for topology computation of algebraic curves
• Accelerated approximation of the complex roots of a univariate polynomial
• Algorithms in real algebraic geometry
• Algorithms – ESA 2005
• Amortized bound for root isolation via Sturm sequences
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Bisection acceleration for the symmetric tridiagonal eigenvalue problem
• Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
• Efficient real root approximation
• Faster integer multiplication
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Modern computer algebra
• Near optimal subdivision algorithms for real root isolation
• Numerical methods for roots of polynomials. II
• On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
• On solving systems of bivariate polynomials
• On the Boolean complexity of real root refinement
• On the Complexity of Reliable Root Approximation
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On the complexity of solving a bivariate polynomial system
• On the topology of planar algebraic curves
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• Practical divide-and-conquer algorithms for polynomial arithmetic
• Practical improvement of the divide-and-conquer eigenvalue algorithms
• Quadratic interval refinement for real roots
• Quasi-Laguerre Iteration in Solving Symmetric Tridiagonal Eigenvalue Problems
• Random polynomials and expected complexity of bisection methods for real solving
• Real polynomial root-finding by means of matrix and polynomial iterations
• Simple algorithms for approximating all roots of a polynomial with real roots
• The quasi-Laguerre iteration
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Univariate real root isolation in an extension field
• When Newton meets Descartes

Cited In (16)

• On the Complexity of Reliable Root Approximation
• Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
• Polynomial real root isolation by means of root radii approximation
• Solving rank-constrained semidefinite programs in exact arithmetic
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Simple and nearly optimal polynomial root-finding by means of root radii approximation
• Efficient sampling in spectrahedra and volume approximation
• Real polynomial root-finding by means of matrix and polynomial iterations
• Root refinement for real polynomials using quadratic interval refinement
• Nearly optimal computations with structured matrices
• On the Boolean complexity of real root refinement
• New Practical Advances in Polynomial Root Clustering
• Positive root isolation for poly-powers by exclusion and differentiation
• Efficient real root approximation
• Quadratic interval refinement for real roots
• Root-refining for a polynomial equation

This page was built for publication: Nearly optimal refinement of real roots of a univariate polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898253)