@inproceedings{17776480dd1940ca81a7523def018a89,
title = "Amortized bound for root isolation via sturm sequences",
abstract = "This paper presents two results on the complexity of root isolation via Sturm sequences. Both results exploit amortization arguments. For a square-free polynomial A(X) of degree d with L-bit integer coefficients, we use an amortization argument to show that all the roots, real or complex, can be isolated using at most 0(dL + dlgd) Sturm probes. This extends Davenport's result for the case of isolating all real roots. We also show that a relatively straightforward algorithm, based on the classical subresultant PQS, allows us to evaluate the Sturm sequence of A(X) at rational {\~O}(dL)-bit values in time {\~O}(d3L); here the {\~O}-notation means we ignore logarithmic factors. Again, an amortization argument is used. We provide a family of examples to show that such amortization is necessary.",
keywords = "Complexity, Davenport-Mahler bound, Root isolation, Separation bound, Sturm sequence, Subresultant",
author = "Zilin Du and Vikram Sharma and Yap, {Chee K.}",
note = "Publisher Copyright: {\textcopyright} 2007 Birkh{\"a}user Verlag Basel/Switzerland.; International Workshop on Symbolic-Numeric Computation, SNC 2005 ; Conference date: 19-07-2005 Through 21-07-2005",
year = "2007",
doi = "10.1007/978-3-7643-7984-1_8",
language = "English (US)",
isbn = "9783764379834",
series = "Trends in Mathematics",
publisher = "Springer International Publishing",
pages = "113--129",
editor = "Dongming Wang and Dongming Wang and Lihong Zhi",
booktitle = "Symbolic-Numeric Computation",
}