An efficient algorithm for the complex roots problem (Q2565192): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Q1058845 / rank | |||
Property / author | |||
Property / author: John H. Reif / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2031561848 / rank | |||
Normal rank |
Latest revision as of 00:22, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm for the complex roots problem |
scientific article |
Statements
An efficient algorithm for the complex roots problem (English)
0 references
27 May 1998
0 references
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.
0 references
complex roots
0 references
polynomials
0 references
complexity
0 references
algorithm
0 references