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
Country/TerritoryChina
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