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

DOI10.1016/J.JSC.2014.02.001zbMATH Open1357.68305arXiv1301.4870OpenAlexW2134534233MaRDI QIDQ2252120

Author name not available (Why is that?)

Publication date: 16 July 2014

Published in: (Search for Journal in Brave)

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.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)