Computing Real Roots of Real Polynomials ... and now For Real!

Polynomial real root isolation using Descartes’ Rule of Signs

G. E. Collins & A. G. Akritas · 1976

Earlier work this paper cites.

Isolierung reeller Nullstellen von Polynomen

W. Krandick · 1995

Earlier work this paper cites.

Polynomial real root isolation using approximate arithmetic

J. R. Johnson & W. Krandick · 1997

Earlier work this paper cites.

Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding

V. Y. Pan · 2002

Earlier work this paper cites.

Zeros of Polynomials

N. Obreshkoff · 2003

Earlier work this paper cites.

Efficient isolation of [a] polynomial’s real roots

F. Rouillier & P. Zimmermann · 2004

Earlier work this paper cites.

A Descartes algorithm for polynomials with bit-stream coefficients

A. Eigenwillig et al · 2005

Earlier work this paper cites.

Motivations for an arbitrary precision interval arithmetic and the MPFI library

N. Revol & F. Rouillier · 2005

Cited alongside, same era.

Almost tight complexity bounds for the Descartes method

A. Eigenwillig, V. Sharma & C. K. Yap · 2006

Cited alongside, same era.

Amortized Bounds for Root Isolation via Sturm Sequences

Z. Du, V. Sharma & C. K. Yap · 2007

Cited alongside, same era.

Real Root Isolation for Exact and Approximate Polynomials Using Descartes’ Rule of Signs

A. Eigenwillig · 2008

Cited alongside, same era.

A deterministic Descartes algorithm for real polynomials

K. Mehlhorn & M. Sagraloff · 2011

Cited alongside, same era.

A simple but exact and efficient algorithm for complex root isolation

C. K. Yap & M. Sagraloff · 2011

Cited alongside, same era.

Improved bounds for the CF algorithm

E. P. Tsigaridas · 2013

Later among the works it cites.

Continued fraction real root isolation using the Hong bound

G. E. Collins · 2014

Later among the works it cites.

Algebraic algorithms

I. Z. Emiris, V. Y. Pan & E. P. Tsigaridas · 2014

Later among the works it cites.

On the complexity of computing with planar algebraic curves

A. Kobel & M. Sagraloff · 2014

Later among the works it cites.

On the complexity of the Descartes method when using approximate arithmetic

M. Sagraloff · 2014

Later among the works it cites.

From approximate factorization to root isolation with application to cylindrical algebraic decomposition

K. Mehlhorn, M. Sagraloff & P. Wang · 2015

Later among the works it cites.