Beyond Worst-Case Analysis for Root Isolation Algorithms
Beyond Worst-Case Analysis for Root Isolation Algorithms
复制标题
根隔离算法超越最坏情况分析
DOI：
10.1145/3476446.3535475
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tsigaridas, Elias
中科院分区：
文献类型：
--
作者：
Ergür, Alperen;Tonelli-Cueto, Josué;Tsigaridas, Elias
分离单变量多项式的实根是符号计算中的一个基本问题，并且可以说是计算数学中最重要的问题之一。这个问题有着悠久的历史，有许多巧妙的算法，并提供了一个活跃的研究领域。然而，寻根算法的最坏情况分析与其实际性能并不相关。我们为具有整数系数的多项式开发了一个平滑分析框架，以弥合复杂性估计和实际性能之间的差距。在此设置中，我们得出笛卡尔求解器分离系数均匀分布的多项式实根的预期位复杂度为 ÕB(d2 + dτ)，其中 d 是多项式的次数，τ 是系数的位大小。
Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. We develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of Descartes solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is ÕB(d2 + dτ), where d is the degree of the polynomial and τ the bitsize of the coefficients.
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
影响因子：
1
作者：
M. Rudelson;R. Vershynin
通讯作者：
R. Vershynin
影响因子：
3
作者：
D. Castro;J. L. Montaña;L. M. Pardo;Jorge San Martín
通讯作者：
Jorge San Martín
单变量多项式近似的新数据结构及其在根隔离、数值多点评估和其他问题中的应用
DOI：
--
发表时间：
2021
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
G. Moroz
通讯作者：
G. Moroz
数值分析师的一些评论
DOI：
--
发表时间：
1971
期刊：
JACM
影响因子：
--
作者：
J. H. Wilkinson
通讯作者：
J. H. Wilkinson