Files:
Abstract:
We assume that a real square-free polynomial $A$ has a degree $d$, a maximum coefficient bitsize $\tau$ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then we combine the Double Exponential Sieve (also called the Bisection of the Exponents) algorithm, the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor $t=2^-L$. The algorithm has Boolean complexity $\sOB(d^2 \tau + d L )$.
BibTeX:
@InProceedings{pt-issac-2013,
author = {Victor~Y. Pan and Elias~P. Tsigaridas},
title = {On the Boolean complexity of real root refinement},
booktitle = ISSAC_2013,
year = 2013,
address = {Boston, USA},
month = {Jun},
publisher = {ACM},
pages = "299--306",
abstract = "We assume that a real square-free polynomial $A$ has
a degree $d$, a maximum coefficient bitsize $\tau$
and a real root lying in an isolating interval and
having no nonreal roots nearby (we quantify this
assumption). Then we combine the {\em Double
Exponential Sieve} (also called the {\em Bisection
of the Exponents}) algorithm, the bisection, and
Newton iteration to decrease the width of this
inclusion interval by a factor $t=2^{-L}$. The
algorithm has Boolean complexity $\sOB(d^2 \tau + d
L )$.",
url = {http://hal.inria.fr/hal-00816214},
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02