GPU acceleration of Newton’s method for large systems of polynomial equations in double double and quad double arithmetic
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 South Morgan (M/C 249), Chicago, IL 60607-7045, USA
University of Illinois at Chicago, 2014
@article{verschelde2014gpu,
title={GPU acceleration of Newton’s method for large systems of polynomial equations in double double and quad double arithmetic},
author={Verschelde, Jan and Yu, Xiangcheng},
year={2014}
}
In order to compensate for the higher cost of double double and quad double arithmetic when solving large polynomial systems, we investigate the application of NVIDIA Tesla C2050, K20C, and K40 general purpose graphics processing units. As the dimension equals several thousands, the cost to compute one QR decomposition is sufficiently large so that the achieved speedups also compensate for the cost of data transfer of the evaluated polynomials and their derivatives. In cases where the polynomial evaluation and differentiation is relatively inexpensive, we could thus afford to leave this stage in the computation at the host. Acceleration of our modified Gram-Schmidt method enables to solve linear systems in the least squares sense in higher dimension and with greater accuracy. In particular, with acceleration it takes less time to solve a system of dimension 4,096 in double double complex arithmetic than a system of dimension 2,048 in double complex arithmetic without acceleration. On a polynomial system where the cost of evaluation and differentiation grows linearly in the dimension with an accelerated Newton’s method we obtain double digit speedups in double double complex arithmetic.
January 26, 2014 by hgpu
