About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Specified precision polynomial root isolation is in NC
Abstract
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.