Bounds for polynomials on algebraic numbers and application to curve topology

DOI10.1007/s00454-021-00353-wzbMath1486.14074arXiv1807.10622OpenAlexW4289420046MaRDI QIDQ2118214

Michael Sagraloff, Daouda Niang Diatta, Fabrice Rouillier, Sény Diatta, Marie-Françoise Roy

Publication date: 22 March 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.10622

zbMATH Keywords

singular pointsresultantsanalysis of algorithmsreal algebraic curvesbit complexitygeneralized discriminantamortized bounds on algebraic numbersexact topology computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Plane and space curves (14H50) Computational aspects of algebraic curves (14Q05) Topology of real algebraic varieties (14P25) Solving polynomial systems; resultants (13P15)

Related Items

\texttt{PTOPO}: computing the geometry and the topology of parametric curves, Computing the topology of the image of a parametric planar curve under a birational transformation, Algorithm for Connectivity Queries on Real Algebraic Curves, On Isolating Roots in a Multiple Field Extension, p-adic algorithm for bivariate Gröbner bases, Avoiding the general position condition when computing the topology of a real algebraic plane curve defined implicitly

Cites Work

• Unnamed Item
• Unnamed Item
• Solving bivariate systems using rational univariate representations
• Exact symbolic-numeric computation of planar algebraic curves
• Root refinement for real polynomials using quadratic interval refinement
• Computing real roots of real polynomials
• On the topology of real algebraic plane curves
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Topology and arrangement computation of semi-algebraic planar curves
• A worst-case bound for topology computation of algebraic curves
• 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
• Efficient topology determination of implicitly defined algebraic plane curves.
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• On the complexity of computing with planar algebraic curves
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• A New Algorithm for Long Integer Cube Computation with Some Insight into Higher Powers
• From approximate factorization to root isolation
• On the boolean complexity of real root refinement
• On the computation of the topology of a non-reduced implicit space curve
• Complete subdivision algorithms, II
• Regularity Criteria for the Topology of Algebraic Curves and Surfaces
• Algorithms in real algebraic geometry