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

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)

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

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)