University of Illinois at Chicago
Browse

Accelerating Polynomial Homotopy Continuation on Graphics Processing Units

Download (1.61 MB)
thesis
posted on 2016-02-16, 00:00 authored 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

2016-02-16

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC