Tree Breadth of the Continued Fractions Root Finding Method

Kyriakos Kalorkoti

doi:10.1142/9789811215476_0014

Tree Breadth of the Continued Fractions Root Finding Method

Kyriakos Kalorkoti

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	New Trends in Algebras and Combinatorics
Subtitle of host publication	Proceedings of the 3rd International Congress in Algebras and Combinatorics (ICAC2017)
Publisher	World Scientific
Pages	203-227
Number of pages	23
ISBN (Electronic)	978-981-121-548-3
ISBN (Print)	978-981-121-546-9
DOIs	https://doi.org/10.1142/9789811215476_0014
Publication status	Published - 2 Mar 2020
Event	The Third International Congress in Algebras and Combinatorics - The Open University of Hong Kong, Hong Kong, Hong Kong Duration: 25 Aug 2017 → 28 Aug 2017 http://plbpc001.ouhk.edu.hk/ocean2017/index.html

Conference

Conference	The Third International Congress in Algebras and Combinatorics
Abbreviated title	ICAC 2017
Country/Territory	Hong Kong
City	Hong Kong
Period	25/08/17 → 28/08/17
Internet address	http://plbpc001.ouhk.edu.hk/ocean2017/index.html

Keywords / Materials (for Non-textual outputs)

Polynomial roots
continued fractions
tree breadth

Access to Document

10.1142/9789811215476_0014Licence: All Rights Reserved

Continued Fractions MethodAccepted author manuscript, 361 KB

https://www.worldscientific.com/doi/abs/10.1142/9789811215476_0014Licence: All Rights Reserved

Cite this

@inproceedings{32d352ba5ca440db8fc7f3c9d6e88599,

title = "Tree Breadth of the Continued Fractions Root Finding Method",

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

keywords = "Polynomial roots, continued fractions, tree breadth",

author = "Kyriakos Kalorkoti",

year = "2020",

month = mar,

day = "2",

doi = "10.1142/9789811215476_0014",

language = "English",

isbn = "978-981-121-546-9",

pages = "203--227",

booktitle = "New Trends in Algebras and Combinatorics",

publisher = "World Scientific",

note = "The Third International Congress in Algebras and Combinatorics, ICAC 2017 ; Conference date: 25-08-2017 Through 28-08-2017",

url = "http://plbpc001.ouhk.edu.hk/ocean2017/index.html",

}

Kalorkoti, K 2020, Tree Breadth of the Continued Fractions Root Finding Method. in New Trends in Algebras and Combinatorics: Proceedings of the 3rd International Congress in Algebras and Combinatorics (ICAC2017). World Scientific, pp. 203-227, The Third International Congress in Algebras and Combinatorics, Hong Kong, Hong Kong, 25/08/17. https://doi.org/10.1142/9789811215476_0014

TY - GEN

T1 - Tree Breadth of the Continued Fractions Root Finding Method

AU - Kalorkoti, Kyriakos

PY - 2020/3/2

Y1 - 2020/3/2

N2 - 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.

AB - 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.

KW - Polynomial roots

KW - continued fractions

KW - tree breadth

UR - http://plbpc001.ouhk.edu.hk/ocean2017/abstractbooklet.pdf

UR - http://plbpc001.ouhk.edu.hk/ocean2017/call.html

UR - https://www.worldscientific.com/worldscibooks/10.1142/11694

U2 - 10.1142/9789811215476_0014

DO - 10.1142/9789811215476_0014

M3 - Conference contribution

SN - 978-981-121-546-9

SP - 203

EP - 227

BT - New Trends in Algebras and Combinatorics

PB - World Scientific

T2 - The Third International Congress in Algebras and Combinatorics

Y2 - 25 August 2017 through 28 August 2017

ER -

Tree Breadth of the Continued Fractions Root Finding Method

Abstract

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

Cite this