Factoring Solution Sets of Polynomial Systems in Parallel

Anton Leykin and Jan Verschelde

Abstract:

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.

Proceedings of the 2005 International Conference on Parallel Processing Workshops. 14-17 June 2005. Oslo, Norway. High Performance Scientific and Engineering Computing. Edited by Tor Skeie and Chu-Sing Yang. Pages 173-180, IEEE Computer Society, 2005.