Modular Resultant Algorithm for Graphics Processors

Pavel Emeliyanenko
Max-Planck Institute for Informatics, Saarbrucken, Germany
Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science, 2010, Volume 6081/2010, 427-440


   title={Modular Resultant Algorithm for Graphics Processors},

   author={Emeliyanenko, P.},

   journal={Algorithms and Architectures for Parallel Processing},





Source Source   



In this paper we report on the recent progress in computing bivariate polynomial resultants on Graphics Processing Units (GPU). Given two polynomials in Z[x,y], our algorithm first maps the polynomials to a prime field. Then, each modular image is processed individually. The GPU evaluates the polynomials at a number of points and computes univariate modular resultants in parallel. The remaining “combine” stage of the algorithm is executed sequentially on the host machine. Porting this stage to the graphics hardware is an object of ongoing research. Our algorithm is based on an efficient modular arithmetic from [1]. With the theory of displacement structure we have been able to parallelize the resultant algorithm up to a very fine scale suitable for realization on the GPU. Our benchmarks show a substantial speed-up over a host-based resultant algorithm [2] from CGAL ( www.cgal.org ).
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: