Cache Complexity and Multicore Implementation for Univariate Real Root Isolation
Changbo Chen, Marc Moreno Maza, Yuzhen Xie · Journal of Physics Conference Series · 2012
We present parallel algorithms with optimal cache complexity for the kernel routine of many real root isolation algorithms, namely the Taylor shift by 1 . We then report on multicore implementation for isolating the real roots of univariate polynomials with integer coefficients based on a classical algorithm due to Vincent, Collins and Akritas. For processing some well-known benchmark examples with sufficiently large size, our software tool reaches linear speedup on an 8-core machine. In addition, we show that our software is able to fully utilize the many cores and the memory space of a 32-core machine to tackle large problems that are out of reach for a desktop implementation.