W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Given a polynomial p(z) of degree n with integer coefficients, whose absolute values are bounded above by 2m, and a specified integer μ, we show that the problem of determining all roots of p with error less than 2-μ is in the parallel complexity class NC. To do this, we construct an algorithm which runs on at most D(n + m + μ)f processors in at most C loge(n + m - μ) parallel steps, where the constants C, D, e, f are given in terms of the corresponding processor and time bounds for the computation of certain elementary polynomial and matrix operations. In fact, one can easily see that the time complexity is O(log3(n + m + μ)). Thus, the algorithm presented here extends the algorithm of Ben-Or, Feig, Kozen, and Tiwari by removing the severe restriction that all the roots of p(z) be real. © 1994 Academic Press, Inc. All rights reserved.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Charles Micchelli
Journal of Approximation Theory