8317

Computing resultants on Graphics Processing Units: Towards GPU-accelerated computer algebra

Pavel Emeliyanenko
Max-Planck Institute for Informatics, Saarbrucken, Germany
J. Parallel Distrib. Comput., 2012

@article{emel-res-2012,

   author={Emeliyanenko, Pavel},

   title={Computing resultants on Graphics Processing Units: Towards GPU-accelerated computer algebra},

   journal={Journal of Parallel and Distributed Computing},

   year={2012},

   pages={1–14},

   month={August}

}

Download Download (PDF)   View View   Source Source   

2144

views

In this article we report on our experience in computing resultants of bivariate polynomials on Graphics Processing Units (GPU). Following the outline of Collins’ modular approach [6], our algorithm starts by mapping the input polynomials to a finite field for sufficiently many primes m. Next, the GPU algorithm evaluates the polynomials at a number of fixed points x in Z_m, and computes a set of univariate resultants for each modular image. Afterwards, the resultant is reconstructed using polynomial interpolation and Chinese remaindering. The GPU returns resultant coefficients in the form of Mixed Radix (MR) digits. Finally, large integer coefficients are recovered from the MR representation on the CPU. All computations performed by the algorithm (except for, partly, Chinese remaindering) are outsourced to the graphics processor thereby minimizing the amount of work to be done on the host machine. The main theoretical contribution of this work is the modification of Collins’ modular algorithm using the methods of matrix algebra to make an efficient realization on the GPU feasible. According to the benchmarks, our algorithm outperforms a CPU-based resultant algorithm from 64-bit Maple 14 by a factor of 100.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: