High-performance polynomial GCD computations on graphics processors
Max-Planck-Institut fur Informatik, Saarbrucken, Germany
International Conference on High Performance Computing and Simulation (HPCS), 2011
@inproceedings{emeliyanenko2011high,
title={High-performance polynomial GCD computations on graphics processors},
author={Emeliyanenko, P.},
booktitle={High Performance Computing and Simulation (HPCS), 2011 International Conference on},
pages={215–224},
year={2011},
organization={IEEE}
}
We propose an algorithm to compute a greatest common divisor (GCD) of univariate polynomials with large integer coefficients on Graphics Processing Units (GPUs). At the highest level, our algorithm relies on modular techniques to decompose the problem into subproblems that can be solved separately. Next, we employ resultant-based or matrix algebra methods to compute a GCD of each modular image in parallel. Our approach exhibits block structure to distribute the computation of a single modular GCD over several thread blocks, and thus to remove any hardware limitations on the maximal size of polynomials that can be handled. To "combine" all modular results, we have adopted Mixed-Radix Conversion (MRC) algorithm running on the GPU. Our approach shows a significant speed-up over host-based GCD algorithm from Maple 13.
December 16, 2011 by hgpu
