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
IEEE Transactions on Industry Applications
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 μ, it is shown that the problem of determining all roots of p with error less than 2-μ is in the parallel complexity class NC. To do this, an algorithm that runs on at most POLY (n + m + μ) processors with a parallel time complexity of O(log3(n + m + μ)) is constructed. This algorithm extends the algorithm of M. Ben-Or et al. (SIAM J. Comput., Vol. 17, pp. 1081-1092, 1988) by removing the severe restriction that all the roots of p(z) be real.