Improved bounds for Continued Fractions variants for real root isolation

摘要：

We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using (variants of) the continued fraction algorithm (CF). We introduce a novel way to compute a lower bound on the positive real roots of univariate polynomials. This allows us to derive a worst case bound of (O)B(dG+d4T2+d3T2) for isolating the real roots of a polynomial with integer coefficients using the classic variant of CF introduced by Akritas, where d is the degree of the polynomial and r the maximum bitsize of its coefficients. This improves the previous bound of Sharma by a factor of d3 and matches the bound derived by Mehlhorn and Ray for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.

作者: Elias P.Tsigaridas

作者单位: Computer Science Department Aarhus University IT-parken, Abogade 34 DK 8200 (A)rhus N, Denmark

会议类型: 国际会议

会议名称: The Fourth International Conference on Mathematical Aspects of Computer and Information Sciences(第四届计算机与信息科学中的数学方法国际会议 MACIS 2011)

会议地点: 北京

会议语种:英文

页码: 226-237

在线出版日期: 2011-10-21（万方平台首次上网日期，不代表论文的发表时间）