Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

On the Boolean complexity of real root refinement

Victor Pan 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
Inria Paris-Rocquencourt, LIP6 - Laboratoire d'Informatique de Paris 6
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} algorithm (also called the {\em Bisection of the Exponents}), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of $t=2^{-L}$. The algorithm has Boolean complexity ${\widetilde{\mathcal{O}}_B}(d^2 \tau + d L )$. Our algorithms support the same complexity bound for the refinement of $r$ roots, for any $r\le d$.
Document type :
Conference papers
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-00816214
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Thursday, April 25, 2013 - 2:10:08 PM
Last modification on : Friday, January 21, 2022 - 3:22:23 AM
Long-term archiving on: : Monday, April 3, 2017 - 11:38:14 PM

File

pt-refine.pdf
Files produced by the author(s)

Identifiers

Citation

Victor Pan, Elias Tsigaridas. On the Boolean complexity of real root refinement. ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. ⟨10.1145/2465506.2465938⟩. ⟨hal-00816214v3⟩

Share

Metrics

Record views

202

Files downloads

413