Tree Breadth of the Continued Fractions Root Finding Method

Kyriakos Kalorkoti

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

Abstract

The continued fractions algorithm for isolating the real roots of polynomials with certainty is one of the most efficient known and widely used. It can be viewed as exploring a tree created by a sequence of simple transformations. In this paper we produce new upper bounds for the breadth of the tree that are significantly smaller than the degree of the input polynomial. We also consider the expected breadth under a reasonable distribution and derive a bound, subject to a plausible assumption, that grows logarithmically with the degree and coefficient size.
Original languageEnglish
Title of host publicationNew Trends in Algebras and Combinatorics
Subtitle of host publicationProceedings of the 3rd International Congress in Algebras and Combinatorics (ICAC2017)
PublisherWorld Scientific
Pages203-227
Number of pages23
ISBN (Electronic)978-981-121-548-3
ISBN (Print)978-981-121-546-9
DOIs
Publication statusPublished - 2 Mar 2020
EventThe Third International Congress in Algebras and Combinatorics - The Open University of Hong Kong, Hong Kong, Hong Kong
Duration: 25 Aug 201728 Aug 2017
http://plbpc001.ouhk.edu.hk/ocean2017/index.html

Conference

ConferenceThe Third International Congress in Algebras and Combinatorics
Abbreviated titleICAC 2017
CountryHong Kong
CityHong Kong
Period25/08/1728/08/17
Internet address

Keywords

  • Polynomial roots
  • continued fractions
  • tree breadth

Fingerprint Dive into the research topics of 'Tree Breadth of the Continued Fractions Root Finding Method'. Together they form a unique fingerprint.

Cite this