Accelerating Polynomial Homotopy Continuation on Graphics Processing Units

Polynomial homotopy continuation is a symbolic-numerical method to compute all solutions of a polynomial system. In this thesis, an accelerated homotopy continuation method is designed on GPUs to compute more accurate results faster. First, we describe our massive parallel algorithm for polynomial evaluation and differentiation. Then, we design Newton's method on GPUs, which minimizes the communication between the CPU host and the GPU device. Finally, predictor-corrector algorithms are developed to track single path and multiple paths. For another contribution, we classify polynomial systems by a new type of graph. Via the canonical form of this graph, a database is implemented for storing and searching polynomial systems.