Bounds for polynomials on algebraic numbers and application to curve topology

DOI10.1007/S00454-021-00353-WzbMATH Open1486.14074arXiv1807.10622OpenAlexW4289420046MaRDI QIDQ2118214FDOQ2118214

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)

Abstract: Let $PinmathbbZ[X,Y]$ be a given square-free polynomial of total degree $d$ with integer coefficients of bitsize less than $au$, and let $V_{mathbbR}(P):=(x,y)inmathbb{R}^2,P(x,y)=0$ be the real planar algebraic curve implicitly defined as the vanishing set of $P$. We give a deterministic and certified algorithm to compute the topology of $V_{mathbbR}(P)$ in terms of a straight-line planar graph $mathcalG$ that is isotopic to $V_{mathbbR}(P)$. Our analysis yields the upper bound $ildeO(d^{5}au+d^6)$ on the bit complexity of our algorithm, which matches the current record bound for the problem of computing the topology of a planar algebraic curve However, compared to existing algorithms with comparable complexity, our method does not consider any change of coordinates, and the returned graph $mathcalG$ yields the cylindrical algebraic decomposition information of the curve. Our result is based on two main ingredients: First, we derive amortized quantitative bounds on the the roots of polynomials with algebraic coefficients as well as adaptive methods for computing the roots of such polynomials that actually exploit this amortization. Our second ingredient is a novel approach for the computation of the local topology of the curve in a neighborhood of all critical points.

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

Recommendations

• A worst-case bound for topology computation of algebraic curves
• On the computation of the topology of plane curves
• On the complexity of computing with planar algebraic curves
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• On the topology of planar algebraic curves

zbMATH Keywords

analysis of algorithmssingular pointsresultantsbit complexityreal algebraic curvesgeneralized 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) Topology of real algebraic varieties (14P25) Computational aspects of algebraic curves (14Q05) Solving polynomial systems; resultants (13P15)

Cites Work

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

Cited In (12)

• A worst-case bound for topology computation of algebraic curves
• \texttt{PTOPO}: computing the geometry and the topology of parametric curves
• Bounding curves in algebraic surfaces by genus and Chern numbers
• p-adic algorithm for bivariate Gröbner bases
• Computing the topology of the image of a parametric planar curve under a birational transformation
• Avoiding the general position condition when computing the topology of a real algebraic plane curve defined implicitly
• Algorithm for Connectivity Queries on Real Algebraic Curves
• On Isolating Roots in a Multiple Field Extension
• On the topology of polynomials with bounded integer coefficients
• Computing the non-properness set of real polynomial maps in the plane
• An improved complexity bound for computing the topology of a real algebraic space curve
• Polynomial bounds for Arakelov invariants of Belyi curves. With an appendix by Peter Bruin.

This page was built for publication: Bounds for polynomials on algebraic numbers and application to curve topology

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