New Practical Advances in Polynomial Root Clustering
New Practical Advances in Polynomial Root Clustering
复制标题
多项式根聚类的新实用进展
DOI：
10.1007/978-3-030-43120-4_11
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pan, V
中科院分区：
文献类型：
--
作者：
Imbach, R;Pan, V
我们报告了一项正在进行的关于具有实数或复数系数的单变量多项式复数根的聚类算法的工作。与之前的最佳细分算法一样，我们的寻根器即使对于由黑匣子给出的多项式的多个根（用于近似其系数）也是稳健的，并且它们的复杂性至少与复杂平面（例如圆盘或正方形）上的感兴趣区域（ROI）中的根的数量成比例地降低，但我们大大加强了之前算法的主要成分。我们为新的计数测试奠定了基础，该测试本质上相当于评估多项式及其导数，这是一个主要好处，例如对于稀疏多项式sp。此外，通过在大约点处进行评估（相对于先前的有序记录），我们在其轮廓附近没有 p 根的圆盘中输出正确的根数。我们的第二个也是不太重要的贡献涉及具有实数系数的多项式的细分算法。我们的测试证明了所提出算法的强大功能。
We report an ongoing work on clustering algorithms for complex roots of a univariate polynomialpof degreedwith real or complex coefficients. As in their previous best subdivision algorithms our root-finders are robust even for multiple roots of a polynomial given by a black box for the approximation of its coefficients, and their complexity decreases at least proportionally to the number of roots in a region of interest (ROI) on the complex plane, such as a disc or a square, but we greatly strengthen the main ingredient of the previous algorithms. We build the foundation for a new counting test that essentially amounts to the evaluation of a polynomialpand its derivative, which is a major benefit, e.g., for sparse polynomialsp. Moreover with evaluation at aboutpoints (versus the previous record of orderd) we output correct number of roots in a disc whose contour has no roots ofpnearby. Our second and less significant contribution concerns subdivision algorithms for polynomials with real coefficients. Our tests demonstrate the power of the proposed algorithms.