High-performance polynomial GCD computations on graphics processors

Pavel Emeliyanenko
Max-Planck-Institut fur Informatik, Saarbrucken, Germany
International Conference on High Performance Computing and Simulation (HPCS), 2011


   title={High-performance polynomial GCD computations on graphics processors},

   author={Emeliyanenko, P.},

   booktitle={High Performance Computing and Simulation (HPCS), 2011 International Conference on},





Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: