2319

A complete modular resultant algorithm targeted for realization on graphics hardware

Pavel Emeliyanenko
Max-Planck Institute for Informatics, Saarbrucken, Germany
Proceedings of the 4th International Workshop on Parallel and Symbolic Computation PASCO ’10

@conference{emeliyanenko2010complete,

   title={A complete modular resultant algorithm targeted for realization on graphics hardware},

   author={Emeliyanenko, P.},

   booktitle={Proceedings of the 4th International Workshop on Parallel and Symbolic Computation},

   pages={35–43},

   year={2010},

   organization={ACM}

}

Download Download (PDF)   View View   Source Source   

601

views

This paper presents a complete modular approach to computing bivariate polynomial resultants on Graphics Processing Units (GPU). Given two polynomials, the algorithm first maps them to a prime field for sufficiently many primes, and then processes each modular image individually. We evaluate each polynomial at several points and compute a set of univariate resultants for each prime in parallel on the GPU. The remaining “combine” stage of the algorithm comprising polynomial interpolation and Chinese remaindering is also executed on the graphics processor. The GPU algorithm returns coefficients of the resultant as a set of Mixed Radix (MR) digits. Finally, the large integer coefficients are recovered from the MR representation on the host machine. With the approach of displacement structure [16] and efficient modular arithmetic [8] we have been able to achieve more than 100x speed-up over a CPU-based resultant algorithm from Maple 13.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: