@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",

}