## An efficient algorithm for the complex roots problem

Publication ,  Journal Article
Neff, AC; Reif, JH
Published in: Journal of Complexity
January 1, 1996

Given a univariate polynomial f(z) of degree n with complex coefficients, whose norms are less than 2m in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2-μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexity O(n log5 n log B), where b = χ + μ, and χ = max{n, m}. This improves on the previous best known algorithm of Pan for the problem, which has complexity O(n2 log2 n log(m + μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation of f, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = [n(B + log n + 3)] bits of the binary representations of the real and imaginary parts of each of the coefficients of f. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where φ = π + 2n2χ + 3(n + log n + 1) + n2 + 2 log n) + log log n. and π = μ 2n + nχ + log log n + 5. Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor of M(φ) (where M(ψ) = O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and "centered" points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel time O(log6 n log B) using n processors. © 1996 Academic Press, Inc.

## Published In

Journal of Complexity

0885-064X

January 1, 1996

12

2

## Start / End Page

81 / 115

• Numerical & Computational Mathematics
• 4901 Applied mathematics
• 4613 Theory of computation
• 0802 Computation Theory and Mathematics
• 0103 Numerical and Computational Mathematics
• 0102 Applied Mathematics

### Citation

APA
Chicago
ICMJE
MLA
NLM
Neff, A. C., & Reif, J. H. (1996). An efficient algorithm for the complex roots problem. Journal of Complexity, 12(2), 81–115. https://doi.org/10.1006/jcom.1996.0008
Neff, A. C., and J. H. Reif. “An efficient algorithm for the complex roots problem.” Journal of Complexity 12, no. 2 (January 1, 1996): 81–115. https://doi.org/10.1006/jcom.1996.0008.
Neff AC, Reif JH. An efficient algorithm for the complex roots problem. Journal of Complexity. 1996 Jan 1;12(2):81–115.
Neff, A. C., and J. H. Reif. “An efficient algorithm for the complex roots problem.” Journal of Complexity, vol. 12, no. 2, Jan. 1996, pp. 81–115. Scopus, doi:10.1006/jcom.1996.0008.
Neff AC, Reif JH. An efficient algorithm for the complex roots problem. Journal of Complexity. 1996 Jan 1;12(2):81–115.

## Published In

Journal of Complexity

0885-064X

January 1, 1996

12

2

81 / 115