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

bivariate polynomial systemcomplexity analysiscurve analysiscylindrical algebraic decompositionroot findingroot isolationroot refinementtopology computation

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(26)

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

Describes a project that uses

Uses Software

• SqFreeEVAL
• na20
• Lgp

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)