From approximate factorization to root isolation with application to cylindrical algebraic decomposition

DOI10.1016/j.jsc.2014.02.001zbMath1357.68305arXiv1301.4870OpenAlexW2134534233MaRDI QIDQ2252120

Pengming Wang, Kurt Mehlhorn, Michael Sagraloff

Publication date: 16 July 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

cylindrical algebraic decompositioncomplexity analysisbivariate polynomial systemroot findingtopology computationroot isolationroot refinementcurve analysis

Mathematics Subject Classification ID

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

Related Items

On μ-symmetric polynomials, Near optimal subdivision algorithms for real root isolation, Solving bivariate systems using rational univariate representations, Symmetry detection of rational space curves from their curvature and torsion, A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration, Fast evaluation and root finding for polynomials with floating-point coefficients, Algorithm for Connectivity Queries on Real Algebraic Curves, On Isolating Roots in a Multiple Field Extension, Nearly optimal refinement of real roots of a univariate polynomial, Counting solutions of a polynomial system locally and exactly, On the Topology of the Intersection Curve of Two Real Parameterized Algebraic Surfaces, Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials, Computing real roots of real polynomials, A new method to compute the singularities of offsets to rational plane curves, Univariate real root isolation in an extension field and applications, Bounds for polynomials on algebraic numbers and application to curve topology

Uses Software

• SqFreeEVAL
• na20
• Lgp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact symbolic-numeric computation of planar algebraic curves
• A deterministic algorithm for isolating real roots of a real polynomial
• On the topology of real algebraic plane curves
• SqFreeEVAL: An (almost) optimal real-root isolation algorithm
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• A worst-case bound for topology computation of algebraic curves
• Complete numerical isolation of real roots in zero-dimensional triangular systems
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• Quasi-gcd computations
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• On nearest-neighbor graphs
• Ten methods to bound multiple roots of polynomials
• An efficient method for analyzing the topology of plane real algebraic curves.
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Finding a cluster of zeros of univariate polynomials
• PRIMES is in P
• Interval arithmetic in cylindrical algebraic decomposition
• Numerical methods for roots of polynomials. II
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Cylindrical algebraic decomposition using validated numerics
• On location and approximation of clusters of zeros of analytic functions
• Upperbounds for roots of polynomials
• Root isolation for bivariate polynomial systems with local generic position method
• Rational univariate representations of bivariate systems and applications
• Separating linear forms for bivariate systems
• From approximate factorization to root isolation
• In Praise of Numerical Computation
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• On the complexity of solving a bivariate polynomial system
• When Newton meets Descartes
• Efficient real root approximation
• Univariate real root isolation in an extension field
• A simple but exact and efficient algorithm for complex root isolation
• Computer Algebra in Scientific Computing
• On Solving Systems of Bivariate Polynomials
• Algorithms in real algebraic geometry