On the Boolean complexity of real root refinement

DOI10.1145/2465506.2465938MaRDI QIDQ2963249zbMATHOpenAlexFDO

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

polynomialBoolean complexityreal root refinementreal root problem

Mathematics Subject Classification ID

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

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)

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

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)