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

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.