Computing roots of polynomials by quadratic clipping

Michael Bartoň; Bert Jüttler

doi:10.1016/j.cagd.2007.01.003

Computing roots of polynomials by quadratic clipping

Michael Bartoň, Bert Jüttler^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

49 Scopus citations

Abstract

We present an algorithm which is able to compute all roots of a given univariate polynomial within a given interval. In each step, we use degree reduction to generate a strip bounded by two quadratic polynomials which encloses the graph of the polynomial within the interval of interest. The new interval(s) containing the root(s) is (are) obtained by intersecting this strip with the abscissa axis. In the case of single roots, the sequence of the lengths of the intervals converging towards the root has the convergence rate 3. For double roots, the convergence rate is still superlinear (frac(3, 2)). We show that the new technique compares favorably with the classical technique of Bézier clipping.

Original language	English (US)
Pages (from-to)	125-141
Number of pages	17
Journal	Computer Aided Geometric Design
Volume	24
Issue number	3
DOIs	https://doi.org/10.1016/j.cagd.2007.01.003
State	Published - Apr 2007
Externally published	Yes

Bibliographical note

Funding Information:
This research was supported by the Austrian Science Fund (FWF) through SFB F013 “Numerical and Symbolic Scientific Computing”, subproject 15. The authors thank the reviewers for their comments which have helped to improve the presentation of the manuscript.

Keywords

Bézier clipping
Polynomial
Root finding

ASJC Scopus subject areas

Modeling and Simulation
Automotive Engineering
Aerospace Engineering
Computer Graphics and Computer-Aided Design

Access to Document

10.1016/j.cagd.2007.01.003

Cite this

@article{f3f32c8b875a4dbb9e8d1a3c48718c30,

title = "Computing roots of polynomials by quadratic clipping",

abstract = "We present an algorithm which is able to compute all roots of a given univariate polynomial within a given interval. In each step, we use degree reduction to generate a strip bounded by two quadratic polynomials which encloses the graph of the polynomial within the interval of interest. The new interval(s) containing the root(s) is (are) obtained by intersecting this strip with the abscissa axis. In the case of single roots, the sequence of the lengths of the intervals converging towards the root has the convergence rate 3. For double roots, the convergence rate is still superlinear (frac(3, 2)). We show that the new technique compares favorably with the classical technique of B{\'e}zier clipping.",

keywords = "B{\'e}zier clipping, Polynomial, Root finding",

author = "Michael Barto{\v n} and Bert J{\"u}ttler",

note = "Funding Information: This research was supported by the Austrian Science Fund (FWF) through SFB F013 “Numerical and Symbolic Scientific Computing”, subproject 15. The authors thank the reviewers for their comments which have helped to improve the presentation of the manuscript.",

year = "2007",

month = apr,

doi = "10.1016/j.cagd.2007.01.003",

language = "English (US)",

volume = "24",

pages = "125--141",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Computing roots of polynomials by quadratic clipping

AU - Bartoň, Michael

AU - Jüttler, Bert

N1 - Funding Information: This research was supported by the Austrian Science Fund (FWF) through SFB F013 “Numerical and Symbolic Scientific Computing”, subproject 15. The authors thank the reviewers for their comments which have helped to improve the presentation of the manuscript.

PY - 2007/4

Y1 - 2007/4

N2 - We present an algorithm which is able to compute all roots of a given univariate polynomial within a given interval. In each step, we use degree reduction to generate a strip bounded by two quadratic polynomials which encloses the graph of the polynomial within the interval of interest. The new interval(s) containing the root(s) is (are) obtained by intersecting this strip with the abscissa axis. In the case of single roots, the sequence of the lengths of the intervals converging towards the root has the convergence rate 3. For double roots, the convergence rate is still superlinear (frac(3, 2)). We show that the new technique compares favorably with the classical technique of Bézier clipping.

AB - We present an algorithm which is able to compute all roots of a given univariate polynomial within a given interval. In each step, we use degree reduction to generate a strip bounded by two quadratic polynomials which encloses the graph of the polynomial within the interval of interest. The new interval(s) containing the root(s) is (are) obtained by intersecting this strip with the abscissa axis. In the case of single roots, the sequence of the lengths of the intervals converging towards the root has the convergence rate 3. For double roots, the convergence rate is still superlinear (frac(3, 2)). We show that the new technique compares favorably with the classical technique of Bézier clipping.

KW - Bézier clipping

KW - Polynomial

KW - Root finding

UR - http://www.scopus.com/inward/record.url?scp=33847382410&partnerID=8YFLogxK

U2 - 10.1016/j.cagd.2007.01.003

DO - 10.1016/j.cagd.2007.01.003

M3 - Article

AN - SCOPUS:33847382410

SN - 0167-8396

VL - 24

SP - 125

EP - 141

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

IS - 3

ER -

Computing roots of polynomials by quadratic clipping

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this