Accelerating Polynomial Homotopy Continuation on Graphics Processing Units
thesisposted on 16.02.2016 by Xiangcheng Yu
In order to distinguish essays and pre-prints from academic theses, we have a separate category. These are often much longer text based documents than a paper.
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.