Logo image
Back
High-performance implementations of the Descartes method
Conference proceeding

High-performance implementations of the Descartes method

Jeremy Johnson, Werner Krandick, Kevin Lynch, David Richardson and Anatole Ruslanov
Proceedings of the 2006 international symposium on symbolic and algebraic computation, v 2006, pp 154-161
09 Jul 2006
DOI: https://doi.org/10.1145/1145768.1145797

Abstract

Bernstein bases code generation de Casteljau Descartes high-performance computing performance tuning polynomial real root isolation register tiling Taylor shift
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.

Metrics

12 Record Views
10 citations in Scopus

Details

Logo image