From approximate factorization to root isolation

DOI10.1145/2465506.2465523MaRDI QIDQ2963246zbMATH OpenOpenAlexFDO

Authors K. Mehlhorn, Michael Sagraloff, Pengming Wang

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://doi.org/10.1145/2465506.2465523

zbMATH Keywords

bit complexitycertified algorithmscylindrical algebraic decompositionnumerical algorithmsroot isolationroot refinement

Mathematics Subject Classification ID

Computational aspects of algebraic curves (14Q05) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of roots of polynomial equations (65H04) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Recommendations

• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Bounds for polynomials on algebraic numbers and application to curve topology
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Computing real roots of real polynomials
• Efficient real root approximation

Cited in

(17)

• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Bounds for polynomials on algebraic numbers and application to curve topology
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• On the complexity of computing with planar algebraic curves
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• On isolation of real and nearly real zeros of a univariate polynomial and its splitting into factors
• On the complexity of the Descartes method when using approximate arithmetic
• An efficient algorithm for the complex roots problem
• Root-neededness and approximations of neededness
• scientific article; zbMATH DE number 5850072 (Why is no real title available?)
• On the Complexity of Reliable Root Approximation
• Separating linear forms and rational univariate representations of bivariate systems
• Root refinement for real polynomials using quadratic interval refinement
• Computing real roots of real polynomials
• Certified complex root isolation via adaptive root separation bounds
• A simple but exact and efficient algorithm for complex root isolation
• On the complexity of isolating real roots and computing with certainty the topological degree

This page was built for publication: From approximate factorization to root isolation

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