Polynomial Root-Finding Algorithms and Branched Covers
Polynomial Root-Finding Algorithms and Branched Covers
复制标题
多项式求根算法和分支覆盖
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Sutherland
中科院分区：
文献类型：
--
作者：
Myong;S. Sutherland
一个家庭的寻根算法的构造，结合知识的分支覆盖结构的多项式与路径提升算法，寻找个人的根源。特别地，该族包括一个算法，该算法计算$d$次多项式的$n $-因子分解，其算术复杂度为$Order{d（log d）^2|对数|+d^2（log d）^2}$。目前，这种复杂性在程度上是最有名的。
A family of root-finding algorithms is constructed that combines knowledge of the branched covering structure of a polynomial with a path-lifting algorithm for finding individual roots. In particular, the family includes an algorithm that computes an $epsilon$-factorization of a polynomial of degree $d$ that has an arithmetic complexity of $Order{d(log d)^2|logepsilon| +d^2(log d)^2}$. At the present time, this complexity is the best known in terms of the degree.