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

DOI10.1016/J.JSC.2014.02.001MaRDI QIDQ2252120zbMATH OpenOpenAlexFDO

Authors K. Mehlhorn, Michael Sagraloff, Pengming Wang

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

complexity analysiscylindrical algebraic decompositionroot findingtopology computationroot isolationroot refinementcurve analysisbivariate polynomial system

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) 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)

Abstract: We present an algorithm for isolating the roots of an arbitrary complex polynomial $p$ that also works for polynomials with multiple roots provided that the number $k$ of distinct roots is given as part of the input. It outputs $k$ pairwise disjoint disks each containing one of the distinct roots of $p$, and its multiplicity. The algorithm uses approximate factorization as a subroutine. In addition, we apply the new root isolation algorithm to a recent algorithm for computing the topology of a real planar algebraic curve specified as the zero set of a bivariate integer polynomial and for isolating the real solutions of a bivariate polynomial system. For input polynomials of degree $n$ and bitsize $au$, we improve the currently best running time from $O(n^{9}au+n^{8}a{u}^2)$ (deterministic) to $O(n^6+n^{5}au)$ (randomized) for topology computation and from $O(n^8+n^{7}au)$ (deterministic) to $O(n^6+n^{5}au)$ (randomized) for solving bivariate systems.

Recommendations

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

Cites work

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

Cited in

(24)

• Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
• Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
• Solving bivariate systems using rational univariate representations
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Certified complex root isolation via adaptive root separation bounds
• Near optimal subdivision algorithms for real root isolation
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Fast evaluation and root finding for polynomials with floating-point coefficients
• A new method to compute the singularities of offsets to rational plane curves
• Symmetry detection of rational space curves from their curvature and torsion
• Counting solutions of a polynomial system locally and exactly
• On the Topology of the Intersection Curve of Two Real Parameterized Algebraic Surfaces
• Computing real roots of real polynomials
• Univariate real root isolation over a single logarithmic extension of real algebraic numbers
• Algorithm for Connectivity Queries on Real Algebraic Curves
• Univariate real root isolation in an extension field and applications
• On \(\mu\)-symmetric polynomials
• Nearly optimal refinement of real roots of a univariate polynomial
• On Isolating Roots in a Multiple Field Extension
• Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
• An improved complexity bound for computing the topology of a real algebraic space curve
• Bounds for polynomials on algebraic numbers and application to curve topology
• From approximate factorization to root isolation

Describes a project that uses

Uses Software

• Lgp
• na20
• SqFreeEVAL

This page was built for publication: From approximate factorization to root isolation with application to cylindrical algebraic decomposition

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