Bounds for polynomials on algebraic numbers and application to curve topology

DOI10.1007/S00454-021-00353-WMaRDI QIDQ2118214zbMATH OpenOpenAlexFDO

Authors Daouda Niang Diatta, Sény Diatta, Fabrice Rouillier, Michael Sagraloff, 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

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)

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.

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

Cites work

• A New Algorithm for Long Integer Cube Computation with Some Insight into Higher Powers
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• A worst-case bound for topology computation of algebraic curves
• Algorithms in real algebraic geometry
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Complete subdivision algorithms, II
• Computing real roots of real polynomials
• Efficient topology determination of implicitly defined algebraic plane curves.
• Exact symbolic-numeric computation of planar algebraic curves
• Fast and exact geometric analysis of real algebraic plane curves
• From approximate factorization to root isolation
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Modern computer algebra
• On the Boolean complexity of real root refinement
• On the complexity of computing with planar algebraic curves
• On the computation of the topology of a non-reduced implicit space curve
• On the topology of real algebraic plane curves
• Regularity Criteria for the Topology of Algebraic Curves and Surfaces
• Root refinement for real polynomials using quadratic interval refinement
• Solving bivariate systems using rational univariate representations
• Topology and arrangement computation of semi-algebraic planar curves
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Univariate real root isolation in an extension field and applications

Cited in

(19)

• 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
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On the computation of the topology of plane curves
• Avoiding the general position condition when computing the topology of a real algebraic plane curve defined implicitly
• Quantitative result on the deviation of a real algebraic curve from its vertical tangents
• On the complexity of computing with planar algebraic curves
• Algorithm for Connectivity Queries on Real Algebraic Curves
• On the topology of polynomials with bounded integer coefficients
• On Isolating Roots in a Multiple Field Extension
• Computing the non-properness set of real polynomial maps in the plane
• On the complexity of real solving bivariate systems
• An improved complexity bound for computing the topology of a real algebraic space curve
• From approximate factorization to root isolation
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• 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)