×

An efficient algorithm for the complex roots problem. (English) Zbl 0888.12005

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 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.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0632.65052
PDFBibTeX XMLCite
Full Text: DOI Link