INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Using Parallelism to Compensate for Extended Precision in Path Tracking for Polynomial System Solving

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF Yoffe_Genady.pdf (413KB) (no description provided) PDF
Title: Using Parallelism to Compensate for Extended Precision in Path Tracking for Polynomial System Solving
Author(s): Yoffe, Genady
Advisor(s): Verschelde, Jan
Contributor(s): Friedland, Shmuel; Leykin, Anton; Nicholls, David; Turan, Gyorgy
Department / Program: Mathematics, Statistics, and Computer Science
Graduate Major: Mathematics
Degree Granting Institution: University of Illinois at Chicago
Degree: PhD, Doctor of Philosophy
Genre: Doctoral
Subject(s): Multithreaded Graphics Processing Unit Compute Unified Device Architecture Automatic Differentiation GPU CUDA AD
Abstract: Solving polynomial systems by homotopy continuation consists of two stages: we first define a family of systems, the homotopy, and then we track the solution paths defined by the homotopy. Tracking all paths is a pleasingly parallel computation. The problem we consider in this thesis is tracking one solution path when use of extended precision is required. While tracking only one solution path could occur for systems of larger dimensions and degrees, as it is no longer feasible to compute all solutions, the need to track one difficult path with multiprecision arithmetic often arises for bigger systems. The main subject of this thesis is compensating for the extra cost of double double (DD) and of quad double (QD) precision in path tracking for sparse polynomial systems of moderate sizes by employing multiple cores. First we obtained a scalable multithreaded DD/QD version of Newton's method and subsequently of a path tracker. We achieved on eight cores for moderate systems close to maximal speedups in quad double path tracking. It appeared that in dimensions in which our DD/QD multithreaded path tracker achieves good speedups, with the use of some widely accepted algorithms for sparse polynomial systems, which we originally integrated into our multithreaded path tracker and its input processing procedure, both the path tracking and input processing take an unacceptably long time. Subsequently we have greatly increased the efficiency of our multithreaded implementation in working dimensions by improvements in three different directions. First we suggested a new input processing procedure based on functionality of a Standard Template Library (STL) sorted associative container. Secondly we came up with a choice of much more suitable predictor. Thirdly we integrated into our multithreaded implementation a prudent algorithm for polynomial evaluation and differentiation, which is based on the ideas of reverse mode Automatic Differentiation (AD). Recently we efficiently accelerated with general purpose graphics unit the same AD-like algorithm for polynomial evaluation and differentiation. We obtained two digit speedups for moderate systems as hardware double arithmetic is used.
Issue Date: 2012-12-10
Genre: thesis
Rights Information: Copyright 20012 Genady Yoffe
Date Available in INDIGO: 2012-12-10
Date Deposited: 2012-05

This item appears in the following Collection(s)

Show full item record


Country Code Views
United States of America 353
China 138
Russian Federation 12
United Kingdom 7
Germany 4


My Account


Access Key