Amortized bound for root isolation via sturm sequences

Zilin Du, Vikram Sharma, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Õ(dL)-bit values in time Õ(d3L); here the Õ-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.

Original languageEnglish (US)
Title of host publicationSymbolic-Numeric Computation
EditorsDongming Wang, Dongming Wang, Lihong Zhi
PublisherSpringer International Publishing
Pages113-129
Number of pages17
ISBN (Print)9783764379834
DOIs
StatePublished - 2007
EventInternational Workshop on Symbolic-Numeric Computation, SNC 2005 - Xian, China
Duration: Jul 19 2005Jul 21 2005

Publication series

NameTrends in Mathematics
Volume41
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X

Other

OtherInternational Workshop on Symbolic-Numeric Computation, SNC 2005
CountryChina
CityXian
Period7/19/057/21/05

Keywords

  • Complexity
  • Davenport-Mahler bound
  • Root isolation
  • Separation bound
  • Sturm sequence
  • Subresultant

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Amortized bound for root isolation via sturm sequences'. Together they form a unique fingerprint.

  • Cite this

    Du, Z., Sharma, V., & Yap, C. K. (2007). Amortized bound for root isolation via sturm sequences. In D. Wang, D. Wang, & L. Zhi (Eds.), Symbolic-Numeric Computation (pp. 113-129). (Trends in Mathematics; Vol. 41). Springer International Publishing. https://doi.org/10.1007/978-3-7643-7984-1_8