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

polynomial Boolean complexity double exponential sieve algorithm fast polynomial division precision of computing real root refinement

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

On the Complexity of Reliable Root Approximation
Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
Solving rank-constrained semidefinite programs in exact arithmetic
Accelerated approximation of the complex roots and factors of a univariate polynomial
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
New Practical Advances in Polynomial Root Clustering
Positive root isolation for poly-powers by exclusion and differentiation
Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation
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)