Yu_Xiangcheng.pdf (1.61 MB)
Download fileAccelerating Polynomial Homotopy Continuation on Graphics Processing Units
thesis
posted on 2016-02-16, 00:00 authored by Xiangcheng YuPolynomial 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.
History
Advisor
Verschelde, JanDepartment
MathematicsDegree Grantor
University of Illinois at ChicagoDegree Level
- Doctoral
Committee Member
Abramov, Rafail V. Nicholls, David Reyzin, Lev Petrovic, SonjaSubmitted date
2015-12Language
- en