Polynomial Homotopies on Multicore Workstations

Jan Verschelde and Genady Yoffe

Abstract:

Homotopy continuation methods to solve polynomial systems scale very well on parallel machines. In this paper we examine its parallel implementation on multiprocessor multicore workstations using threads. With more cores we can speed up pleasingly parallel path tracking jobs. In addition, we can compute solutions more accurately in the same amount of time with threads, and thus achieve quality up. Focusing on polynomial evaluation and linear system solving (the key ingredients of Newton's method) we can double the accuracy of the results with the quad doubles of QD-2.3.9 in less than double the time, if we use all available eight cores on our workstation.