TY - GEN

T1 - Complexity analysis of root clustering for a complex polynomial

AU - Becker, Ruben

AU - Sagraloff, Michael

AU - Sharma, Vikram

AU - Xu, Juan

AU - Yap, Chee

N1 - Funding Information:
Supported by China Scholarship Council, No.20150602005.

PY - 2016/7/20

Y1 - 2016/7/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84984600078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984600078&partnerID=8YFLogxK

U2 - 10.1145/2930889.2930939

DO - 10.1145/2930889.2930939

M3 - Conference contribution

AN - SCOPUS:84984600078

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 71

EP - 78

BT - ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

A2 - Rosenkranz, Markus

PB - Association for Computing Machinery

T2 - 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016

Y2 - 20 July 2016 through 22 July 2016

ER -