An efficient algorithm for the complex roots problem (Q2565192): Difference between revisions

Improving their own algorithm of 1994, the authors present an algorithm to isolate all complex roots of an \(n\)-degree polynomial \(f=z^n+\sum_{i=0}^{n-1} c_i z^i\) with specified precision \(2^{-\mu}\) in \(O(n \log^5 n \log B)\) arithmetic operations, where \(B= \chi + \mu\), \(\chi=\max \{ m, n\}\), \(|c_i|< 2^m, i=0,\ldots, n-1\). The algorithm improves the upper bound for the complex roots problem due to \textit{V. Y. Pan} [Comput. Math. Appl. 14, 285-304 (1987; Zbl 0632.65052)] and approximates its complexity to those of basic operations such as interpolation and evaluation. The algorithm hinges on a balance splitting technique in which an \(n\)-degree polynomial is translated to a coordinate system where it can be approximately factored into smaller degree polynomials (of degree \(\leq n/2\)). Such a technique is based on the notion of splitting set of points for complex polynomials developed by the authors, which may be seen as a generalization of the splitting point idea, used to obtain a geometrically balanced set of roots for totally real polynomials. A remarkable property of the algorithm presented is that it does not need any assumption about the root separation of \(f\). The authors also show that their splitting procedure works without modification in the Boolean model of arithmetic. The complexity in the Boolean model is only increased by a multiplicative factor (explicitly determined). The paper also discusses a parallel implementation of the algorithm. It is not clear whether the algorithm can be translated to an efficient numerical routine, but its relatively simple description seems to indicate that it is possible to simplify the presentation, which may lead to an actual implementation.