Old and New Nearly Optimal Polynomial Root-Finders
Old and New Nearly Optimal Polynomial Root-Finders
复制标题
新旧近乎最优多项式求根器
DOI：
10.1007/978-3-030-26831-2_26
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pan, Victor
中科院分区：
文献类型：
--
作者：
Pan, Victor
单变量多项式求根已经被研究了四千年，并且仍然是深入研究的主题。对于这一任务，已经提出并分析了数百个(如果不是数千个)有效的算法。1995年和2016年，人们设计了两种近似最优解的算法，分别基于多项式的递归分解和细分迭代，但在实践中这两种算法都被Ehrlich的函数迭代所取代。通过将因式分解技术与Ehrlich迭代和细分迭代相结合，我们设计了各种新的寻根器。它们在复杂平面、圆盘和线段上求根的估计复杂性方面与已知算法相匹配或取代，并有望在实际中具有竞争力。
Univariate polynomial root-finding has been studied for four millennia and still remains the subject of intensive research. Hundreds if not thousands of efficient algorithms for this task have been proposed and analyzed. Two nearly optimal solution algorithms have been devised in 1995 and 2016, based on recursive factorization of a polynomial and subdivision iterations, respectively, but both of them are superseded in practice by Ehrlich’s functional iterations. By combining factorization techniques with Ehrlich’s and subdivision iterations we devise a variety of new root-finders. They match or supersede the known algorithms in terms of their estimated complexity for root-finding on the complex plane, in a disc, and in a line segment and promise to be practically competitive.
登录
查看更多内容
采样绕数计算求凸紧区域多项式的根
DOI：
10.1007/978-3-030-26831-2_29
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Vitaly Zaderman;Liang Zhao
通讯作者：
Liang Zhao
DOI：
--
发表时间：
2015
期刊：
Computer Algebra in Scientific Computing
影响因子：
--
作者：
V. Pan;Liang Zhao
通讯作者：
Liang Zhao
DOI：
10.1007/978-3-319-96418-8_28
发表时间：
2018
期刊：
International Congress on Mathematical Software (ICMS
影响因子：
--
作者：
Imbach, Rémi;Pan, Victor;Yap, Chee
通讯作者：
Yap, Chee
将多项式分解为因子的格雷夫过程、类切比雪夫过程和卡迪纳尔过程
DOI：
10.1006/jcom.1996.0030
发表时间：
1996
期刊：
J. Complex.
影响因子：
--
作者：
Dario Bini;V. Pan
通讯作者：
V. Pan
影响因子：
2.9
作者：
Dario Bini;L. Gemignani;V. Pan
通讯作者：
Dario Bini;L. Gemignani;V. Pan