Tracking Many Solution Paths of a Polynomial Homotopy on a
Graphics Processing Unit in Double Double and Quad Double Arithmetic
Jan Verschelde
Abstract:
Polynomial systems occur in many areas of science and engineering.
Unlike general nonlinear systems, the algebraic structure enables
to compute all solutions of a polynomial system.
We describe our massively parallel predictor-corrector algorithms
to track many solution paths of a polynomial homotopy.
The data parallelism that provides the speedups stems from the
evaluation and differentiation of the monomials in the same polynomial
system at different data points, which are the points on the solution paths.
Polynomial homotopies that have tens of thousands of solution paths
can keep a sufficiently large amount of threads occupied.
Our accelerated code combines the reverse mode of algorithmic differentiation
with double double and quad double arithmetic to compute more accurate
results faster.
This is joint work with Xiangcheng Yu.
The 17th IEEE International Conference on High Performance Computing
and Communications (HPCC 2015), New York, 24-26 August 2015.
slides of the talk