Computing roots of polynomials by quadratic clipping

Michael Bartoň, Bert Jüttler*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


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 languageEnglish (US)
Pages (from-to)125-141
Number of pages17
JournalComputer Aided Geometric Design
Issue number3
StatePublished - Apr 2007
Externally publishedYes

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.


  • Bézier clipping
  • Polynomial
  • Root finding

ASJC Scopus subject areas

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


Dive into the research topics of 'Computing roots of polynomials by quadratic clipping'. Together they form a unique fingerprint.

Cite this