Plain, and Somehow Sparse, Univariate Polynomial Division on Graphics Processing Units

We present multithreaded adaptations of the Euclidean plain division and the Euclidean GCD algorithms to the many-core GPU architectures We report on implementation with NVIDIA CUDA and complexity analysis with an enhanced version of the PRAM model.