### 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 language | English (US) |
---|---|

Title of host publication | Symbolic-Numeric Computation |

Editors | Dongming Wang, Dongming Wang, Lihong Zhi |

Publisher | Springer International Publishing |

Pages | 113-129 |

Number of pages | 17 |

ISBN (Print) | 9783764379834 |

DOIs | |

State | Published - 2007 |

Event | International Workshop on Symbolic-Numeric Computation, SNC 2005 - Xian, China Duration: Jul 19 2005 → Jul 21 2005 |

### Publication series

Name | Trends in Mathematics |
---|---|

Volume | 41 |

ISSN (Print) | 2297-0215 |

ISSN (Electronic) | 2297-024X |

### Other

Other | International Workshop on Symbolic-Numeric Computation, SNC 2005 |
---|---|

Country | China |

City | Xian |

Period | 7/19/05 → 7/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

*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