Factoring Solution Sets of Polynomial Systems in Parallel

Abstract:

In a joint work with Anton Leykin, we report on a first parallel implementation of a recent algorithm to factor positive dimensional solution sets of polynomial systems. As the algorithm uses homotopy continuation, we observe a good speedup of the path tracking jobs. However, for solution sets of high degree, the overhead of managing different homotopies and large lists of solutions exposes the limits of the master/servant parallel programming paradigm for this type of problem. A probabilistic complexity study suggests modifications to the method which will also improve the serial version of the original algorithm.

The 7th Workshop on High Performance Scientific and Engineering Computing (HPSEC-05), Oslo, Norway, 14-17 June 2005.

slides of the talk