R.T. Farouki, C. Neff
Mathematics of Computation
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.
R.T. Farouki, C. Neff
Mathematics of Computation
D. Coppersmith, C. Neff
SODA 1994
R.T. Farouki, C. Neff, et al.
ACM Transactions on Graphics (TOG)
R.T. Farouki, C. Neff
Mathematics of Computation