Parallelization of triangular decompositions: Techniques and implementation

Abstract

We discuss the parallelization of algorithms for solving polynomial systems by way of triangular decomposition. The Triangularize algorithm proceeds through incremental intersections of polynomials to produce different components (points, curves, surfaces, etc.) of the solution set. Independent components imply the opportunity for concurrency. This “component-level” parallelization of triangular decompositions, our focus here, belongs to the class of dynamic irregular parallelism. Potential parallel speed-up depends only on geometrical properties of the solution set (number of components, their dimensions and degrees); these algorithms do not scale with the number of processors. To manage the irregularities of component-level parallelization we combine different concurrency patterns: map, workpile, producer-consumer, pipeline, and fork-join. We report on our implementation in the freely available BPAS library. Comprehensive experimentation with thousands of polynomial systems yields examples with up to 10.8× speed-up on a 12-core machine.