• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms - ESA 2006; Lecture Notes in Computer Science; 4168 >Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
【24h】

Univariate Polynomial Real Root Isolation: Continued Fractions Revisited

机译：单变量多项式实根隔离：续分数

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real numbers. We improve the previously known bound by a factor of dτ, where d is the polynomial degree and τ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is O_B(d~4τ~2) using a standard bound on the expected bitsize of the integers in the continued fraction expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source C++ implementation in the algebraic library SYNAPS, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.
机译：我们介绍了使用实数的连续分数展开式关于整数单变量多项式的实根隔离的算法，复杂度和实现结果。我们以系数dτ改善先前已知的边界，其中d是多项式度，τ约束系数位大小，从而通过精确方法匹配当前记录的复杂度以进行真正的根隔离。即，使用在连续分数扩展中整数的预期比特大小上的标准界限，复杂度界限为O_B（d〜4τ〜2）。我们展示了如何在相同的复杂度内计算多重性并将算法扩展到非平方无穷多项式。最后，我们在代数库SYNAPS中提出了一种有效的开源C ++实现，并说明了与其他可用软件相比的效率。我们使用系数位最大为8000，阶次为1000的多项式。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号