A Blackbox Polynomial System Solver on Parallel Shared Memory Computers
For researchers solving polynomial systems, this work provides a parallel blackbox solver that improves computational efficiency on shared memory architectures.
The paper presents a parallel implementation of homotopy continuation methods for computing numerical irreducible decompositions of polynomial systems, achieving efficient load balancing and pipelining on multicore processors. The method is demonstrated on cyclic n-roots problems for n=8, 9, and 12.
A numerical irreducible decomposition for a polynomial system provides representations for the irreducible factors of all positive dimensional solution sets of the system, separated from its isolated solutions. Homotopy continuation methods are applied to compute a numerical irreducible decomposition. Load balancing and pipelining are techniques in a parallel implementation on a computer with multicore processors. The application of the parallel algorithms is illustrated on solving the cyclic $n$-roots problems, in particular for $n = 8, 9$, and~12.