High-performance polynomial GCD computations on graphics processors

Abstract

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.