Our problem is to decompose a positive dimensional solution set of a polynomial system into irreducible components. This solution set is represented by a witness set, obtained by intersecting the set with random linear slices of complementary dimension. Points on the same irreducible components are connected by path tracking techniques applying the idea of monodromy. The computation of a linear trace for each component certifies the decomposition. This decomposition method exhibits a good practical performance on solution sets of relatively high degrees defined by systems of low degree polynomials.
Using the same concepts of monodromy and linear trace, we present a new monodromy breakup algorithm. On multiple processors, we solve the synchronization issues which resulted in a performance loss of the straightforward parallel version of the original algorithm. Our new algorithm performs also better on a single processor: by exploiting several random slices and choosing pairs of slices according to accumulated statistics, the tracking of many redundant paths are avoided and new paths connecting points of the witness set are discovered with a higher probability.
2000 Mathematics Subject Classification. Primary 65H10. Secondary 14Q99, 68W30.
Key words and phrases. Continuation methods, factorization, homotopy, irreducible components, load balancing, linear trace, monodromy, numerical algebraic geometry, numerical homotopy algorithms, numerical irreducible decomposition, parallel computation, path following, polynomial systems.