Polynomial Real Root Isolation by Means of Root Radii Approximation
Polynomial Real Root Isolation by Means of Root Radii Approximation
复制标题
通过根半径近似的多项式实根隔离
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Liang Zhao
中科院分区：
文献类型：
--
作者：
V. Pan;Liang Zhao
单变量多项式根发现是一个经典的主题，对于现代计算仍然很重要。通常，人们只是寻求真实系数多项式的真正根源，并且要挑战它们更快地近似它们。挑战很长一段时间以来都知道，并且对主题进行了深入的研究。如果多项式没有非现实的根，则可以以低计算成本近似真正的根，但是对于高度多项式，非现实根通常比真实的根大得多。简单和孤立的真实根的布尔成本的边界已经降低至几乎最佳，但是在隔离真正根基的阶段，成功的范围更加有限。通过通过Schonhage重新访问1982年的算法来近似root Radii的近似，即根和原点之间的距离，我们获得了很大的进步：我们隔离了在布尔成本主导的多项式的简单且条件良好的真实根源通过几乎最佳的界限，用于细化此类根。我们使用IEEE标准双精度进行的基准多项式测试的数值测试表明，所得的几乎最佳的真实根膜实际上是有希望的。我们的技术很简单，它们的功率和应用范围可能与已知的有效方法相结合。最后，我们指出了一些有希望的方向，以隔离复杂的根和根簇。
Univariate polynomial root-finding is a classical subject, still important for modern computing. Frequently one seeks just the real roots of a real coefficient polynomial and is challenged to approximate them faster. The challenge is known for long time, and the subject has been intensively studied. The real roots can be approximated at a low computational cost if the polynomial has no non-real roots, but for high degree polynomials, non-real roots are typically much more numerous than the real ones. The bounds on the Boolean cost of the refinement of the simple and isolated real roots have been decreased to nearly optimal, but the success has been more limited at the stage of the isolation of real roots. By revisiting the algorithm of 1982 by Schonhage for the approximation of the root radii, that is, the distances between the roots and the origin, we obtain substantial progress: we isolate the simple and well conditioned real roots of a polynomial at the Boolean cost dominated by the nearly optimal bounds for the refinement of such roots. Our numerical tests with benchmark polynomials performed with the IEEE standard double precision show that the resulting nearly optimal real root-finder is practically promising. Our techniques are simple, and their power and application range may increase in combination with the known efficient methods. At the end we point out some promising directions to the isolation of complex roots and root clusters.
影响因子：
0.7
作者：
Sagraloff, Michael;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt