Can I read From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition on EtoBox?

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition by Mehlhorn, Kurt; Sagraloff, Michael; Wang, Pengming is a scholarly article available to read on EtoBox.

What is From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition about?

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 $\tau$, we improve the currently best running time from $\tO(n^{9}\tau+n^{8}\tau^{2})$ (deterministic) to $\tO(n^{6}+n^{5}\tau)$ (randomized) for topology computation and from $\tO(n^{8}+n^{7}\tau)$ (deterministic) to $\tO(n^{6}+n^{5}\tau)$ (randomized) for solving bivariate systems.

Author

Mehlhorn, Kurt; Sagraloff, Michael; Wang, Pengming

Published

2013

Language

EN