Complexity Analysis of Root Clustering for a Complex Polynomial

DOI10.1145/2930889.2930939zbMATH Open1364.30011arXiv2105.05183OpenAlexW2484278949MaRDI QIDQ2985810

Author name not available (Why is that?)

Publication date: 10 May 2017

Published in: (Search for Journal in Brave)

Abstract: Let $F(z)$ be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural $varepsilon$-clusters of roots of $F(z)$ in some box region $B_0$ in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of $F$ are provided by means of an oracle at the cost of reading the coefficients. Our algorithmic techniques come from a companion paper (Becker et al., 2018) and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Sch"onhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Complexity Analysis of Root Clustering for a Complex Polynomial

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