Complexity analysis of root clustering for a complex polynomial

Ruben Becker, Michael Sagraloff, Vikram Sharma, Juan Xu, Chee Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Let F(z) be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural 7epsi;-clusters of roots of F(z) in some box region B0 in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is twofold: 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 [3] and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Schonhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice.

Original languageEnglish (US)
Title of host publicationISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation
EditorsMarkus Rosenkranz
PublisherAssociation for Computing Machinery
Pages71-78
Number of pages8
ISBN (Electronic)9781450343800
DOIs
StatePublished - Jul 20 2016
Event41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016 - Waterloo, Canada
Duration: Jul 20 2016Jul 22 2016

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume20-22-July-2016

Other

Other41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016
CountryCanada
CityWaterloo
Period7/20/167/22/16

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Complexity analysis of root clustering for a complex polynomial'. Together they form a unique fingerprint.

Cite this