Yu_Xiangcheng.pdf (1.61 MB)

Accelerating Polynomial Homotopy Continuation on Graphics Processing Units

Download (1.61 MB)
thesis
posted on 16.02.2016 by Xiangcheng Yu
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.

History

Advisor

Verschelde, Jan

Department

Mathematics

Degree Grantor

University of Illinois at Chicago

Degree Level

Doctoral

Committee Member

Abramov, Rafail V. Nicholls, David Reyzin, Lev Petrovic, Sonja

Submitted date

2015-12

Language

en

Issue date

16/02/2016

Exports