2011 · 12 citations · 13 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsHardware AccelerationParallel ArchitecturesBlock Structure AnalysisComputational Gcd AlgorithmsGpu AcceleratorsGpu ArchitectureGpu Parallel AlgorithmsGreatest Common DivisorGreatest Common Divisor AlgorithmsMixed Radix Conversion
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.
13
NVIDIA Tesla: A Unified Graphics and Computing Architecture
Erik Lindholm, John Nickolls, Stuart F. Oberman et al. · IEEE Micro · 2008 · 1.3K citations
Displacement Structure: Theory and Applications
T. Kailath, Ali H. Sayed · SIAM Review · 1995 · 441 citations