论文标题
评估orac给出的多项式的聚类根的加速细分
Accelerated Subdivision for Clustering Roots of Polynomials given by Evaluation Oracles
论文作者
论文摘要
为了寻求设计，分析和实施了一个细分算法，用于寻找由Oracles进行评估的单变量多项式的复杂根，我们提出了子词素，允许对这种多项量的复杂根部聚类的细胞分量进行实质性加速。我们依靠cauchy和近似于固定复合盘中根的功率总和，并且可以在少数评估中计算 - 该程度上的二旋gar素。我们描述了根部排除，根计数，根半径近似和将光盘缩合到其包含的根群的过程，称为$ \ varepsilon $ -compression。为了证明我们的算法的效率，我们将它们结合在原型的根群集算法中。为了计算可以快速评估的多项式根部的簇，我们的实现与用户选择的root查找，mpsolve竞争。
In our quest for the design, the analysis and the implementation of a subdivision algorithm for finding the complex roots of univariate polynomials given by oracles for their evaluation, we present sub-algorithms allowing substantial acceleration of subdivision for complex roots clustering for such polynomials. We rely on Cauchy sums which approximate power sums of the roots in a fixed complex disc and can be computed in a small number of evaluations --polylogarithmic in the degree. We describe root exclusion, root counting, root radius approximation and a procedure for contracting a disc towards the cluster of root it contains, called $\varepsilon$-compression. To demonstrate the efficiency of our algorithms, we combine them in a prototype root clustering algorithm. For computing clusters of roots of polynomials that can be evaluated fast, our implementation competes advantageously with user's choice for root finding, MPsolve.
