Solving Bivariate Polynomial Systems on a GPU
University of Western Ontario
AIP Conference Proceedings 1368, pp. 263-266, 2011
@article{maza2011solving,
title={Solving bivariate polynomial systems on a GPU},
author={Maza, M.M. and Pan, W.},
journal={ACM Communications in Computer Algebra},
volume={45},
number={1/2},
pages={127–128},
year={2011},
publisher={ACM}
}
We present a CUDA implementation of dense multivariate polynomial arithmetic based on Fast Fourier Transforms over finite fields. Our core routine computes on the device (GPU) the subresultant chain of two polynomials with respect to a given variable. This subresultant chain is encoded by values on a FFT grid and is manipulated from the host (CPU) in higher-level procedures. We have realized a bivariate polynomial system solver supported by our GPU code. Our experimental results (including detailed profiling information and benchmarks against a serial polynomial system solver implementing the same algorithm) demonstrate that our strategy is well suited for GPU implementation and provides large speedup factors with respect to pure CPU code.
January 25, 2012 by hgpu
