High-performance implementations of the Descartes method

Abstract

The Descartes method for polynomial real root isolation can be performed with respect to monomial bases and with respect to Bernstein bases. The first variant uses Taylor shift by 1 as its main subalgorithm, the second uses de Casteljau's algorithm. When applied to integer polynomials, the two variants have co-dominant, almost tight computing time bounds. Implementations of either variant can obtain speed-ups over previous state-of-the-art implementations by more than an order of magnitude if they use features of the processor architecture. We present an implementation of the Bernstein-bases variant of the Descartes method that automatically generates architecture-aware high-level code and leaves further optimizations to the compiler. We compare the performance of our implementation, algorithmically tuned implementations of the monomial and Bernstein variants, and architecture-unaware implementations of both variants on four different processor architectures and for three classes of input polynomials.