On the Boolean complexity of real root refinement

DOI10.1145/2465506.2465938MaRDI QIDQ2963249zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan, Elias P. Tsigaridas

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00816214/file/pt-refine.pdf

zbMATH Keywords

Boolean complexitypolynomialreal root problemreal root refinement

Mathematics Subject Classification ID

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

Recommendations

• Nearly optimal refinement of real roots of a univariate polynomial
• Efficient real root approximation
• Root refinement for real polynomials using quadratic interval refinement
• Quadratic interval refinement for real roots
• Accelerated approximation of the complex roots of a univariate polynomial

Cited in

(13)

• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Univariate real root isolation in an extension field and applications
• Bounds for polynomials on algebraic numbers and application to curve topology
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• On the complexity of computing the topology of real algebraic space curves
• Simple and nearly optimal polynomial root-finding by means of root radii approximation
• Univariate real root isolation over a single logarithmic extension of real algebraic numbers
• Transformations of matrix structures work again
• A generic position based method for real root isolation of zero-dimensional polynomial systems
• Root refinement for real polynomials using quadratic interval refinement
• New Practical Advances in Polynomial Root Clustering
• Quadratic interval refinement for real roots
• Nearly optimal refinement of real roots of a univariate polynomial

This page was built for publication: On the Boolean complexity of real root refinement

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